How can I solve Sam Loyd's "15" puzzle, which consists of 15 sliding pieces in a 4 by 4 array, looking like...
competition/games/15.puzzle Added material
Problem
How can I solve Sam Loyd's "15" puzzle, which consists of 15 sliding pieces in a 4 by 4 array, looking like this when solved? [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [10] [11] [12] [13] [14] [15]
Show solution
First you need to know if the starting position is even solvable. Count the number of "inversions", larger numbers coming before smaller numbers. If the number of inversions is odd then you can only "solve" for other positions with an odd number of inversions. If you find an even number, you can only "solve" for other even positions. Consider the case with the last two tiles reversed: [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [10] [11] [12] [13] [15] [14] In this case the starting position is odd (15 before 14 is the only inversion), but the goal has all the numbers in order, which is even (no inversions) so you can not do it by sliding the numbers around. You may be able to disassemble the puzzle and reassemble it in order, but that is against the rules. Here is a common-sense proof. Take about five different objects, and assign them to places on your desk. Define a "swap" as the operation of taking two different objects and interchanging their places. Observe, by experimentation, that any re-ordering that can be done with an odd number of swaps, cannot be done with an even number of swaps. Also, any re-ordering that can be done with an even number of swaps, cannot be done with an odd number of swaps. For instance, [ABCDE]->[BACDE] can be done in any odd number of swaps. [ABCDE]->[CABDE] can be done only in even numbers of swaps. Now consider the 15-puzzle. It has 16 components (15 tiles and the hole). The basic operation consists of swapping the hole with one of the adjacent tiles. If we start with the hole at the bottom right, do some swaps, and end with the hole at the bottom right, we must have made an even number of swaps (the hole has ended up where it started, so the distance it has travelled must be even). So if the hole is to end up where it started, we can only achieve positions which can be achieved by even numbers of swaps. The position which started this thread had the 14 and the 15 swapped round and everything else in place, and so could only be achieved in an odd number of swaps. Here is a somewhat more mathematical proof based on one in _The Master Book of Mathematical Recreations_, by Frederik Schuh. Label the squares in the following order: A B C D H G F E I J K L P O N M Define two pieces in the 15-puzzle to be inverted if the larger number is on the smaller-lettered square; thus, in the standard solution, the last row is 13-14-15-blank, so the pairs 13-14, 13-15, and 14-15 are inverted. Any horizontal move does not change inversions. A vertical move changes an even number of inversions; for example, moving a piece from G to J will cause it to be inverted with H in its new position if and only if it wasn't inverted before, and likewise with I. Therefore, if the initial number of inversions is even, it will always stay even; there is no way to switch two pieces. This puzzle was introduced in the 19th century by Sam Loyd, and was as popular as Rubik's Cube was in the 20th. A version of this with letters was attributed to Loyd. The requirement was to make the message RATE YOUR MIND PAL. The letters in the words RATE YOUR were one color, and the letters in the words MIND PAL were a different color. The trickster would show the punter it done and then mix it up and offer it to the punter to solve. Most often he couldn't do it. Here's why. The goal position is R A T E Y O U R M I N D P A L Notice that the puzzle has 2 Rs with the same color and two As with different colors. You can't swap the two Rs (nor any pair of tiles), so mix up the letters placing the R in YOUR in the upper-left corner and placing the other R far away from the corner. There is a strong tendency to leave the R in the upper-left corner where it is but this amounts to solving the puzzle with the Rs swapped which can't be done. If the punter knows how to solve the version with numbers 1 through 15, then he will eventually reach the position where the last two letters are swapped. Typically he will forever try to complete this last "step" not realizing that you can't independently swap two tiles.
Additional material
[ Editor: lower bounds for the worst case of the generalized puzzle,
from the rec.puzzles thread "Deranged puzzle data", November 1993. Jim
Ferry's first posting gave a table that ignored parity; he replaced it
the next day with the article below, which he said was how the first
"should have read". ]
+---+---+---+---+ I don't know what this puzzle is called, but I
| 1 | 2 | 3 | 4 | remember it generating some talk recently. You all
+---+---+---+---+ recognize it I assume. To solve the puzzle one puts
| 5 | 6 | 7 | 8 | a shuffled arrangement of the 16 squares on the left
+---+---+---+---+ into this standard form by successively swapping the
| 9 |10 |11 |12 | blank square with adjacent numbered squares.
+---+---+---+---+
|13 |14 |15 | | This article contains results about the maximum
+---+---+---+---+ number of moves required to solve the puzzle.
We generalize to the case of an A x B rectangle, where A and B are
integers greater than 1.
Imagine a chessboard lying beneath the numbers, with a white square in
the lower righthand corner (where the blank is, in the solved
position). We define the "color parity" of an arrangement to be even
if the color exposed by the blank is white and odd if it is black.
We can think of an arrangement of squares as a permutation of the
numbers 1,2, . . . A*B (we identify the blank with A*B, and consider
the solved position to correspond to the identity permutation). We now
define the "total parity" of an arrangement as its permutation's parity
plus its color parity.
Since each move we flip both the color and permutation parities, the
total parity remains fixed. This motivates the following theorem (the
proof is at the end of the article).
---------------------------------------------------------------------
Theorem: For A,B > 1, the puzzle can be solved if and only if the
total parity of the arrangement it's in is even.
---------------------------------------------------------------------
The following table gives lower bounds for the maximum number of moves
required to solve the puzzle. In other words, for a given A and B, the
table says, "there exist arrangements that can be solved but take at
least this many moves to solve."
Lower Bounds for Worst-Case Derangement
Distances (for reachable cases, of course)
| 2 3 4 5 6 7 8 9 10
--+--------------------------------------------
2 | 6 14 20 26 33 41 49 57 66
|
3 | 14 20 28 37 47 57 68 79 91
|
4 | 20 28 39 51 64 78 92 107 122
|
5 | 26 37 51 67 83 100 118 137 157
|
6 | 33 47 64 83 103 124 147 170 193
|
7 | 41 57 78 100 124 150 176 204 232
|
8 | 49 68 92 118 147 176 207 239 272
|
9 | 57 79 107 137 170 204 239 275 313
|
10 | 66 91 122 157 193 232 272 313 355
One might also use the easily derived Ceiling(Log_3((A*B)!/4)) to
generate lower bounds that are pretty good.
The Mathematica code is below. It's as simple as its brevity
indicates. It begins with the blank in the southwest corner and
considers paths that the blank could take that don't immediately double
back on themselves (e.g. the blank might move n,e,e,s,w,n,w, but the
next move couldn't be 'e'). Let n(i,j,t) be the number of paths the
blank could take, starting at (1,1) and ending after t moves at (i,j),
having just come north (similarly for e(), s(), and w() ). Define S(k)
as 1 + the sum of n,e,s, and w from t = 1 to k and over all (i,j).
Finally, let T(k) be the number of arrangements that can be reached in
k moves or less. Clearly T(k) <= S(k). If all arrangements can be
reached in N moves, then T(N) = (A*B)!/2. Therefore the least k such
that S(k) >= (A*B)!/2 is a lower bound for N.
This program's efficiency could be improved by taking D2 symmetry into
account (or D4 for A=B). Furthermore, since the problem is a
first-order linear difference equation, one might calculate the
eigensystem of the appropriate matrix to solve the problem. However,
floating point operations could jeopardize the rigor of the result.
f[a_Integer,b_Integer] := If[a > 1 && b > 1,
Block[{i,j,iters,perm,paths,tot},
For[i=1, i<=a, i++, For[j=1, j<=b, j++,
nx[i,j] = ex[i,j] = sx[i,j] = wx[i,j] = 0]];
For[i=1, i<=a, i++, ny[i,1] = sy[i,b] = 0];
For[j=1, j<=b, j++, ey[1,j] = wy[a,j] = 0];
nx[1,2] = ex[2,1] = 1;
For[iters=1; perm=(a*b)!/2-3, perm>0, iters++; perm-=paths,
If[Mod[iters,2]==1,
n1=nx; e1=ex; s1=sx; w1=wx; n2=ny; e2=ey; s2=sy; w2=wy,
n1=ny; e1=ey; s1=sy; w1=wy; n2=nx; e2=ex; s2=sx; w2=wx];
For[paths=0; i=1, i<=a, i++, For[j=1,j<=b, j++,
tot = s1[i,j] + w1[i,j] + n1[i,j] + e1[i,j];
paths +=
If[j!=b, n2[i,j+1] = tot - s1[i,j], 0] +
If[i!=a, e2[i+1,j] = tot - w1[i,j], 0] +
If[j!=1, s2[i,j-1] = tot - n1[i,j], 0] +
If[i!=1, w2[i-1,j] = tot - e1[i,j], 0];
]];
];
iters
]];
Proof of the Theorem:
The "only if" is immediate, since the solved position has even parity.
To show the "if", we give an explicit method for solving the puzzle.
We talk about the 4 x 4 case, but the arguments generalize
automatically.
Given a shuffled arrangement, we first move the +---+---+---+---+
blank onto a white square. Next, we relabel | d | c | b | a |
with d=1,c=2, etc, such that the solved position +---+---+---+---+
is as shown. The problem is now reduced to | e | f | g | h |
sorting a scrambled, linear array of letters +---+---+---+---+
(using appropriate operations) given that the | l | k | j | i |
scrambed array is an even permutation of abc...p. +---+---+---+---+
The sorting is easy if we allow ourselves cyclic | m | n | o |(p)|
permutations of 3 (linearly) adjacent elements. +---+---+---+---+
We can bring 'a' to the beginning, then put 'b'
next, etc, in a fashion similar to bubble-sort. We can thereby sort up
through 'n'. The letters 'o' and 'p' fall into place because we began
with an even permutation of abc...p.
How do we justify using those 3-cycles? The problem reduces to being
able to perform the following operations R and S:
+---+---+ +---+---+ +---+---+---+ +---+---+---+
| 1 | 2 | R | 3 | 1 | | 1 | 2 | 3 | S | 2 | 3 | 1 |
+---+---+ <-> +---+---+ and +---+---+---+ <-> +---+---+---+
| 3 | | | 2 | | | 4 | 5 | | | 4 | 5 | |
+---+---+ +---+---+ +---+---+---+ +---+---+---+
If we can do these then to shift 'efg' to 'fge' (for example) in the
"solved alphabet picture" above, we simply move the blank to where 'j'
is, apply 'S', and move the blank back to where it was (along the
reverse path).
'R' is easy to do. If we let 'n' denote "move the blank north", and
similarly for 'e', 's', and 'w' we have:
R = nwse.
We show how to do 'S' graphically, using 'R':
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| 1 | 2 | 3 | w | 1 | 2 | 3 | R | 1 | 3 | 5 | R | 4 | 1 | 5 | R
+---+---+---+ -> +---+---+---+ -> +---+---+---+ -> +---+---+---+ ->
| 4 | 5 | | | 4 | | 5 | | 4 | | 2 | | 3 | | 2 |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
+---+---+---+ +---+---+---+ +---+---+---+
| 4 | 2 | 1 | R | 2 | 3 | 1 | e | 2 | 3 | 1 |
+---+---+---+ -> +---+---+---+ -> +---+---+---+
| 3 | | 5 | | 4 | | 5 | | 4 | 5 | |
+---+---+---+ +---+---+---+ +---+---+---+
This completes the proof.
-- Jim Ferry <jpf@sticky.rockefeller.edu>
[ Editor: the table in Ferry's first posting, which did not take parity
into account (it bounded the number of moves needed to reach all
(A*B)! arrangements, and used essentially the same code with (a*b)! in
place of (a*b)!/2): ]
Lower Bounds for Worst-Case Derangement Distances
| 1 2 3 4 5 6 7 8 9 10
--+------------------------------------------------
1 | 0 1
|
2 | 1 16 21 28 35 42 50 58 67
|
3 | 16 22 29 38 48 58 69 80 92
|
4 | 21 29 40 52 65 79 93 108 123
|
5 | 28 38 52 67 84 101 119 138 157
|
6 | 35 48 65 84 104 125 147 170 194
|
7 | 42 58 79 101 125 151 177 204 232
|
8 | 50 69 93 119 147 177 208 239 272
|
9 | 58 80 108 138 170 204 239 276 313
|
10| 67 92 123 157 194 232 272 313 356
Note: Null entries denote a value of infinity, i.e. there exist
unreachable arrangements. I nullified a few obvious ones. Some finite
values in the table may merely be gross underestimates of infinity. I
haven't looked into it.
-- Jim Ferry
In article <1993Nov28.051254.18368@rockyd.rockefeller.edu>
jpf@sticky.rockefeller.edu (Jim Ferry) writes:
>One might also use the easily derived Ceiling(Log ((A*B)!/4)) to
>generate lower bounds that are pretty good. 3
The worst-case is known to be 31 in the 3x3 puzzle, and >= 66 in the
4x4 so I'm afraid these lower bounds are not very useful...
-- Philippe Bizard <Philippe.Bizard@imag.fr>
In <dsavitt.760436329@unixg.ubc.ca>, dsavitt@unixg.ubc.ca writes:
> As far as I know (and I have not actually analyzed it) this puzzle
> has the neat property that if everything in the first few rows is in
> the right place, then everything falls into place in the end. Some
> parity argument or something like that can probably be made....
It's not as simple as that. This puzzle was invented by Sam Loyd, and
it was a huge success. The object was to start like this:
1 2 3 4 (A)
5 6 7 8
9 10 11 12
13 15 14
and slide the blocks so they ran like this:
1 2 3 4 (B)
5 6 7 8
9 10 11 12
13 14 15
Nobody succeeded, but thousands claimed to have! As you guess, there's
a parity argument to show it's impossible. Indeed, Loyd was unable to
patent the puzzle. The Patent Office insisted on a "working model,"
meaning he had to show how to solve it!
Anyway, this position has two inversions and so is attainable from
(B):
1 2 3 4 (C)
5 6 7 8
9 10 11 12
15 13 14
So it's wrong to assume that all the pieces at the end "fall into
place".
These puzzles are called "sliding block" (not "square") puzzles, since
many of them have nonsquare pieces. I perplexed many people at chess
meets in the 1970s with a homemade puzzle called the "Pig Puzzle". It
was really the old "Dad's Puzzle" redecorated. Of 9 pieces, only 3
were square.
-- Col. G. L. Sicherman <gls@hrcms.ATT.COM>, February 1994