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

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

Solutions

Submitted by B MacKenzie on Mon, 12/27/2010 - 21:46.

Congratulations. I will be very interested in reading the details of the work.

I played around with the fifteen puzzle last summer. I found it a challenge to come up with a model of the puzzle group. I'd like to see how you approached it. In the end I came up with an IDA solver for the puzzle. By way of testing my solver, I gave it your antipodes and found 43 move solutions for each. These follow. The notation specifies the relative position of the void token after the move (token 16 in the layouts below). R = Right, L = Left, U = Up, D = Down. R3 signifies that the void token is moved three positions to the right by sliding the three intervening tokens to the left, etc.

Solving state 1 of 16
	 1  5  9 13 
	 2  6 10 14 
	 3  7 11 15 
	 4  8 12 16 
L1 U1 R1 U2 L3 D3 R2 U2 L2 D2 R1 U1 R2 U1 L3 D1 R3 U1 L3 U1 R3 
D1 L3 D1 R2 U2 L1 D3 L1 U2 R2 U1 R1 D2 L3 U1 R3 D2 L3 U2 R2 D2 R1

Solving state 2 of 16
	16 12  8  1 
	15 11  7  5 
	14 10  6  9 
	 2  3  4 13 
R1 D1 R2 U1 L1 D2 R1 D1 L3 U1 R3 D1 L3 U3 R3 D3 L2 U2 R2 D2 L1 
U3 R1 D2 L1 U1 R1 D1 L3 U2 R2 D2 L2 U2 R3 D2 L3 D1 R3 U1 L3 D1 R3

Solving state 3 of 16
	15 12  7  1 
	14 10 16  5 
	 2  6 11  9 
	 3  4  8 13 
L1 D2 L1 U3 R1 D3 L1 U3 R1 D1 R2 D2 L3 U2 R3 D1 L3 U1 R3 U1 L3 
D1 R3 U1 L1 D3 L1 U3 R1 D3 L2 U1 R3 D1 L2 U2 R2 D2 L3 U3 R1 D3 R2

Solving state 4 of 16
	16  8  5  9 
	12  7  6 13 
	15 11 10 14 
	 1  3  2  4 
R1 D1 R2 U1 L2 D1 R2 D2 L3 U2 R3 D2 L3 U2 R2 D2 L2 U3 R3 D3 L2 
U2 R1 D2 L1 U3 R1 D1 L2 U1 R3 D2 L1 U2 R1 D1 L3 U1 R3 D1 L1 D2 R1

Solving state 5 of 16
	16 12  8  4 
	15 11  7  3 
	14 10  6  2 
	13  9  5  1 
R1 D1 R2 D1 L3 U1 R3 U1 L3 D1 R3 D1 L3 D1 R3 U1 L2 U2 R1 D3 R1 
U2 L2 D2 L1 U1 R3 U1 L2 D2 R2 U3 L3 D1 R2 U1 L2 D2 R2 U2 L1 D3 R2

Solving state 6 of 16
	16 12  8  5 
	15 11  7  9 
	14 10  6 13 
	 1  2  3  4 
R1 D3 L1 U2 R3 D1 L3 U1 R3 U1 L3 D1 R2 D2 L1 U3 R1 D3 L2 U1 R1 
U2 R1 D2 L1 U1 R2 D2 L3 U2 R3 U1 L3 D1 R3 D1 L2 U2 R2 D1 L2 D2 R2

Solving state 7 of 16
	12  8  5  9 
	15  7  6 13 
	10 16 11 14 
	 1  2  3  4 
L1 U1 R3 D1 L3 D1 R1 U2 R2 D2 L2 U3 R2 D3 L2 U3 L1 D3 R2 U2 L1 
U1 R2 D2 L2 U2 L1 D1 R3 D1 L3 U1 R3 D1 L1 U2 L1 D3 R1 U3 L1 D3 R2

Solving state 8 of 16
	16 15 12  1 
	14 10 11  9 
	 2  6  7  5 
	 3  4  8 13 
R1 D1 R2 U1 L2 D3 L1 U2 R3 U1 L3 D1 R3 U1 L2 D3 L1 U3 R1 D3 R2 
U3 L2 D3 R2 U3 L2 D3 R2 U2 L3 D1 R1 D1 R2 U2 L2 D2 L1 U2 R2 D2 R1

Solving state 9 of 16
	12  5  9 16 
	15  6 10 13 
	 1  7 11 14 
	 2  3  4  8 
L1 D2 L1 U2 L1 D3 R1 U3 L1 D2 R2 D1 L2 U1 R3 U2 L2 D3 R2 U3 L2 
D3 R2 U3 L2 D3 R2 U2 L3 D2 R3 U3 L2 D3 R1 U2 L2 D1 R3 U1 L2 D2 R2

Solving state 10 of 16
	16 12  5  9 
	15  6 10 13 
	 1  7 11 14 
	 2  3  4  8 
