11.

Tower of Hanoi
Robert Snapp
[email protected]
Department of Computer Science
University of Vermont
Robert R. Snapp 2012 11. Tower of Hanoi CS 32, Fall 2012 1 / 20
The Tower of Hanoi: Origin
In the great temple at Benares, beneath the dome which marks the center
of the world, rests a brass plate in which are xed three diamond needles,
each a cubit high and as thick as the body of a bee. On one of these
needles, at the creation, God placed sixty-four discs of pure gold, the
largest disk resting on the brass plate, and the others getting smaller and
smaller up to the top one. This is the Tower of Bramah. Day and night
unceasingly the priests transfer the discs from one diamond needle to
another according to the xed and immutable laws of Bramah, which
require that the priest on duty must not move more than one disc at a time
and that he must place this disc on a needle so that there is no smaller disc
below it. When the sixty-four discs shall have been transferred from the
needle on which at the creation God placed them to one of the other
needles, tower, temple, and Brahmins alike will crumble into dust, and with
a thuderclap the world will vanish.
(From, De Parville, La Nature, 1884, part I, pp. 285286; as translated in W. W. Rouse Ball and
H. S. M. Coxeter, Mathematical Recreations and Essays, 13th edition, Dover, NY, 1987,
p. 317.)
Robert R. Snapp 2012 11. Tower of Hanoi CS 32, Fall 2012 2 / 20
The Tower of Hanoi: The Puzzle
Initial State:
Goal State:
Only one disk can be moved at a time, from one peg to another, such that it never is
placed on a disk of smaller diameter.
Robert R. Snapp 2012 11. Tower of Hanoi CS 32, Fall 2012 3 / 20
Tower of Hanoi: One Disk Solution
1 Move.
Robert R. Snapp 2012 11. Tower of Hanoi CS 32, Fall 2012 4 / 20
Two Disk Solution
Note that we perform the solution to the one-disk Tower of Hanoi twice (once in the
top row, and once in the bottom row). Between rows, we move the bottom disk. Thus,
we require
2 1 C1 D 3 Moves
Robert R. Snapp 2012 11. Tower of Hanoi CS 32, Fall 2012 5 / 20
Tower of Hanoi: Three Disk Solution
Note that we perform the solution to the two-disk Tower of Hanoi twice (once in the
top row, and once in the bottom row). Between rows we move the bottom disk. Thus,
we require
2.2 1 C1/ C1 D 7 Moves
Robert R. Snapp 2012 11. Tower of Hanoi CS 32, Fall 2012 6 / 20
Tower of Hanoi: What we know so far
Let M.n/ denote the minimum number of legal moves required to complete a tower
of Hanoi puzzle that has n disks.
n M.n/
1 1
2 3
3 7
Following the pattern, for n D 4 we need to solve the three-disk puzzle twice, plus
one more operation to move the largest disk. Thus,
M.4/ D 2 M.3/ C1 D 2 7 C1 D 15:
Similarly, for n D 5 disks, we expect that we will need to perform
M.5/ D 2 M.4/ C1 D 2 15 C1 D 31:
Robert R. Snapp 2012 11. Tower of Hanoi CS 32, Fall 2012 7 / 20
Tower of Hanoi: n Disk Analysis
Let M.n/ denote the minimum number of legal moves required to complete a tower
of Hanoi puzzle that has n disks.
Before the largest disk (i.e., the n-th disk) can be moved to the rightmost peg, all
of the remaining (n 1) disks must moved to the center peg. (These n 1 disks
must be somewhere, and they cant obstruct the transfer of the largest disk.)
This requires M.n 1/ legal moves.
It takes 1 more operation to move the n-th disk to the rightmost peg.
Finally, another legal sequence of M.n 1/ steps is required to move the n 1
disks from the center peg, to the rightmost peg.
We thus obtain the recursion relation,
M.n/ D 2M.n 1/ C1:
Robert R. Snapp 2012 11. Tower of Hanoi CS 32, Fall 2012 8 / 20
Tower of Hanoi: Solution
With the solution for a single disk
M.1/ D 1
the recursion relation
M.n/ D 2M.n 1/ C1:
denes the solution
M.n/ D 2
n
1:
In are hierarchy of algorithms, this would be called exponential or O.2
n
/.
Robert R. Snapp 2012 11. Tower of Hanoi CS 32, Fall 2012 9 / 20
Tower of Hanoi: Practical Consequences
The practical difculty with exponential algorithms is that they can quickly grow out of
hand. (With each additional disk, the minimum number of operations essentially
doubles.) N.B., 1 century 4:5 10
9
seconds. (The age of the universe is 4 10
17
seconds.)
n 2
n
1 n 2
n
1 n 2
n
1
8 255 19 524287 30 1073741823
9 511 20 1048575 31 2147483647
10 1027 21 2097151 32 4294967295
11 2047 22 4194303 33 8589934591
12 4095 23 8388607 34 17179869183
13 8191 24 16777215 35 34359738367
14 16383 25 33554431 36 68719476735
15 32767 26 67108863 37 137438953471
16 65635 27 134217727 38 274877906943
17 131071 28 268435455 39 549755813887
18 262143 29 536870911 64 18446744073709551615
Robert R. Snapp 2012 11. Tower of Hanoi CS 32, Fall 2012 10 / 20
Tower of Hanoi: Strategy
We have seen that the solution to this puzzle is recursive:
In order to move all n disks to the right peg, we must rst move the top n 1
disks to the center peg.
Before this, we must move the top n 2 disks to the right peg.
And before this, we must move the top n 3 disks to the center peg, and so on.
So what should the rst move be? Should the top disk be moved to the center peg, or
to the right peg?
Robert R. Snapp 2012 11. Tower of Hanoi CS 32, Fall 2012 11 / 20
Tower of Hanoi: Solution Path
If the number of disks is odd, then the rst move should be to transfer the top
disk to the right peg.
If the number of disks is even, then the rst move should be to transfer the top
disk to the center peg.
The sequence of states that is visited in the course of solving the puzzle is called the
solution path.
The length of the shortest solution path to the n-disk puzzle is 2
n
.
Robert R. Snapp 2012 11. Tower of Hanoi CS 32, Fall 2012 12 / 20
Tower of Hanoi: Legal States
A conguration of disks in the Tower of Hanoi puzzle is said to be a legal state if no
disk rests on a disk of smaller diameter. That is, the largest disk on each peg must be
placed on the bottom, and the remaining disks must be placed in the order of
decreasing diameter.
Question: How many legal states are there for n disks placed on three pegs?
Robert R. Snapp 2012 11. Tower of Hanoi CS 32, Fall 2012 13 / 20
Tower of Hanoi: Accessible States
A conguration of disks is said to be anaccessible state, if it can be realized from the
initial state after a legal sequence of moves.
Question: How many accessible states are there for n disks placed on three pegs?
Robert R. Snapp 2012 11. Tower of Hanoi CS 32, Fall 2012 14 / 20
Tower of Hanoi: Examples
Number Length of Number Fraction of
of Disks Solution Path of Legal States Visited States
n 2
n
3
n
.2=3/
n
1 2 3 0.6666667
2 4 9 0.4444446
3 8 27 0.2962963
4 16 81 0.1975309
5 32 243 0.1316872
6 64 729 0.0877915
7 128 2187 0.0585277
8 256 6561 0.0390184
32 4294967296 1853020188851841 2:32 10
6
Robert R. Snapp 2012 11. Tower of Hanoi CS 32, Fall 2012 15 / 20
State Representation
Its cumbersome to represent a state by an illustration. Instead we will adopt a list
notation.
For example, for a ve disk puzzle, the notation
(2 1 3 1 1)
indicates
The smallest disk is on peg 2 (the center peg).
The next larger disk is on peg 1 (the left peg).
The next larger disk is on peg 3 (the right peg).
The next larger disk is on peg 1.
The next larger (i.e., largest) disk is on peg 1.
The only legal conguration that describes this is
1 2 3
Robert R. Snapp 2012 11. Tower of Hanoi CS 32, Fall 2012 16 / 20
State Graph: 1 disk
(2)
(1)
(3)
Each state is represented by a labeled vertex; legal moves are represented by edges.
Robert R. Snapp 2012 11. Tower of Hanoi CS 32, Fall 2012 17 / 20
State Graph: 2 disks
(33) (22) (13) (12)
(11)
(21)
(23)
(31)
(32)
Robert R. Snapp 2012 11. Tower of Hanoi CS 32, Fall 2012 18 / 20
State Graph: 3 disks
(333) (222)
(113) (112)
(111)
(311) (211)
(321)
(121) (131)
(231)
(123) (132) (323) (232)
(313) (212)
(133) (122)
(233) (322) (213) (312)
(221)
(223)
(331)
(332)
Robert R. Snapp 2012 11. Tower of Hanoi CS 32, Fall 2012 19 / 20