Sam Loyd's Fifteen
Until very recently it was a common belief that the Fifteen puzzle has been invented by Sam Loyd more than a hundred years ago. However, the scrupulous research conducted by Jerry Slocum and Dic Sonneveld revealed a sad truth: Sam Loyd deliberately took the puzzling community for a ride by starting to claim the authorship of the puzzle about 10 years after the puzzle made his mark on the world. It became an instantaneous success much like the Rubik's cube 100 years later. Some of its history is narrated elsewhere.
As probably every one knows, the purpose of the puzzle is to get the original ordering of the counters after they have been randomly reshuffled. The only allowed moves are sliding counters into the empty square. The puzzle's theory says that there are two groups of starting configurations. Configurations in the first could eventually be solved whereas configurations in the second are unsolvable. The difference between the two is that configurations in the former group can be obtained by acting backwards - starting with the target ordering and just randomly sliding the counters. Configurations of the unsolvable group are obtained when, in addition, two neighboring counters are physically lifted and their positions swapped. Pressing the Cheat button below does precisely this.
| What if applet does not run? |
I must note that the theory of the puzzle, as presented in the puzzle's history page, relates only to two configurations: the original one with all the counters in the right order and the one with the counters 14 and 15 interchanged. Below I present a version that encompasses all possible starting configurations. Just to remind, imagine the board cut into 4 rows of counters which are then placed successively one after another: first row, second row, etc. This procedure places counters in a certain order. Whenever a counter with a greater number on it precedes a counter with a smaller number, the counters are said to be inverted.
Proposition
For a given puzzle configuration, let N denote the sum of the total number of inversions and the row number of the empty square. Then (N mod 2) is invariant under any legal move. In other words, after a legal move an odd N remains odd whereas an even N remains even.
Proof
First of all, sliding a counter horizontally changes neither the total number of inversions nor the row number of the empty square. Therefore let's consider sliding a counter vertically.
Let's assume, for example, that the counter a is located directly over the empty square. Sliding it down changes the parity of the row number of the empty square. Now consider the total number of inversions. The move only affects relative positions of counters a, b, c, and d. If none of the b, c, d caused an inversion relative to a (i.e., all three are larger than a) then after sliding one gets three (an odd number) of additional inversions. If one of the three is smaller than a, then before the move b,c, and d contributed a single inversion (relative to a) whereas after the move they'll be contributing two inversions - a change of 1, also an odd number. Two additional cases obviously lead to the same result. Thus the change in the sum N is always even. This is precisely what we have set out to show.
A problem
Let's consider, say, Loyd's Eight (3×3) or Loyd's 24 (5×5) puzzles. Will the proposition above apply to either of them?
In the general framework of Graph Theory, R.Wilson gave a complete treatment of puzzles on graphs of which Fifteen is a particular case. Applied to the Fifteen puzzle we obtain the following
Theorem
Assume the board of (the generalized) "Fifteen" consists of nxm squares. The graph of the puzzle is always bipartite, and, therefore, puz(Fifteen) has two connected components, one consisting of odd and another of even permutations.
However, a variant of the puzzle seems to contradict the general theory.
Remark
If we allow the counters wrap around the puzzle in, say the vertical direction, we may look at the puzzle as played on the surface of a cylinder. And, similarly, we may imagine playing on a Moebius strip. Please verify, on the basis of Wilson's theorem, that on the Moebius strip the puzzle is always solvable, whereas on the cylinder it is always solvable for a puzzle with an odd number of rows (and, hence, columns.)
Eric Weisstein has noticed my misspelling of Sam Loyd's name. Originally I used double L in the last name. As Eric remarks, Sam Loyd himself used a single L spelling. In my defense, I do have a book which spells the name with double L. Encyclopedia Britannica and Martin Gardner, on the other hand, spell the name correctly. Thanks to Eric I finally got into a good company.
One of the first proofs of the theorem due to W. W. Johnson that appeared in 1879 can be found on a separate page.
Discussion of the problem
The argument, as it was presented for the original 4×4 puzzle, does not work for either 3×3 or 5×5 boards. The reason for the incorporation of the row number in the 4×4 puzzle is that when a counter is moved vertically it jumps over 3 (an odd number of) other counters. Thus the difference in the number of inversions before and after the move is always odd. Thus a move in a 4×4 puzzle does not preserve the parity as we count it. The addition of the row number fixes that problem. However, the problem does not arise at all for 3×3 and 5×5 puzzles because then a vertical move causes a jump over an even number of counters and, therefore, preserves the number of inversions.
Related material
| |
Sliders and Puzzles on Graphs | |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|Contact| |Front page| |Contents| |Games| |Eye opener| |Impossible|
Copyright © 1996-2018 Alexander Bogomolny
71533739