R1 D1 L1 U1 R2 D3 R1 U2 L3 D1 R3 U2 L2 D3 R1 U3 L1 D3 R2 U1 L1
 U2 L2 D3 R3 U3 L2 D2 R2 U1 L3 D1 R3 U1 L3 D1 R2 U2 L1 D1 R1 D2 R1

Solving state 11 of 16
	12  8  9 16 
	15 11  7 13 
	14 10  6  4 
	 5  1  2  3 
L1 D1 L1 D2 L1 U1 R1 U1 L1 D1 R3 U2 L3 D2 R3 U1 L3 D2 R3 U2 L2 
D2 R2 U3 L2 D3 R1 U3 L1 D2 L1 D1 R3 U2 L3 D2 R1 U1 R2 U2 L1 D3 R1

Solving state 12 of 16
	16 12  8  9 
	15 11  7 13 
	14 10  6  4 
	 5  1  2  3 
R1 D2 L1 U2 R1 D3 L1 U2 R2 U1 R1 D2 L3 U2 R3 D1 L1 D2 L1 U3 R1 
D3 L2 U3 R2 D2 L2 U2 R3 D3 L2 U1 L1 U1 R3 D2 L3 U2 R3 U1 L1 D3 R1

Solving state 13 of 16
	15 12  1  5 
	 2  6 10  9 
	 3  7 11 13 
	16  4  8 14 
R1 U2 L1 D2 R2 U3 L2 D2 R3 U2 L3 D1 R2 U1 L2 D2 R3 U1 L1 D2 L2 
U2 R2 U1 L2 D2 R3 U2 L1 D3 L2 U2 R2 D2 R1 U2 L1 D1 L2 U1 R1 D2 R2

Solving state 14 of 16
	16 12  1  5 
	15  6 10  9 
	 2  7 11 13 
	 3  4  8 14 
R1 D1 L1 U1 R2 D2 R1 U1 L3 D1 R3 U1 L1 D2 L1 U3 R1 D3 R1 U2 L3 
D2 R3 U2 L1 D1 L2 U2 R3 D1 L3 U1 R3 D2 L3 U2 R2 D2 L2 U2 R2 D3 R1

Solving state 15 of 16
	15 12  8  2 
	14 11  7  1 
	 3 10  6  5 
	16  4 13  9 
R1 U1 R2 U1 L3 D1 R3 D1 L3 U1 R3 U2 L2 D3 R1 U3 L2 D1 R3 U1 L2
D1 R2 D2 L3 U2 R3 U1 L2 D3 R2 U3 L2 D3 R2 U3 L3 D3 R3 U3 L3 D3 R3

Solving state 16 of 16
	16 12  8  2 
	15 11  7  1 
	14 10  6  5 
	 3  4 13  9 
R1 D1 R1 D2 L2 U1 R3 D1 L3 U3 R2 D2 R1 D1 L2 U1 R2 D1 L2 U3 R1 
D1 R1 D1 L2 U2 R1 D2 L2 U2 R3 D2 L3 U2 R3 D2 L3 D1 R3 U1 L3 D1 R3
» login or register to post comments

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.
» login or register to post comments

Group or Groupoid?

Submitted by B MacKenzie on Wed, 12/29/2010 - 10:43.

Encoded as elements of the S16 permutation group, you're quite right. The states of the puzzle do not form a mathematical group. Nevertheless, I was able to formulate a permutation group which maps 1:1 to the states of the puzzle. Since the puzzle moves are performed relative to the void token, I chose to use the void token as the reference point from which to describe the state of the puzzle. To encode a puzzle state the columns and rows of the tableau are rolled right and down to place the void token in position 16. Using the third antipode above as an example: 

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

Tokens 1 through 15 in the rearranged tableau define a permutation. In GAP cycle notation:

(1,9)(3,6)(4,11,12,7)(5,13)(10,15)

The frame shift is then encoded using two cyclic permutation groups of order 4, one for the vertical shift and one for the horizontal shift.

(1,9)(3,6)(4,11,12,7)(5,13)(10,15) * (16,18)(17,19) * (20,21,22,23)

Thus, in this representation a state is encoded with a 15 element permutation giving the arrangement of the tokens relative to the void token and two cycle permutations encoding the position of the void token. With this encoding the puzzle moves on on the identity state are:

L1 := (1,4,3,2)(5,8,7,6)(9,12,11,10)(13,15,14)(20,21,22,23);

U1 := (1,13,9,5)(2,14,10,6)(3,15,11,7)(4,12,8)(16,17,18,19);

And all states of the puzzle may be formed from these two generators:

XV_Group := Group( L1 , U1 );
Group([ (1,4,3,2)(5,8,7,6)(9,12,11,10)(13,15,14)(20,21,22,23), 
  (1,13,9,5)(2,14,10,6)(3,15,11,7)(4,12,8)(16,17,18,19) ])

Size( XV_Group );
10461394944000

Note that the physical restraints of the puzzle means that the Cayley graph of the puzzle moves is the same as the Cayley graph of the above group with missing edges. Although the product (L1 * L1 * L1 * L1) is a valid state of the puzzle, the move sequence (L1 L1 L1 L1) cannot be performed on the physical puzzle.

» login or register to post comments