Home »

The Fifteen Puzzle can be solved in 43 "moves"

Submitted by Bruce Norskog on Wed, 12/08/2010 - 16:43.

Of course, it had been previously proved that some positions of the Fifteen Puzzle require 80 moves to solve, but in that work it was assumed that a move only affects one tile at a time. Since people commonly slide up to 3 tiles in the same row or column at once, it seems natural to count such an action as a single move. With this way of counting, which we call the "multi-tile metric," the maximum number of required moves is only 43, and of the 16!/2 = 10,461,394,944,000 valid configurations of the puzzle, there are only 16 antipodes, i.e., positions that actually require 43 moves.

The 16 antipodes include two positions that are mirror-symmetric to themselves. These two positions are those that are obtained by transposing the rows and columns with respect to either diagonal. The other antipodes consist of 7 pairs of positions that are mirror-symmetric with the other. These 14 positions also include 4 pairs of neighboring positions. So only 8 of the antipodes are "strict" antipodes having the property that any move gets you one move closer to the solved state.

Antipodes in the multi-tile metric

 1  5  9 13      x 12  8  4        12  5  9  x     15 12  1  5
 2  6 10 14     15 11  7  3        15  6 10 13      2  6 10  9
 3  7 11 15     14 10  6  2         1  7 11 14      3  7 11 13
 4  8 12  x     13  9  5  1         2  3  4  8      x  4  8 14

 x 12  8  1      x 12  8  5         x 12  5  9      x 12  1  5
15 11  7  5     15 11  7  9        15  6 10 13     15  6 10  9
14 10  6  9     14 10  6 13         1  7 11 14      2  7 11 13
 2  3  4 13      1  2  3  4         2  3  4  8      3  4  8 14

15 12  7  1     12  8  5  9        12  8  9  x     15 12  8  2
14 10  x  5     15  7  6 13        15 11  7 13     14 11  7  1
 2  6 11  9     10  x 11 14        14 10  6  4      3 10  6  5
 3  4  8 13      1  2  3  4         5  1  2  3      x  4 13  9

 x  8  5  9      x 15 12  1         x 12  8  9      x 12  8  2
12  7  6 13     14 10 11  9        15 11  7 13     15 11  7  1
15 11 10 14      2  6  7  5        14 10  6  4     14 10  6  5
 1  3  2  4      3  4  8 13         5  1  2  3      3  4 13  9

The analysis assumes the goal state for the puzzle to be:

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15  x

The work was based upon a program written by Norskog in 2006. Due to not having sufficient computer power to carry through the analysis, the project was put aside until 2009 when some further analysis was done on a computer based on an Intel i7-920 CPU. After having met at the Ohio Open cubing event earlier that year, we started a collaboration and completed the analysis in 2010 with the help of the IBM Opteron Cluster 1350 ("Glenn") at the Ohio Supercomputer Center. We will publish more details on the algorithm and computation in the near future.

-Bruce Norskog (Boston area, capella321-bruce15p@yahoo.com) and Morley Davidson (Kent State University)

» login or register to post comments | previous forum topic | next forum topic

Thanks

Submitted by Bruce Norskog on Tue, 12/28/2010 - 12:43.
Thanks, B MacKenzie. As the Wikipedia article notes, the 15 puzzle is more of a groupoid than a group, because not all moves can be composed.

Also, thanks for the independent verification that these 16 positions require 43 moves. We also have a similar optimal solver. Internally it considers there to be just 6 moves, but what those 6 moves do depend upon the position of the empty square. Basically it tries moves in the order of which column or row the empty square ends up in. (At each move after the first, only either horizontal or vertical moves need be considered, since optimal solutions alternate between horizontal and vertical moves.) So it generates different solutions than your solver.

I note that I've used lower case letters for denoting direction the empty square moves, or upper case letters for indicating the direction tiles move. In the latter case, I use put the number before the letter, so 3L means to move 3 tiles leftward. This is the format our solver currently outputs.
» parent | login or register to post comments