Chapter 3

GAME OVER

The words “Game Over” appeared on the screen in big, flashing characters. The man who wished to be called Mr. Smith but whose real name was Leonard Richter had been following the game on a monitor from his private study. Not that there had been much to follow. Unlike most of the other candidates who had battled until the very end trying to solve the puzzle, Jule had stopped playing after only a quarter of an hour, so the screen had displayed what looked like a frozen image of the board for the remaining forty-five minutes.

Richter had first feared a system failure, but the screen clock had continued to operate normally. A more likely explanation was that Jule had used the time trying to figure out some principle or strategy that would lead to the solution, instead of playing the game by trial and error in the hope of hitting on the winning configuration by some lucky combination of moves. If such was the case, he had obviously run out of time. Unless . . .

When Richter entered the big room, Jule swiveled round in his chair to face him. He was smiling as he said: “Congratulations, Mr. Smith. That was a very neat trick you pulled on me. I wonder how many candidates for whatever you have to offer fell into the trap.”

“Congratulations to you, Mr. Davidson.” Richter also smiled, seemingly very pleased by what he heard, and completely ignoring Jule’s sarcastic tone. “When did you find out that the puzzle had no solution?”

“Less than five minutes ago.”

“And may I ask how you did it?”

“It happened while I was trying to understand the puzzle in mathematical terms. I discovered that it was impossible to reach certain configurations of the board by making only the permissible moves, that is, by sliding blocks into the vacant square. At that point it occurred to me that the desired final configuration, with the numbers in sequential order, might be among these. After all, your little story about the game never mentioned anyone who had actually solved the puzzle, even after the cash prize was offered.”

“So you only suspect that the puzzle has no solution, but you don’t know that for sure, do you?” Richter had expected a reasoned explanation, not just an educated—and lucky—guess.

“Not at all. I am certain that there is no solution, and I can prove it mathematically.”

“I’d be glad to hear your proof, then.”

“Are you a mathematician?”

Richter hesitated before replying. “I have degrees in philosophy and literature, but I’ve always been fascinated by enigmas, mathematical or otherwise, and have studied them for many years. Most of the books you see here deal with the subject, in one form or another. As for this particular puzzle, I am familiar with one mathematical proof of the impossibility of solving it, so I’m pretty sure I shall be able to understand yours, Mr. Davidson.”

Jule reached for his notebook, which was lying on the table beside the computer monitor. He had been scribbling some notes but, with time running out, had not been able to check every link in the logical chain of his argument.

“The fundamental concept in play here is that of a permutation,” he began. “Every configuration of the board, when read from left to right, top to bottom, becomes a permutation of the sixteen numbers 1 to 16, that is, a list of these numbers in a particular order (the empty square may be considered as the number ‘16’). For instance, the initial configuration becomes 1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 16. The total number of such permutations is quite large, about 7 trillion.”

“Or exactly 16 factorial,” interrupted Richter, “that is, 16 times 15 times 14 times 13 and so forth, all the way down to 1. The reason for this being that there are sixteen choices for the first number in a permutation and, after it has been chosen, fifteen choices for the second, so there are 16 × 15 ways of choosing the first two numbers; 16 × 15 × 14 ways of selecting the first three, and so on, until the 16th position can only be filled with the remaining number. This gives a total of 16 × 15 × 14 × . . . × 2 × 1—‘16 factorial,’ in mathematical jargon—possible permutations of the sixteen numbers.”

“That’s right,” confirmed Jule, wondering whether the man he knew only as Mr. Smith was trying to show off.

“Put in the simplest terms, a solution of the puzzle consists in transforming the initial permutation into the final one by a succession of moves of a particular kind: sliding a block (left, right, up, or down) into the adjacent empty square. Both the initial and the final permutations end with ‘16’ (i.e., the empty square is in the lower right corner). Now, here is the first significant fact: To go from one permutation ending with ‘16’ to another of the same type requires an even number of moves.”

“And is that fact supposed to be obvious?” asked Richter.

“Not really, but I can easily convince you why it must be true. First notice that after each move the empty square itself ‘moves’ one square from its previous position on the board, either horizontally (left or right) or vertically (up or down), so that any series of moves causes the empty square to ‘travel’ around the board. Do you follow me?”

“Perfectly. Please go on.” Richter appeared impatient to hear the rest of the proof. Jule resumed his explanation. “Suppose that you start from the initial configuration S and, after making a certain number of moves, you reach the final configuration F. Since at the end of its ‘journey’ around the board the blank square comes back to its original position (the lower right corner), it must have moved as many times up the board—m times, say—as it did down the board, so it must have moved vertically an even number (2m) of times; similarly, it must have moved horizontally also an even number of times. Hence, the total number of moves that took you from S to F, being the sum of two even numbers, must itself be an even number. We have thus established fact number 1: Reaching the final configuration requires an even number of moves.” At this point Jule paused and began checking his notes.

