Tower of Hanoi Solution

The binary numbers, considered in numerical order, comprise a set of sequential moves that will allow you to solve the game of the Tower of Hanoi with the minimum number of moves, specifically 2ⁿ - 1 where n is the number of disks. Each binary number is read from the right until the first "1" is encountered. The position of that "1" from the right indicates the disk to move. If there is no other "1" in the binary number, that disk is moved to an empty peg. The second "1" from the right indicates the location of the reference disk. If there are no or an even number of zeros between these two "1"s (the first two "1"s from the right), the moving disk is moved so as to cover the reference disk. If there is an odd number of zeros between these two "1"s, the moving disk is moved so as NOT to cover the reference disk.

A few examples for five disks follow:

Move	Binary Number	Interpretation
8	01000	Move disk 4 to empty peg.
13	01011	Move disk 1 to cover disk 2.
25	11001	Move disk 1 to cover disk 4.
18	10010	Move disk 2 to cover disk 5.
10	11010	Move disk 2 NOT to cover disk 4.
17	10001	Move disk 1 NOT to cover disk 5.

The table below lists the 2⁵- 1 = 31 sequential moves required for a tower with five disks. Try it with the interactive tower in http://www.lhs.berkeley.edu/Java/Tower/Tower.html. Before you begin, reset the number of blocks (disks) to five (5).

Move	Binary Number	Interpretation
1	00001	Move disk 1 to empty peg.
2	00010	Move disk 2 to empty peg.
3	00011	Move disk 1 to cover disk 2.
4	00100	Move disk 3 to empty peg.
5	00101	Move disk 1 NOT to cover disk 3.
6	00110	Move disk 2 to cover disk 3.
7	00111	Move disk 1 to cover disk 2.
8	01000	Move disk 4 to empty peg.
9	01001	Move disk 1 to cover disk 4.
10	01010	Move disk 2 NOT to cover disk 4.
11	01011	Move disk 1 to cover disk 2.
12	01100	Move disk 3 to cover disk 4.
13	01101	Move disk 1 NOT to cover disk 3.
14	01110	Move disk 2 to cover disk 3.
15	01111	Move disk 1 to cover disk 2.
16	10000	Move disk 5 to empty peg.
17	10001	Move disk 1 NOT to cover disk 5.
18	10010	Move disk 2 to cover disk 5.
19	10011	Move disk 1 to cover disk 2.
20	10100	Move disk 3 NOT to cover disk 5.
21	10101	Move disk 1 NOT to cover disk 3.
22	10110	Move disk 2 to cover disk 3.
23	10111	Move disk 1 to cover disk 2.
24	11000	Move disk 4 to cover disk 5.
25	11001	Move disk 1 to cover disk 4.
26	11010	Move disk 2 NOT to cover disk 4.
27	11011	Move disk 1 to cover disk 2.
28	11100	Move disk 3 to cover disk 4.
29	11101	Move disk 1 NOT to cover disk 3.
30	11110	Move disk 2 to cover disk 3.
31	11111	Move disk 1 to cover disk 2.

Jill Britton Home Page