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 [2].

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 [2]). 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.

[1] H. E. Dudeney,

*The Canterbury Puzzles*, Mineola, New York: Dover Publications, 2002.

[2] K. H. Rosen,

*Discrete Mathematics and Its Applications*, 5th ed., Boston: McGraw-Hill, 2003.