Richter’s voice filled the momentary silence. “But that fact does not rule out the possibility of reaching the final configuration F, does it?”

Jule looked at him, slightly annoyed by the remark, and replied: “Of course it doesn’t, not fact number 1 by itself. But wait until I prove to you fact number 2: Reaching the final configuration requires an odd number of moves. Then, by putting the two facts together, we must conclude that the Fifteen Puzzle has no solution: for if the puzzle could be solved in n moves, say, this number n would be both even and odd, a number that doesn’t exist!”

“That would certainly clinch the argument,” Richter commented enthusiastically, “I’m eager to hear your proof of fact number 2.”

“And I shall be happy to oblige, but first I need a few minutes to review my notes, if you don’t mind.”

“Not at all. Take as much time as you need.” And, getting on his feet, he added, “If you would excuse me, I have some business to attend to. It won’t take long.”

While Jule turned his attention to his notes, Richter left the room and headed back to his study. He closed the door behind him, sat down at his desk, and reached for a telephone half buried under a pile of papers. The telephone at the other end of the line rang several times before the answering machine was activated: “We cannot take your call just now. Please leave a message.” After a short beep, the machine began recording Richter’s message: “Richter. I’ve got good news. I’ve found him. The team is now complete. Can you call me back this evening? Thank you.” And he hung up.

“We need to go back to permutations,” announced Jule to his audience of one. Richter was once again in the library room, sitting in a comfortable leather sofa, three-quarters of which was covered with books and sheets of paper.

“There are two sorts of permutations, even permutations and odd ones. Are you familiar with these concepts?”

“I’m afraid not,” admitted Richter.

“Then we shall start from the beginning. Any given permutation can be ‘unscrambled,’ that is, restored to the natural order, 1 2 3 4 5, etc., by performing a certain number of ‘exchanges.’ Here’s an example—we shall use six numbers instead of sixteen to make it simpler, but the principle is the same. You’ll need some paper to write on.” Richter picked up a blank sheet lying nearby and produced a fountain pen from one of his pockets.

“Please write ‘3 6 2 1 5 4.’ ” Richter did as requested, in small, blue numerals. “Now exchange 3 and 1 and write down the resulting permutation.” The permutation ‘1 6 2 3 5 4’ appeared on Richter’s sheet, one numeral at a time, below the previous list. He dutifully continued to record each new permutation that resulted from the exchange dictated by Jule. “Now exchange 2 and 6 (‘1 2 6 3 5 4’); 6 and 3 (1 2 3 6 5 4) and finally 6 and 4. You must now have arrived at 1 2 3 4 5 6, that is, the natural order.”

“I have indeed,” confirmed Richter, looking up from the sheet of paper.

“Notice that you needed four exchanges to unscramble the given permutation. Actually, there are many other sequences of exchanges that would achieve the unscrambling, but they all have something in common: the number of exchanges is always even—this is a well-known property of permutations that you can check out in any mathematics textbook on the subject. For this reason, we say that permutations such as 3 6 2 1 5 4 are even, while those requiring an odd number of exchanges to put them back in the natural order are said to be odd.”

Jule paused, as if inviting Richter to ask questions, but his host kept silent.

“Now, regarding our puzzle, the initial configuration of the board is an odd permutation, for exchanging 15 and 14 (i.e., a single exchange) restores the natural order. On the other hand, the desired final configuration is the natural order, so that it requires no exchanges at all (or, if you prefer, two ‘artificial’ exchanges: 1 and 2, say, and then 1 and 2 again). In other words, the final configuration is even.”

At this point Richter interrupted him, leaning forward, his voice filled with excitement: “I can now see what you’re getting at, Mr. Davidson, and it’s very clever. A permissible move of the game is actually an exchange: the number 16 (i.e., the empty square) and some other number (i.e., some other square) swap places. And so, after each single move, the new permutation on the board is odd if the previous one was even, and it is even if the previous one was odd. Therefore, to go from the initial configuration (odd) to the final one (even), if at all possible, must necessarily take an odd number of moves. That’s your fact number 2, and the proof is complete, because the number of moves made by a player who had solved the puzzle would be both even and odd, a number that doesn’t exist!”

Richter had leaped to his feet and joined Jule, who was still sitting at the computer desk. He put his right hand on Jule’s shoulder, looked at him directly in the eyes and said, with a solemn expression on his face: “I have a very exciting and lucrative proposition for you, Mr. Davidson. I do hope you will accept it.”

Only much later, curious about the history of the Fifteen Puzzle, did Jule learn the end of the story. It was obvious that Loyd had intentionally designed the puzzle so that it could not be solved. He had offered the $1,000 prize as an incentive for people to buy his game, well aware that he would never have to pay out the money. But despite the success of his invention, he never patented it in the United States. According to one source, in order to obtain a patent he had to submit a “working model.” But when the patent office official learned from Loyd that the puzzle had no solution, he told him that in such case there couldn’t be a working model, and without one, there could be no patent.