Search code examples
pythonalgorithmpypysliding-tile-puzzle

5x5 Sliding Puzzle Fast & Low-Move Solution

I am trying to find a way to programmatically solve a 24-piece sliding puzzle in a reasonable amount of time and moves. Here is an example of the solved state in the puzzle I am describing:

5x5 Solved Sliding Puzzle

I have already found that the IDA* algorithm works fairly well to accomplish this for a 15-puzzle (4x4 grid). The IDA* algorithm is able to find the lowest number of moves for any 4x4 sliding puzzle in a very reasonable amount of time. I ran an adaptation of this code to test 4x4 sliding puzzles and was able to significantly reduce runtime further by using PyPy. Unfortunately, when this code is adapted for 5x5 sliding puzzles it runs horribly slow. I ran it for over an hour and eventually just gave up on seeing it finish, whereas it ran for only a few seconds on 4x4 grids. I understand this is because the number of nodes that need to searched goes up exponentially as the grid increases. However, I am not looking to find the optimal solution to a 5x5 sliding puzzle, only a solution that is close to optimal. For example, if the optimal solution for a given puzzle was 120 moves, then I would be satisfied with any solution that is under 150 moves and can be found in a few minutes.

Are there any specific algorithms that might accomplish this?

Solution

  • It as been proved that finding the fewest number of moves of n-Puzzle is NP-Complete, see Daniel Ratner and Manfred Warmuth, The (n2-1)-Puzzle and Related Relocation Problems, Journal of Symbolic Computation (1990) 10, 111-137.

    Interesting facts reviewed in Graham Kendall, A Survey of NP-Complete Puzzles, 2008:

    • The 8-puzzle can be solved with A* algorithm;
    • The 15-puzzle cannot be solved with A* algorithm but the IDA* algorithm can;
    • Optimal solutions to the 24-puzzle cannot be generated in reasonable times using IDA* algorithm.

    Therefore stopping the computation to change the methodology was the correct things to do.

    It seems there is an available algorithm in polynomial time that can find sub-optimal solutions, see Ian Parberry, Solving the (n^2−1)-Puzzle with 8/3n^3 Expected Moves, Algorithms 2015, 8(3), 459-465. It may be what you are looking for.