Rules and practice of the Game of the TOWER OF HANOI
-------------------
The base is placed horizontally; the pegs stand upright in the
holes in the surface. Then, the eight disks are stacked in decreasing
order from base to summit; this creates the Tower.
The game consists of moving this, by threading the disks on another
peg, and by moving only one disk at a time, obeying the following rules:
I. -- After each move, the disks will all be stacked on one, two, or
three pegs, in decreasing order from the base to the top.
II. -- The top disk may be lifted from one of the three stacks of
disks, and placed on a peg that is empty.
III. -- The top disk may be lifted from one of the three stacks and
placed on top of another stack, provided that the top disk on that
stack is larger.
--------------------
The Game easily teaches itself, in solving first the problem for
3, 4, and 5 disks.
--------------------
The Game is always possible and requires double the time each time
that an additional disk is placed on the tower. Anyone who knows how
to solve the problem for eight disks, for example, moving the tower
from peg number 1 to peg number 2, also knows how to solve it for
nine disks. One first moves the eight top disks to peg number 3,
then moves the ninth disk to peg number 2, and then brings the eight
disks from peg number 3 to peg number 2. Now, in augmenting the
tower by one disk, the number of moves is doubled, plus one, from
the preceding game.
For a tower of two disks, three moves are required;
-three -- seven ---
-four -- fifteen ---
-5 -- 31 ---
-6 -- 63 ---
-7 -- 127 ---
-8 -- 255 ---
and so on.
At one move per second it requires more than four minutes to move
a tower of eight disks.
Variations of the Game. -- One varies, to infinity, the conditions
of the problem of the tower of Hanoi as follows. At the beginning,
one stacks the disks, in any manner, on one, two, or all three pegs.
It is necessary to reconstruct the Tower on one of the pegs designated
in advance. For 64 disks, the number of initial arrangements is
staggering; the number is more than 50 digits long.
For more details, consult the following work in the chapter on
the Baguenaudier:
RÉCRÉATIONS MATHÉMATIQUES
by Mr. Édouard Lucas,
professor of higher mathematics
at the Lycée Saint-Louis
Two small volumes, in two colors
--------------------
Paris, 1883, by GAUTHER-VILLARS,
printer of the Académie des
Sciences and the Ecole Polytechnique
Quai des Augustins, 55
Back to
Page One of the
English translation of the original instructions.
Back to the beginning
Tower of Hanoi page.
This page is maintained by
Paul K. Stockmeyer. Select my name to see my home page.
|
The URL for this page is
http://www.cs.wm.edu/~pkstoc/page_2.html
Last updated 27 August 1998
|