# 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)