Sam Loyd's Fifteen

"The well known tray with 15 numbered square counters has a curious history few people even suspect of. We'll recall it in the words of W. Arens, a German, mathematician and investigator:"

"About half a century ago, in the late 1870's, the Fifteen Puzzle bobbed up in the United States; it spread quickly and owing to the uncountable number of devoted players it had conquered, it became a plague.

"The same was observed on this side of the ocean, in Europe. Here you could even see the passengers in horse trams with the game in their hands. In offices an shops bosses were horrified by their employees being completely absorbed by the game during office and class hours. Owners of entertainment establishments were quick to latch onto the rage and organized large contests. The game had even made its way into solemn halls of the German Reichstag. 'I can still visualize quite clearly the greyhaired people in the Reichstag intent on a square small box in their hands,' recalls the geographer and mathematician Sigmund Gunter who was a deputy during puzzle epidemic.

"In Paris the puzzle flourished in the open air, in the boulevards, and proliferated speedily from the capital all aver the provinces. A French author of the day wrote, 'There was hardly one country cottage where this spider hadn't made its nest lying in wait for a victim to flounder in its web.

"In 1880 the puzzle fever seems to have reached its climax. But soon the tyrant was overthrown and defeated by the weapon of Mathematics. The mathematical theory of the puzzle showed that of the many problems that might be offered only a half were solvable, the other half were impossible, however ingenious the technique that applied to solve them.

"It thus became clear why some problems would not yield under any conditions and why the organizers of the contests had dared offer such enormous rewards for solving problems. The inventor of the puzzle took the cake in this respect suggesting to the editor of a New York newspaper that he publish an unsolvable problem in the Sunday edition with a reward of $1,000 for its solution. The editor was a little reluctant so the inventor expressed his willingness to pay his own money. The inventor was Sam Loyd. He came to be widely known as an author of amusing problems and a multitude of puzzles. Curiously enough, he failed to patent his Fifteen Puzzle in the USA. According to the regulations, he had to submit a 'working model' so that a prototype batch could be manufactured from it. He posed the problem to a Patent Office official, but when the latter inquired if it were solvable, the answer was 'No, it's mathematically impossible'. The official therefore reasoned: 'In which case there can't be a working model and without a working model there can be no patent.' Loyd was satisfied with the decision. He would perhaps have been more persistent had he foreseen the unprecedented success of his invention."

"We'll continue the story of the puzzle using the inventor's own words:

"The old dwellers of the realm of aptitude will remember how in the early 1870s I made the whole world rack its brain over a tray of movable counters, that came to be known as the Fifteen puzzle. The fifteen counters were arranged in order in the tray with only 14 and 15 counters inverted. The puzzle was to get the counters into the normal arrangement by individually sliding them so that the 14 and 15 were permuted.

"The $1000 reward offered for the first correct solution remained unretrieved although everybody was busy on it. Funny stories were told of shop-keepers who forget for this reason to open their shops, of respectful officials who stood throughout the night under a street lamp seeking a way to solve it. Nobody wanted to give up as everyone was confident of imminent success. It was said that navigators allowed their ships to run aground, engine drivers took their trains past stations, and farmers neglected their ploughs."

* * *

"We'll now introduce the reader to the beginnings of the game. In its complete form it's very complicated and closely related to one of the branches of higher algebra (the theory of determinants). We'll just confine our discussion to some of the elements as presented by W. Arens.

"The task of the game is normally as follows: using successive movements made possible by the presence of the blank space the arbitrarily arranged squares should be brought to the normal arrangement, i.e. the counters are in numerical order with the 1 in the upper left corner, followed by the 2 on the right, then the 3 and the 4 in the upper right corner; in the next row there should be from left to right the 5, 6, 7, 8, etc., with the blank space ending up back in the lower right corner.

"Now think of an arrangement with 15 counters scattered arbitrarily. A number of movements can always bring the 1 to the place occupied by it originally. In exactly the same way we can, without touching the counter 1 move the counter 2 to the adjacent place on the right. Next, without touching either the 1 or 2, we can move the 3 and 4 to their normal places. If these occasionally are not in the two last columns, we can bring them there and through a number of movements achieve the arrangement sought. Now the upper line is in the normal order and we'll leave it as it is in the later manipulations. In the same way we'll also bring the second line in the normal order. We'll easily find that it's always possible. Further, within the space of the two last lines we'll need to arrange the counters 9 and 13, which is always possible, too. It now only remains to arrange a small patch of six spaces, of which one is free and the other five are occupied by the 10, 11, 12, 14 and 15, arbitrarily arranged. Within this patch we can always bring 10, 11, and 12 into the normal arrangement. This done, the 14 and 15 will be arranged in the last line either in the normal or inverted order. This procedure, which the reader can easily test in practice, will always yield the following result.

"Any initial arrangement can either brought into the normal order (I) or the otherwise normal order with the counters 14 and 15 inverted (II).

"If an arrangement, we'll denote it by S, can be brought to I, then the opposite is clearly possible, i.e. I can be brought to S. After all, the movements are all reversible. If, for instance we can push the 12 in arrangement into the blank space, then we can always restore the previous arrangement by the reverse move.

"We thus have two series of arrangements such that the arrangements in one series can be brought to the normal arrangement I, and those in the other series can be brought to the arrangement II. Conversely, from the normal arrangement we can obtain any arrangement in the first series, and from II any arrangement in the second series. Lastly, any two arrangements in the same series are transferable one to the other.

"Could be go further and combine the two arrangements? We could rigorously prove (we are not going to here) that these arrangements cannot be interchanged, however many moves are used. Therefore, the formidable variety of arrangements break down into two separate series: (1) those that could be brought into the normal arrangement I, and (2) those that can't and it was for these arrangements that the enormous rewards were promised.

"How are we to know whether or not a given arrangement belongs to the first series? An example will clarify this.

"Let's consider the arrangement on the right. The first line is in perfect order, as is the second save for the last counter(9). Counter 9 comes before 8. This sort of violation of the order is called inversion. Concerning the counter 9 we'll say that there is one inversion. Further examination reveals that 14 precedes three counters (12, 13, and 11), thus giving three inversions (14 before 12, 14 before 13, and 14 before 11). This amounts to 1+3=4 inversions. Further, the 12 precedes 11 and the 13 precedes the 11. This adds to more inversions bringing the total to 6. This procedure is used to determine the total number of inversions for any arrangement with the blank space in the lower right corner. If, as in the case in hand, the total number of inversions is even, then the arrangement can be brought to the normal one; in other words, it's solvable. If the number of inversions is odd, the arrangement belongs to the second series, i.e. it is an insolvable arrangement.

"Thanks to the new light shed on the puzzle by Mathematics the earlier morbid passion that was shown for the game is now unthinkable. Mathematics has produced an exhaustive explanation of the game, one that leaves no loophole. The outcome of the game is dependent not on chance nor on aptitude, as in other games, but on purely mathematical factors that predetermine it unconditionally."