Techniques/tools for constructing hard instances of a puzzle game

Are there techniques and/or software tools that can be used to construct hard instances of a simple puzzle game (or a simple planning problem)?

With "hard" I mean that any solution of the instance is "long" with respect to the input size.

What I have in mind:

• model the puzzle game using a constraint programming language (or even STRIPS);
• the tool starts with assigning some random values to the model parameters to construct an instance;
• solve the instance and if solutions are "easy" (shorter than a fixed length) or no solution is found in a specified amount of time, try to adjust it using some heuristics (or other techniques such as GA or simulated annealing).
• Is the puzzle a known one, such as Sudoku? Can we assume the puzzle is difficult to solve (is it NP-complete)? – Juho Apr 28 '12 at 11:41
• @mrm: I haven't a particular puzzle in mind. However I'm interested in finding long solutions of "puzzle games" (planning problems) whose complexity is suspected to be PSPACE-complete. Finding instances that have only long solutions can be a clue of their hardness. – Vor Apr 28 '12 at 21:36

As I understand it, the problem you are interested in is Bounded PlanSAT which asks whether there is a solution of length $k$ or less. PlanSAT on the other hand asks whether there exists any plan than solves the problem. Bounded PlanSAT is, for example, decidable even if we add function symbols to our language and thus make the number of states infinite. Both of these decision problems are indeed in $\text{PSPACE}$.

As for your problem of generating hard instances (meaning long solutions), one approach could be GRAPHPLAN which uses a data structure called the planning graph. Now, the planning problem asks if we can reach a goal state $G$ from the initial state $S_0$. Suppose we are given a tree of all possible actions from the initial state to successor states, and their successors, and so on. Indexed appropriately, we could answer the question of "is $G$ reachable from $S_0$?" just by looking it up. This is naturally impractical, since the tree is of exponential size. The planning graph is a polynomial-size approximation to this tree that can be constructed quickly.

The planning graph can't answer for sure whether $G$ is reachable from $S_0$, but it can estimate how many steps it takes to reach $G$. The estimate is always correct when it reports $G$ is not reachable, and it never overestimates the number of steps. Hence it is an admissible heuristic.

I agree this is perhaps not exactly what you are looking for. Nevertheless this way, one does not have to actually solve the instance. I don't think solve time is a particularly useful measure of hardness. For some solvers, some instances are easy. For some solvers, they are hard. In this sense, something like long solutions seem like a good measure of hardness.

Another thing that crossed my mind was the fact that classical planning can be represented as a constraint problem (SAT/CSP, see for example SATPLAN). If translated as SAT for example, one can use all the tools available in that domain. You might be interested for example in the question Measuring the difficulty of SAT instances. As for directly generating an instance of planning that has a solution of length more than $k$, I don't know the answer to.

By the way, if you want to solve instances in practice, Helmert (2001) analyzes many classes of planning problems and notes that constraint-based approaches such as GRAPHPLAN and SATPLAN are best for $\text{NP}$-hard domains while search-based approaches do better in domains where feasible solutions can be found without backtracking. Both have problems in domains with many objects because they must create many actions. One can also check out the International Planning Competition (IPC), similar to the SAT competition(s).