Reve's puzzle is a variant on the famous Tower of Hanoi problem. The puzzle was first proposed in 1907 by Henry Dudeney in the book The Canterbury Puzzles. This variant is quite interesting because, unlike the Tower of Hanoi problem, there has been no absolute "best" solution to it, dictating the fewest number of moves.
The problem is as follows: a pilgrim is challenged by the reeve to move a stack of cheeses of varying sizes from the first of four stools to another stool without ever placing a cheese on one of smaller diameter. Also, only one piece of cheese can be moved from one peg to another at a given time. When the problem is broken down, it becomes clear that it has the same rules as the Tower of Hanoi problem, only with four pegs instead of three.
The most widely accepted solution to the Reve problem is the Frame-Stewart algorithm, although no proof exists that it is the best solution. Much like the solution to the Tower of Hanoi problem, the solution here is a recursive one. The Frame-Stewart algorithm for solving the Reve's puzzle is as follows.
The algorithm begins with the selection of an integer k, such that 1 =< k =< n, where n is the total number of discs. When there is only one disc, move it from peg 1 to peg 4 and stop. For n > 1, the algorithm proceeds recursively using the following three steps:
- Move the n - k smallest discs from peg 1 to peg 2 using all four pegs. There are many ways to do this; the best may be a slight modification of the Tower of Hanoi solution. Regardless, moving these pieces is very quick because of the extra peg one can use beyond the Tower of Hanoi solution; it should allow you to move the discs in 2^(n-k-1) time, if not better.
- Move the rest of the discs from peg 1 to peg 4, using pegs 1, 2, and 4 in the classic Tower of Hanoi solution. This takes 2^(k) time.
- Then, move the n - k smallest discs to peg 4, using all four pegs. This again takes 2^(n-k-1) time.
Adding the times up (2^(n-k-1) + 2^k + 2^(n-k-1)) gives time 2^(n-k) + 2^(k), which is significantly less than the 2^n time of the regular Tower solution. Selecting an optimal k, then, would give k = n/2, making the time in actuality 2^(n/2 + 1), which is an enormous savings for any large n.
The unsettled conjecture here is known as Frame's conjecture, which states that this algorithm uses the fewest number of moves to solve the puzzle. As of yet, this conjecture has yet to be proven.
Reve's puzzle is a mathematically interesting twist on the usual Tower of Hanoi problem used to demonstrate recursion, and it remains interesting because the optimal solution has yet to be definitively found.