Tower of Hanoi

Cognitive Psychology: Attention · Decision making · Learning · Judgement · Memory · Motivation · Perception · Reasoning · Thinking - Cognitive processes Cognition - Outline Index

File:Hanoiklein.jpg

A model set of the Towers of Hanoi

The Tower of Hanoi or Towers of Hanoi is a mathematical game or puzzle. It consists of three pegs, and a number of discs of different sizes which can slide onto any peg. The puzzle starts with the discs neatly stacked in order of size on one peg, smallest at the top, thus making a conical shape.

The objective of the game is to move the entire stack to another peg, obeying the following rules:

only one disc may be moved at a time
no disc may be placed on top of a smaller disc

Origins

File:Cot co.jpg

Flag Tower of Hanoi

The puzzle was invented by the French mathematician Edouard Lucas in 1883. There is a legend about an Indian temple which contains a large room with three time-worn posts in it surrounded by 64 golden discs. The priests of Brahma, acting out the command of an ancient prophecy, have been moving these discs, in accordance with the rules of the puzzle. According to the legend, when the last move of the puzzle is completed, the world will end. The puzzle is therefore also known as the Tower of Brahma puzzle. It is not clear whether Lucas invented this legend or was inspired by it.

If the legend were true, and if the priests were able to move discs at a rate of 1 per second, using the smallest number of moves, it would take them 2⁶⁴ − 1 seconds or roughly 585 billion years.^[1] The universe is currently about 13.7 billion years old.

There are many variations on this legend. For instance, in some tellings, the temple is a monastery and the priests are monks. The temple or monastery may be said to be in different parts of the world - including Hanoi, Vietnam, and may be associated with any religion. In some versions, other elements are introduced, such as the fact that the tower was created at the beginning of the world, or that the priests or monks may make only one move per day.

The Flag Tower of Hanoi physically resembles an oversized version of the puzzle with a single post and three stacked disks, and may have served as the inspiration for the name.

Solution

Most toy versions of the puzzle have 8 discs. The game seems impossible to many novices, yet is solvable with a simple algorithm:

Recursive algorithm

label the pegs A, B, C -- these labels may move at different steps
let n be the total number of discs
number the discs from 1 (smallest, topmost) to n (largest, bottommost)

To move n discs from peg A to peg B:

move n−1 discs from A to C. This leaves disc #n alone on peg A
move disc #n from A to B
move n−1 discs from C to B so they sit on disc #n

The above is a recursive algorithm: to carry out steps 1 and 3, apply the same algorithm again for n−1. The entire procedure is a finite number of steps, since at some point the algorithm will be required for n = 1. This step, moving a single disc from peg A to peg B, is trivial.

The Tower of Hanoi is a problem often used to teach beginning programming, in particular as an example of a simple recursive algorithm. It is also an example of an exponential time algorithm — for all but the smallest number of discs, it will take an impractically huge amount of time, even on the fastest computers in the world. There is no way to improve on this, because the minimum number of moves required to solve the puzzle is exponential in the number of discs.

Using recurrence relations, we can compute the exact number of moves that this solution requires, which is $2^n-1$ , where $n$ is the number of discs. This result is obtained by noting that steps 1 and 3 take $T_{n-1}$ time and step 2 takes constant time, giving $T_{n}=2T_{n-1}+1$ .

A simple and elegant implementation in Haskell (a functional programming language) is as follows:

