The Reve's Puzzle
Requires a Wolfram Notebook System
Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.
This is the classic Reve's puzzle as presented in . Initially, the Reve placed eight pieces of cheese of graduating sizes on one of four stools. The Reve challenged his fellow pilgrims to move them all to another stool by moving them one at a time, without ever putting a larger cheese on top of a smaller, and in the least number of moves possible. After completing that task, the pilgrim was expected to move nine cheeses, then ten, and so on, until 21 cheeses were finally moved from the starting stool to another stool, in the least number of moves possible. Once a pilgrim was successful, the Reve promised to give him "a draught of the best that our good host can provide". This Demonstration shows the moves that make it possible to win a draught of the host's finest from the Reve.
Contributed by: Samuel E. Rhoads (September 2012)
Open content licensed under CC BY-NC-SA
Snapshot 1: it takes five moves to move three cheeses
Snapshot 2: it takes 49 moves to move 10 of 15 cheeses
Snapshot 3: the position after move number 227 with 21 cheeses
It is an unsolved problem in mathematics and computer science to determine the minimum number of moves for all . For small , however, the minimum number of moves is known, and the well-known Frame–Stewart algorithm lists the moves to use. Simply stated, the algorithm says: "In order to move cheeses to a destination stool, first determine a value for , and then use all four stools to move cheeses to one of the stools (think of that stool as a "spare stool"), then use the remaining three stools—as in the Towers of Hanoi puzzle—to move cheeses to the destination stool, and then use all four stools once again to move the cheeses from the spare stool to the destination stool". See a discussion of the Frame–Stewart algorithm in .
It is important that the reader understand that this algorithm is recursive! Suppose that there are 15 pieces of cheese. In that case, let . So the algorithm says that you first need to use all four stools to move 10 cheeses. But to do that, you need to determine a for . That is 4; so you first need to use all four stools to move six cheeses to a spare stool. When , , so in order to move those six, you first need to move three. No recursion is needed to move three cheeses, so the first three can be moved to a spare stool (with five moves). Then you need to move three cheeses, using the three stools that are available, using the Towers of Hanoi algorithm (that will require seven moves). And then you need to move the three cheeses from the spare stool. Now that you have moved six cheeses, you can move four, and after that you can move the six cheeses from the spare stool. All that describes how to move just the first 10 cheeses; now you need to move five; and then 10. I trust you get the idea. See Snapshot 2.
In the Frame–Stewart algorithm, the value of is determined by a fairly simple rule (see ). For example, if , . However, it turns out that for most values of there are two possible choices for . When , for example, can be chosen to be either 4 or 5. To make this Demonstration more interesting, a random number generator is used to select the value for whenever there are two possible values. This Demonstration also randomly decides which stool to use as the "spare stool". Finally, even though the Reve indicated that the cheeses were to end up on the stool "at the other end", this Demonstration chooses the final destination stool randomly as well.
In the Towers of Hanoi puzzle, the required number of moves is much greater than in the Reve's Puzzle. To move 21 discs in the Towers of Hanoi puzzle requires (2,097,151) moves. As you can see from Snapshot 3, "only" 321 moves are required to move 21 pieces of cheese in the Reve's Puzzle.
There are two sliders. The first slider is used to choose the number of cheeses, from one to 21 (even though the Reve had the pilgrims start with eight pieces of cheese, this Demonstration shows how to move just one to seven pieces as well). The second slider is used to move the pieces.
 H. E. Dudeney, The Canterbury Puzzles, Mineola, New York: Dover Publications, 2002.
 K. H. Rosen, Discrete Mathematics and Its Applications, 5th ed., Boston: McGraw-Hill, 2003.