Variations on the Four-Post Tower of Hanoi Puzzle

Abstract

The famous Tower of Hanoi puzzle, invented in 1883 by Edouard Lucas (see [21]), consists of three posts and a set of n, typically 8, pierced disks of differing diameters that can be stacked on the posts. The tower is formed initially by stacking the disks onto one post in decreasing order of size from bottom to top. The challenge is to transport the tower to another post by moving the disks one at a time from post to post, subject to the rule that no disk can ever be placed on top of a smaller disk. It is well known that 2 − 1 moves are necessary and sufficient to carry out this task. Many variations of this puzzle have been proposed, in which the set of allowable moves has been extended or restricted, the number of posts has changed, or some other aspect has been varied. In this paper we survey what is known and not known about those versions of the puzzle that use four posts, rather than three.