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.
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.
