15 Puzzle Heuristic

Question

The 15 Puzzle is a classical problem for modelling algorithms involving heuristics. Commonly used heuristics for this problem include counting the number of misplaced tiles and finding the sum of the Manhattan distances between each block and its position in the goal configuration. Note that both are admissible, i.e., they never overestimate the number of moves left, which ensures optimality for certain search algorithms such as A*.

• What Heuristic do you think is proper, A* seems to work nice, do you have an example, maybe in c or java?

Solution 1

Heuristic

My heuristic of choice is to find if the sum of all inversions in a permutation is odd or even - if it is even, then the 15Puzzle is solvable.

The number of inversions in a permutation is equal to that of its inverse permutation (Skiena 1990, p. 29; Knuth 1998).

Only if I know it can be solved does it make sense to solve it. The task then is to reduce inverses and - viola problem solved. To find a solution should be no more then 80 moves.

Even more help

The equation for permutation is:

Factorials in range of 0 to 16 are {1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000}. If you need more of them, search WolframAlpha for Range[1,20]!

If you want to learn more about it read: 15Puzzle.

Solution 2

Fifteen puzzle implemetation in C++ using A* algorihtm https://gist.github.com/sunloverz/7338003