[go: up one dir, main page]

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
2n - 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 25- 1 = 31 sequential moves required for a tower with five disks. Try it with the interactive tower in Towers of Hanoi Puzzle.  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		 01-December-2015
Copyright Jill Britton