Variants of 'Towers of Hanoi'
Cyclic Hanoi is a variation of the Hanoi in which each disk must be moved in the same cyclic direction, in most cases, clockwise. For example, given a standard three peg set-up, a given disk can be moved from peg A to peg B, then from B to C, C to A, etc. This can be solved using two mutually recursive procedures:
To move n discs clockwise from peg A to peg C:
- move n - 1 discs clockwise from A to C
- move disc #n from A to B
- move n - 1 discs counterclockwise from C to A
- move disc #n from B to C
- move n - 1 discs clockwise from A to C
To move n discs counterclockwise from peg A to peg C:
- move n - 1 discs clockwise from A to B
- move disc #n from A to C
- move n - 1 discs clockwise from B to C
Four pegs and beyond
Although the three-peg version has a simple recursive solution as outlined above, the optimal solution for the Tower of Hanoi problem with four pegs (called Reve's puzzle), let alone more pegs, is still an open problem. This is a good example of how a simple, solvable problem can be made dramatically more difficult by slightly loosening one of the problem constraints.
The fact that the problem with four or more pegs is an open problem does not imply that no algorithm exists for finding (all of) the optimal solutions. Simply represent the game by an undirected graph, the nodes being distributions of disks and the edges being moves and use breadth first search to find one (or all) shortest path(s) moving a tower from one peg onto another one. However, even smartly implemented on the fastest computer now available, this algorithm provides no way of effectively computing solutions for large numbers of disks; the program would require more time and memory than available. Hence, even having an algorithm, it remains unknown how many moves an optimal solution requires and how many optimal solutions exist for 1000 disks and 10 pegs.
Though it is not known exactly how many moves must be made, there are some asymptotic results. There is also a "presumed-optimal solution" given by the Frame-Stewart algorithm, discovered independently by Frame and Stewart in 1941. The related open Frame-Stewart conjecture claims that the Frame-Stewart algorithm always gives an optimal solution. The optimality of the Frame-Stewart algorithm has been computationally verified for 4 pegs with up to 30 disks.
For other variants of the four-peg Tower of Hanoi problem, see Paul Stockmeyer's survey paper.
Multistack Towers of Hanoi
U.S. patent number 7,566,057 issued to Victor Mascolo discloses multistack Tower of Hanoi puzzles with two or more stacks and twice as many pegs as stacks. After beginning on a particular peg, each stack displaces and is displaced by a different colored stack on another peg when the puzzle is solved. Disks of one color also have another peg that excludes all other colors, so that there are three pegs available for each color disk, two that are shared with other colors, and one that is not shared. On the shared pegs, a disk may not be placed on a different colored disk of the same size, a possibility that does not arise in the standard puzzle.
The simplest multistack game, Tower of Hanoi (2 x 4), has two stacks and four pegs, and it requires 3[T(n)] moves to solve where T(n) is the number of moves needed to solve a single stack classic of n disks. The game proceeds in seesaw fashion with longer and longer series of moves that alternate between colors. It concludes in reverse seesaw fashion with shorter and shorter such series of moves. Starting with the second series of three moves, these alternate series of moves double in length for the first half of the game, and the lengths are halved as the game concludes. The solution involves nesting an algorithm suitable for Tower of Hanoi into an algorithm that indicates when to switch between colors. When there are k stacks of n disks apiece in a game, and k > 2, it requires k[T(n)] + T(n - 1) + 1 moves to relocate them.
The addition of a centrally located universal peg open to disks from all stacks converts these multistack Tower of Hanoi puzzles to multistack Reve's puzzles as described in the preceding section. In these games each stack may move among four pegs, the same combination of three in the 2 x 4 game plus the central universal peg. The simplest game of this kind (2 x 5) has two stacks and five pegs. A solution conjectured to be optimal interlocks the optimal solution of the 2 x 4 puzzle with the presumed optimal solution to Reve's puzzle. It takes R(n) + 2R(n - 1) + 2 moves, where R(n) is the number of moves in the presumed optimal Reve's solution for a stack of n disks.