hanoi n = hanoi' n 1 2 3
hanoi' 0 _ _ _ = []
hanoi' n f i t = (hanoi' (n-1) f t i) ++ (f, t) : (hanoi' (n-1) i f t)

where n is the number of discs; this program returns a list of all the moves required.

Here is an mirrored implementation in SML programming language:

fun hanoi (0,_,_,_) = [] | 
hanoi (n,l,c,r) = 
  hanoi(n-1,l,r,c) @ (l,c)::hanoi(n-1,r,c,l);

Explanation of the algorithm

A more human-readable version of the same algorithm follows:

move disc 1 to peg B
move disc 2 to peg C
move disc 1 from B to C, so it sits on 2

You now have 2 discs stacked correctly on peg C, peg B is empty again

move disc 3 to peg B
repeat the first 3 steps above to move 1 & 2 to sit on top of 3

Each time you re-build the tower from disc i up to 1, move disc i+1 from peg A, the starting stack, and move the working tower again.

Therefore, We can observe and say that number of moves required to move n number of plates will be $2^n-1$ .

Binary solutions

Disc positions may be determined more directly from the binary (base 2) representation of the move number (the initial state being move #0, with all digits 0, and the final state being #2ⁿ−1, with all digits 1), using the following rules:

There is one binary digit (bit) for each disc
The most significant (leftmost) bit represents the largest disc. A value of 0 indicates that the largest disc is on the initial peg, while a 1 indicates that it's on the final peg.
The bitstring is read from left to right, and each bit can be used to determine the location of the corresponding disc.
A bit with the same value as the previous one means that the corresponding disc is stacked on top the previous disc on the same peg.
- (That is to say: a straight sequence of 1's or 0's means that the corresponding discs are all on the same peg).
A bit with a different value to the previous one means that the corresponding disc is one position to the left or right of the previous one. Whether it is left or right is determined by this rule:
- Assume that the initial peg is on the left and the final peg is on the right.
- Also assume "wrapping" - so the right peg counts as one peg "left" of the left peg, and vice versa.
- Let n be the number of greater disks that are located on the same peg as their first greater disk and add 1 if the largest disk is on the left peg. If n is even, the disk is located one peg to the left, if n is odd, the disk located one peg to the right.

For example, in an 8-disc Hanoi:

Move #0 (00000000)
- The largest disc is 0, so it is on the left (initial) peg.
- All other discs are 0 as well, so they are stacked on top of it. Hence all discs are on the initial peg.
Move #255 (11111111)
- The largest disc is 1, so it is on the right (final) peg.
- All other discs are 1 as well, so they are stacked on top of it. Hence all discs are on the final peg and the puzzle is complete.
Move #216 (11011000)
- The largest disc is 1, so it is on the right (final) peg.
- Disc two is also 1, so it is stacked on top of it, on the right peg.
- Disc three is 0, so it is on another peg. Since n is odd, it is one peg to the right, i.e. on the middle peg.
- Disc four is 1, so it is on another peg. Since n is still odd, it is one peg to the right, i.e. on the right peg.
- Disc five is also 1, so it is stacked on top of it, on the right peg.
- Disc six is 0, so it is on another peg. Since n is even, the disk is one peg to the left, i.e. on the middle peg.
- Discs seven and eight are also 0, so they are stacked on top of it, on the middle peg.

One could thus easily compute the positions of discs in a set of eighty discs after some mole of advancements, if the margin were but large enough to contain it. Using slightly more than the margin, the above algorithm can be coded in Scheme as follows:

(define (conf m h f t) ; m=move number, h=height of tower, f=starting peg, t=destination peg
 ; express the height in the number of disks and identify the pegs by the numbers 0, 1 and 2.
 (let loop ((prev-zero? #t) (mask (arithmetic-shift 1 (sub1 h))) (rotation (- t f)) (f f))
  (if (zero? mask) ()
   (let ((zero-bit? (zero? (bitwise-and mask m))) (mask (arithmetic-shift mask -1)))
    (if (eq? prev-zero? zero-bit?) (cons f (loop zero-bit? mask (- rotation) f))
     (let ((f (modulo (+ f rotation) 3)))
      (cons f (loop zero-bit? mask rotation f))))))))

; This procedure produces a list of the positions of the disks in order of decreasing size.
; Assuming Avagadro's number to be exactly 6022x10²⁰ and omitting spaces in the result:

(conf #e6022e20 80 0 2) ; in less than a milisecond on a plain 1.8 GHz personal computer:
;--> (01111111100001201201221111201112012000000210211112002102200222222222222222222222)

The source and destination pegs for the nth move can also be found elegantly from the binary representation of n using bitwise operations. To use the syntax of the C programming language, the nth move is from peg (n&n-1)%3 to peg ((n|n-1)+1)%3, where the discs begin on peg 0 and finish on peg 1 or 2 according as whether the number of discs is even or odd. Furthermore the disk to be moved is determined by the number of times the movecount can be divided by 2 (i.e. the number of zero bits at the right), counting the first move as 1 and identifying the disks by the numbers 0, 1, 2 etc in order of increasing size. This permits a very fast nonrecursive computer implementation of the solution. It also allows a move and the resulting distribution of disks to be computed without reference to any previous move or distribution of disks:

; h : total number of disks
; m : move counter, starting with 1 for the first move.
; f : starting peg; the pegs are identified by the numbers 0, 1 and 2.
; t : destination peg
; d : disk (numbered 0, 1, 2, etc in order of increasing size)
; Function =quotient= takes two integer numbers and computes their quotient rounded to integer towards zero.
; (rot3 m) : sense of rotation of the remaining third peg during move m.
; (rotd d) : sense of rotation of disk d.
; mcnt : number of moves disk d has made after a total of m moves.
; from : the peg a disk is taken from during move m.
; onto : the peg a disk is put onto during move m.
; thrd : the remaining third peg. (- 3 from onto)
; posi : position of disk d after a total of m moves.

(define (exp2 n        ) (expt   2 n))
(define (mod2 n        ) (modulo n 2))
(define (mod3 n        ) (modulo n 3))
(define (pari n        ) (add1 (mod2 (add1 n))))
(define (rotd h   d f t) (mod3 (* (- t f) (pari (- h d)))))
(define (rot3 h     f t) (rotd h 0 f t))
(define (mcnt m   d    ) (quotient (+ m (exp2 d)) (exp2 (add1 d))))
(define (thrd m h   f t) (mod3 (- f (* m (rot3 h f t)))))
(define (onto m h   f t) (mod3 (- (thrd m h f t) (rotd h (disk m) f t))))
(define (from m h   f t) (mod3 (+ (thrd m h f t) (rotd h (disk m) f t))))
(define (posi m h d f t) (mod3 (+ f (* (rotd h d f t) (mcnt m d)))))

(define 2log (let ((log2 (log 2))) (lambda (z) (/ (log z) log2))))
(define (disk m) (sub1 (inexact->exact (round (2log (add1 (bitwise-xor m (sub1 m))))))))
; This requires that the inexact function 2log is always within one half of the exact value.
; If this condition is not met, the following definition should be used:
; (define (disk m) (if (odd? m) 0 (add1 (disk (quotient m 2)))))         ; for m ≠ 0 or
; (define (disk m) (if (odd? m) 0 (add1 (disk (arithmetic-shift m -1))))) ; for m ≠ 0
; No, Scheme does not have a primitive function like bit-count (which would be nice for function =disk=)

Gray code solution

The binary numeral system of Gray codes gives an alternative way of solving the puzzle. In the Gray system, numbers are expressed in a binary combination of 0s and 1s, but rather than being a standard positional numeral system, Gray code operates on the premise that each value differs from its predecessor by only one (and exactly one) bit changed. The number of bits present in Gray code is important, and leading zeros are not optional, unlike in positional systems.

If one counts in Gray code of a bit size equal to the number of discs in a particular Tower of Hanoi, begins at zero, and counts up, then the bit changed each move corresponds to the disc to move, where the least-significant-bit is the smallest disc and the most-significant-bit is the largest.

Counting moves from 1 and identifying the disks by numbers starting from 0 in order of increasing size, the ordinal of the disk to be moved during move m is the number of times m can be divided by 2. This is a property of binary gray codes.

This technique tells you which disc to move, but not where to move it to. Luckily, there is a rule which does say to do so. Simply, a disc should never be placed on another disc of the same parity (i.e. even discs should not be placed on even discs, nor odd on odd). If this rule is followed there should never be any ambiguity with where to place the disc. [1]

Long solutions

A modification of the game can be to move the tower from one peg to another peg using as many moves as possible without ever producing the same distribution of disks more than once. A simple algorithm (written in Scheme) is:

(define (long-move-tower height from-peg onto-peg thrd-peg)
 (if (positive? height)
  (let ((height-1 (sub1 height)))
   (long-move-tower height-1 from-peg onto-peg thrd-peg)
   (move-disk       height-1 from-peg thrd-peg onto-peg)
   (long-move-tower height-1 onto-peg from-peg thrd-peg)
   (move-disk       height-1 thrd-peg onto-peg from-peg)
   (long-move-tower height-1 from-peg onto-peg thrd-peg))))

Where procedure (move-disk d f t r) moves disk d from peg f onto peg t, ignoring peg r. The number of moves of this uniquely defined solution is 3^height-1 and all 3^height different distributions of disks are traversed (when including the starting distribution). This is called a Hamilton path. For this solution the disk to be moved can be found with a ternary gray code in a similar way as explained for the shortest solution, which is uniquely defined too. These statements are easily proven by mathematical induction.

Another modification is to move a tower from a peg back to the same peg while traversing all distributions of disks. (circular Hamilton path) There are exactly two solutions, but they mirror each other in the sense that there is in fact one path that can be traversed in both directions. Obviously, the length of the path is 3^height. A simple algorithm for the circular Hamilton path is:

(define (circular-hamilton-move-tower h a b c) ; h=height. a, b and c are the three pegs.
 (if (positive? h) ; start with a tower at peg a, move tower to peg b, then to peg c and finally return to peg a.
  (let ((h-1 (sub1 h)))
   (hamilton-start  h-1 a c b)
   (move-disk       h-1 a b c)
   (long-move-tower h-1 c a b)
   (move-disk       h-1 b c a)
   (long-move-tower h-1 a b c)
   (move-disk       h-1 c a b)
   (hamilton-finish h-1 b a c))))

(define (hamilton-start h a b c)
 (if (positive? h)
  (let ((h-1 (sub1 h)))
   (hamilton-start  h-1 a c b)
   (move-disk       h-1 a b c)
   (long-move-tower h-1 c b a))))

(define (hamilton-finish h a b c)
 (if (positive? h)
  (let ((h-1 (sub1 h)))
   (long-move-tower h-1 a c b)
   (move-disk       h-1 a b c)
   (hamilton-finish h-1 c b a))))

Graphical representation

The game can be represented by an undirected graph, the nodes representing distributions of disks and the branches representing moves. For one disk, the graph is a triangle:

 /\
/__\

For h+1 disks, take the graph of h disks and replace each small triangle by:

    /\
   /__\
  /    \
 /\    /\
/__\__/__\

The above graph is for 2 disks. The angular points of the outermost triangle represent distributions with all disks on the same peg. For 3 disks the graph is:

          ccc /\ ccc     ; call the pegs a, b and c
         acc /__\ bcc    ; list disk positions from left to right in order of increasing size
        abc /    \ bac
           /\    /\
      bbc /__\__/__\ aac
     bba / cbc  cac \ aab
        /\          /\
   cba /__\aba  bab/__\ cab
  caa /    \      /    \ cbb
     /\    /\    /\    /\
aaa /__\__/__\__/__\__/__\ bbb
      baa   cca   acb abb
         bca   ccb

Each side of the outermost triangle represent the shortest ways of moving a tower from one peg to another one. The branch in the middle of the sides of the largest triangle represents a move of the largest disk. The branch in the middle of the sides of each next smaller triangle represents a move of each next smaller disk. The sides of the smallest triangles represent moves of the smallest disk.

The longest non repetive way for three disks can be visualized by erasing the unused branches:

          /\
         /  \
        /    \
        \    /
      ___\  /___
     /          \
    /            \
   /___        ___\
       \      /    
 /\     \    /     /\
/  \_____\  /_____/  \

The circular hamilton path for three disks is:

          /\
         /  \
        /    \
        \    /
      ___\  /___
     /          \
     \          / 
   ___\        /___
  /                \
 /     /\    /\     \ 
/_____/  \__/  \__ __\

The graphs clearly show that:

From every arbitrary distribution of disks, there is exactly one shortest way to move all disks onto one of the three pegs.
Between every pair of arbitary distributions of disks there are one or two different shortest paths.
From every arbitrary distribution of disks, there is exactly one longest non selfcrossing path to move all disks to one of the three pegs.
Between every pair of arbitary distributions of disks there are one or two different longest non selfcrossing paths.
Let N_h be the number of non selfcrossing paths for moving a tower of h disks from one peg to another one. Then:
- N₁=2
- N_h+1=(N_h)²+(N_h)³.
- For example: N₈≈1.5456x10⁷⁹⁵

Applications

The Tower of Hanoi is frequently used in psychological research on problem solving. There also exists a variant of this task called Tower of London for neuropsychological diagnosis and treatment of executive functions.

The Tower of Hanoi is also used as Backup rotation scheme when performing computer data Backups where multiple tapes/media are involved.

As mentioned above, the Tower of Hanoi is popular for teaching recursive algorithms to beginning programming students. A pictorial version of this puzzle is programmed into the emacs editor, accessed by typing M-x hanoi. There is also a sample algorithm written in Prolog.

The Tower of Hanoi is also used as a memory test by neuropsychologists trying to evaluate amnesia.

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 or 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 optiomal solutions. Simply represent the game by an undirected graph, the nodes being distributions of disks and the edges being moves (of length 1) and use Dijkstra's algorithm to find one (or all) shortest paths moving a tower from one peg onto another one. However, even smartly implemented on the fasted 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" that can be recursively applied to find a solution - see Paul Stockmeyer's survey paper for an explanation and some variants of the four-peg problem.

Although it agrees with computer experiments for small numbers of discs, there is not yet a general proof that this presumed-optimal solution is in fact optimal. However, results in 2004 showed that the presumed-optimal solution must be of the same order of magnitude as the optimal solution.

Description of the presumed-optimal solution

The problem for four pegs is sometimes called "Reve's puzzle". A solution for four (or more) pegs, which has not been proved to be optimal, is described below:

Let $n$ be the number of discs.
Let $r$ be the number of pegs.
Define $T(n,r)$ to be the number of moves required to transfer n discs using r pegs

The algorithm can be described recursively:

For some $k$ , $1 \leq k < n$ , transfer the top $k$ discs to a single other peg, taking $T(k,r)$ moves.
Without disturbing the peg that now contains the top $k$ discs, transfer the remaining $n-k$ discs to the destination peg, using only the remaining $r-1$ pegs, taking $T(n-k,r-1)$ moves.
Finally, transfer the top $k$ discs to the destination peg, taking $T(k,r)$ moves.

The entire process takes $2T(k,r)+T(n-k,r-1)$ moves. Therefore, we should pick $k$ for which this quantity is minimum.
This algorithm (with the above choice for $k$ ) is presumed to be optimal, and no counterexamples are known.

In popular culture

In the classic science fiction story Now Inhale, by Eric Frank Russell (Astounding Science Fiction April 1959, and in various anthologies), the human hero is a prisoner on a planet where the local custom is to make the prisoner play a game until it is won or lost, and then execution is immediate. The hero is told the game can be one of his own species', as long as it can be played in his cell with simple equipment strictly according to rules which are written down before play and cannot change after play starts, and it has a finite endpoint. The game and execution are televised planet-wide, and watching the desperate prisoner try to spin the game out as long as possible is very popular entertainment; the record is sixteen days. The hero knows a rescue ship might take a year or more to arrive, so chooses to play Towers of Hanoi with 64 discs until rescue arrives. When the locals realize they've been had, they are angry, but under their own rules there is nothing they can do about it. They do change the rules, which will apply to any future prisoners. This story makes reference to the legend about the Buddhist monks playing the game until the end of the world, and refers to the game as arkymalarky. (The slang term "malarky", meaning nonsense, pre-dates this story by at least 30 years. [2])

In the Doctor Who serial "The Celestial Toymaker", the Toymaker challenges the Doctor to complete the "Trilogic Game" (eight disc Hanoi) in exactly 1,023 (2¹⁰ − 1) moves. Apparently, both the Doctor and the Toymaker were unaware of the algorithm above.

There is a band named Towers of Hanoi.

In video games

The puzzle is featured regularly in adventure and puzzle games. Since it is easy to implement, and easily-recognised, it is well-suited to use as a puzzle in a larger graphical game. Some implementations use straight discs, but others disguise the puzzle in some other form. What follows is a partial list of games which use the puzzle:

Black & White
The Island of Dr. Brain
The Secret Island of Dr. Quandary
Star Wars: Knights of the Old Republic
Zork Zero

Notes

↑ 1000 Play Thinks

External links

Online Demonstration

History

Algorithm

Theory, recursive and a per step algorithms with Java implementation at cut-the-knot
Towers Of Hanoi in c++ using Stacks at 24bytes

Events

[3] Workshop on the Tower of Hanoi and Related Problems, 18.9. - 22.9.2005, Maribor, Slovenia]]

da:Hanois tårn de:Türme von Hanoi es:Torres de Hanoi eo:Turoj de Hanojo eu:Hanoiko Dorreak fr:Tours de Hanoï ko:하노이의 탑 is:Turninn í Hanoi he:מגדלי האנוי lb:Hanoi-Tuerm nl:Torens van Hanoi pt:Torre de Hanoi sl:Hanojski stolpi fi:Hanoin torni sv:Tornen i Hanoi th:หอคอยแห่งฮานอย vi:Tháp Hà Nội (bài toán) zh:汉诺塔

[1] 1000 Play Thinks

[1]