5x5 Sliding Puzzle Fast & Low-Move Solution

Question

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:

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?

Actually

Commenting since I don't know if this will work, but you could try IDA* to fix the top two rows quickly, then IDA* from whatever configuration resulted to solve the bottom three without moving the top. – Plated

Answer 1

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.

Lumberyard

Do we know that it cannot be solved with A*/IDA* or is it possible that a better heuristic cost function would work? – Galina

I'm going to award the bounty to this answer as well as accept it because I think that is is overall the highest quality answer, however, I wish that I could award the bounty to multiple answers because I have gleaned helpful advice from multiple. I tried the algorithm mentioned in this answer, and although it ran fairly quickly, it unfortunately took more moves on average than I was hoping it would. I ended up doing something similar to what @Martijn Pieters suggested and instead reduced the board to a 4x4 puzzle in a rather inefficient way, and then just ran IDA* on the remainder. – Actually

With that solution, I was able to get a slightly better average case and a much better best case in terms of moves. Overall, I'd like to thank everyone for their solutions and suggestions though as they were all helpful in their own ways and provided different insights. – Actually

Answer 2

IDA* works great up to a 4x4 puzzle, because that's 'just' 16! (20,922,789,888,000‬) possible states. A 5x5 puzzle has 25! (15,511,210,043,330,985,984,000,000) possible states, a factor of 740k million larger.

You need to switch strategies. The 'easiest' method solves the puzzle along the top row and then left column first, repeatedly, until you have a 3x3 puzzle, which can easily be solved using existing techniques.

Solving the puzzle involves 3 different phases you alternate between:

1. Solve the top row (move the pieces for columns 1 - N-2 into place, then move the piece for column N-1 to column N, the piece for column N to colum N, but one row below, finish the row)
2. Solve the left column (move pieces for rows 2 - N-2 into place, then move the piece for row N-1 to row N, piece for row N to row N but one column to the right, finish the column)
3. (2 rows of 3 columns remaining): use A* to solve the remainder.

So phases 1 and 2 alternate until you can run phase 3; after solving the top 5 tiles (phase 1) you solve the left-most 4 tiles on the other rows (phase 2), then the top row of the remainder of the puzzle (4 tiles, phase 1), then the left column (3 tiles, phase 2), then solve phase 3. Phases 1 and 2 are basically identical, only the orientation differs, and for phase 2 the first tile is already in place.

Phases 1 and 2 are easily solved using lookup tables, no search required; you are moving specific tiles and don't care about anything else:

• Locate the desired tile
• Get the gap next to the tile (it depends on the direction of movement what side is best)
• Move the tile into position; there are standard moves that move a tile in any direction (5 for vertical or horizontal moves, 6 for diagonal).

This doesn't give you the shortest path to a solution, but with no state search the problem is strictly bound and the worst case scenario known. Solving the first row and column of a 5x5 puzzle takes at most 427 moves this way, and 256 moves for the next row and column.

This algorithm was first described by Ian Parberry, in a paper titled A real-time algorithm for the (n2 − 1)-puzzle in 1995. I think that DSolving: a novel and efficient intelligent algorithm for large-scale sliding puzzles by GuiPing Wang and Ren Li describes a more efficient lookup-table method still, but as the paper isn't yet available for free I haven't studied it yet.

Repressive

Answer 3

A two-character change that might do the trick is to multiple the heuristic by 2 (or some other constant). It's no longer admissible, but the solution found will be within a factor of 2 of optimal. This trick is called Weighted A*/Static Weighting.

Plated