I am now developing a 15 puzzle game. I know the method to detect unsolvable puzzles. But unlike 8-puzzle, solution for 15-puzzle takes quite long time for some input states and can be solved within 5 seconds some other set of input states.
Now the problem is that I cannot give the user(the player), a problem for which the solution takes more than 10 seconds(if he/she chooses to see the solution). So what I want is that when I initially shuffle the puzzle, I want to only present those puzzles which can be solved within 10 seconds. There must be some way to determine the hardness of the puzzle. I tried searching the net but could not find it.
Does anyone know a way of determining the hardness of a puzzle?
NOTE : I am using A* algorithm to find out the solution on a computer with 3GB RAM and 2.27GHZ processor.
EDIT : I have an additional requirement also. I am including a Puzzle Solver also. So based on the user's input, the cpu will solve the problem. Present A* algorithm with manhattan distance as heuristic takes a lot of time. First of all I would like to know which algorithm to choose - A* or IDA or some other. And I would like to know about other heuristics also.
-
\$\begingroup\$ What heuristic are you using? You can achieve better results with a better heuristic. \$\endgroup\$– MatsemannCommented Nov 3, 2012 at 10:40
-
\$\begingroup\$ @Matsemann : I am using manhattan distance \$\endgroup\$– AshwinCommented Nov 3, 2012 at 10:45
-
\$\begingroup\$ @Matsemann : which heuristic do you suggest? Please give it in the answer section with some details. thank you \$\endgroup\$– AshwinCommented Nov 3, 2012 at 13:10
-
\$\begingroup\$ "I want to only present those puzzles which can be solved within 10 seconds" - by someone who's an expert at 15 puzzles, or someone who's never seen one before? By someone who has excellent mental skills for solving 15 puzzles, or someone who is poor at the mental skills it takes? That said, any of the above might simply stare vacantly at the puzzle for a few seconds before their brain leaps into action. I don't think there is any set of 15 puzzles which can be defined as "solvable in 10 seconds", in theory or in practice. \$\endgroup\$– doppelgreenerCommented Nov 3, 2012 at 14:32
-
3\$\begingroup\$ related: stackoverflow.com/questions/94975/…, stackoverflow.com/questions/5367078/15-puzzle-heuristic, stackoverflow.com/questions/7701345/… \$\endgroup\$– Ray TayekCommented Nov 3, 2012 at 18:11
2 Answers
The time needed to solve a 15 puzzle depends a lot on how the player approaches the problem. Those using a systematic solving method will solve any solvable puzzle in about a minute or two, depending on how much practice they've had. On the other hand, a systematic solution will generally take about the same time regardless of how well scrambled the puzzle is.
Meanwhile, people who don't use any kind of systematic approach, but just slide the blocks around randomly and hope that they'll fall into place, will probably not manage to solve any but the most trivial of puzzles in any reasonable time, if ever. If they haven't solved it in 10 moves, they probably won't manage to solve it at all.
(Solving a 15 puzzle systematically is easy enough that even new players may figure it out on their own. Just the two rules — 1) solve the puzzle in numerical order, and 2) don't disturb completed rows unless you absolutely have to — will essentially do it, even if you may need to experiment a bit to figure out details like how to get the last block in a row in place.)
Anyway, the point of all this is that the "difficulty of the puzzle" is not well defined — it depends entirely on the solver. Sure, you could use Markus von Broady's suggestion to guarantee that there exists a solution with at most n moves, but unless n is really small, most people will either fail to spot the solution or will not even try, preferring their own solution method instead.
Edit: After you clarified the question, I see that you're concerned about the time taken by the computer — not the player — to solve the puzzle. As you've noticed, using A* to solve the 15 puzzle can take a while; the problem is that, unless the solver happens to find a particularly good solution early on, the search space quickly branches out into a huge number of partial solutions with identical scores.
The obvious solution there would be to dispense with the A* search and instead implement a systematic solution method like the one I linked to above. Such methods won't produce an optimal solution, but they do produce a solution to the puzzle very quickly. (As a bonus, the solution they generate will be of a type which the player can feasibly imitate, whereas the optimal solutions found with A* tend to seem "magic".)
Alternatively, you might try using A* in stages — that is, for example, first use A* to find a sequence of moves that solves the first row of the puzzle, ignoring the other tiles (i.e. treat them as identical and don't include them in the heuristic), then restart A* from the result of that solution to solve the second row, and so on. (Remember that the last two rows will need to be solved together.) This should produce something similar, but possibly a bit more efficient, than the purely systematic solution.
Just start with finished puzzle, and then make let's say 10 random moves (1 for every second) of tiles to make sure the puzzle is both solvable and can be done in 10 moves. Make sure your moves don't negate previous, e.g. moving 3 tiles in "circle" or moving a tile back where it was before previous move.
KISS
Edit: A* is not designed to help you in solving 15 puzzle. The fact that your CPU can't do it in 10 seconds show it clearly. There are better algorithms for that, probably you could find one from some programming olympics, but it's not hard to do one yourself when you know the methodology: http://www.wikihow.com/Solve-a-Fifteen-Puzzle
The absurd is, you use complex maths to generate a random puzzle and make sure it is solvable, only to use a complex algorithm to find a solution that in best scenario is an exact opposite of creating this puzzle the easy way, and even then is much more slower because of conditionals taking place.
Edit2: I see now, that your problem is to find a solution after a player moved some pieces in his attempt to solve the puzzle. In regards to my advice above, you could remember player's moves and revert them, or just reset the puzzle or indeed you would need to create an algorithm based on the link provided.
