Sam Loyd's Fifteen

This puzzle was invented by Sam Loyd more than a hundred years ago. 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, is flawed. Below I present a corrected version.

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 consider sliding a counter vertically.

Let assume, for example, that the counter a is located directly over the empty square. Sliding it down changes the evenness 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 a 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 to show.

A problem

Let's consider, say, Loyd's Eight (3x3) or Loyd's 24 (5x5) puzzles. Will the proposition above apply to any 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.

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.

Copyright © 1996-1998 Alexander Bogomolny