Binary solution for Tower of Hanoi

Question

I am reading Algorithms by Robert Sedgewick

Below is an excerpt from page 213, in reference to number of trailing zeros in binary representation of numbers.

For the towers of Hanoi problem, the implication of the correspondence with n-bit numbers is a simple algorithm for the task. We can move the pile one peg to the right by following two steps until done:

1. Move the small disk to the right if n is odd (left if n is even)
2. Make the only legal move not involving the small disk.

That is, after we move the small dsik, the other two pegs contain two disks, one smaller than the other. The only legal move not involving the small disk is to move the smaller one onto the larger one. Every other move involves the smaller disk for the same reason that every other number is odd and that every other mark on the rule is the shortest.

The above text is not getting into my head, even after reading various references from goolged information.

Please help me with a simple example for example disks N = 3. Disk3 is largest and Disk1 is smallest, and they need to be moved from from PegA to PegB.

Disk1
Disk2
Disk3
-------       ------------         ------------
Peg A            Peg B                 Peg C

Answer 1

In case this helps anyone, I wrote up a full solution in python here: https://github.com/goblinhack/towers-of-hanoi

#!/usr/bin/env python
#
# The way to solve this is quite simple but does differ slightly for N = odd or even numbers of rings.
# 
# At each move you do either a) or b):
# 
# a) move the "1" value to the peg to the right, wrapping around to the first peg if needed
# 
# b) make the only other legal move
# 
# And then repeat either a) or b) for (2 ^ numrings) - 1.
# 
# So for N=3, you would do the above steps 7 times.
# 
# The catch that I alluded to earlier is that for N == odd (3,5,...), you will need to repeat this
# entire algorithm one more time as the above will only move the rings one peg to the right. 
#
import sys

#
# Print the tower so we can check our progress
#
def print_tower(pegs, nrings):
    npegs = len(pegs)
    for y in range(0, nrings):
        h = nrings - y
        for x in range(0, npegs):
            if len(pegs[x]) >= h:
                sys.stdout.write(str(pegs[x][len(pegs[x]) - h]) + " ")
            else:
                sys.stdout.write("| ")
        print("")
    print("-----")

def solve_tower(nrings, npegs):
    pegs = []
    for peg in range(0, npegs):
        pegs.append([])

    #
    # push the nrings on
    #
    for i in range(0, nrings):
        pegs[0].append(i + 1)

    #
    # For N == odd numbers we will need to repeat this twice
    #
    for tries in range(0, 1 + nrings % 2):
        print_tower(pegs, nrings)
        move_peg_one_right = True

        #
        # Repeat the steps a) or b) for 2^N-1 times
        #
        for moves in range(0, (1 << nrings) - 1):
            #
            # step a)
            #
            if move_peg_one_right:
                for peg in range(0, npegs):
                    if len(pegs[peg]):
                        if pegs[peg][0] == 1:
                            next_peg = (peg + 1) % npegs
                            pegs[next_peg].insert(0, pegs[peg].pop(0))
                            print("Moving value 1 from peg {} to peg {}\n".format(peg + 1, next_peg + 1))
                            break
            else:
                #
                # step b)
                #
                moved_a_ring = False
                for peg in range(0, npegs):
                    #
                    # Look for a ring on a peg to move
                    #
                    if len(pegs[peg]):
                        value = pegs[peg][0]
                        #
                        # Don't move the ring value "1" as we move that in a)
                        #
                        if value != 1:
                            for next_peg in range(0, npegs):
                                #
                                # The next peg is the one to the right of this peg. If we reach the last peg then we
                                # need to move to the first peg.
                                #
                                next_peg = (peg + next_peg) % npegs

                                #
                                # Don't move to the same peg; that would be silly
                                #
                                if next_peg == peg:
                                    continue

                                #
                                # If the destination peg is empty, move there
                                #
                                if not len(pegs[next_peg]):
                                    pegs[peg].pop(0)
                                    pegs[next_peg].insert(0, value)
                                    moved_a_ring = True
                                    print("Moving value {} from peg {} to empty peg {}\n".format(value, peg + 1, next_peg + 1))
                                    break
                                elif value < pegs[next_peg][0]:
                                    #
                                    # Else if the destination peg has a lower value, move there
                                    #
                                    pegs[peg].pop(0)
                                    pegs[next_peg].insert(0, value)
                                    moved_a_ring = True
                                    print("Moving < value {} from peg {} to peg {} dest {}\n".format(value, peg + 1, next_peg + 1, pegs[next_peg][0]))
                                    break
                    if moved_a_ring:
                        break

                if not moved_a_ring:
                    print("Error, failed to move")
                    sys.exit(1)

            print_tower(pegs, nrings)

            #
            # Alternate between a) and b)
            #
            move_peg_one_right = not move_peg_one_right

        print("Finished pass\n")

nrings = 3
npegs = 3
solve_tower(nrings, npegs)

Answer 2

The first thing to note here is that in this algorithm, the first peg is considered to be right of the last peg, and the last peg is considered to be left of the first peg.

Applying the two steps listed iteratively will result in a tower of n disks being moved right by one peg.

In the case n = 3, n is odd, so the two moves are:

1. Move Disk1 one peg right.
2. Make the only legal move not involving Disk1.

Giving the following solution by repeating these moves:

1. Disk1: PegA -> PegB (Move Disk1 one peg right)
2. Disk2: PegA -> PegC (Only legal move not involving Disk1)
3. Disk1: PegB -> PegC (Move Disk1 one peg right)
4. Disk3: PegA -> PegB (Only legal move not involving Disk1)
5. Disk1: PegC -> PegA (Move Disk1 one peg right)
6. Disk2: PegC -> PegB (Only legal move not involving Disk1)
7. Disk1: PegA -> PegB (Move Disk1 one peg right)

When he writes "the correspondence with n-bit numbers", Sedgewick is referring to the fact that the disk you move in step k of the solution is the disk that corresponds to the least significant 1 bit in the binary representation of k. i.e. for n = 3:

step | bits | disk
------------------
  1  |  001 |  1
  2  |  010 |  2
  3  |  011 |  1
  4  |  100 |  3
  5  |  101 |  1
  6  |  110 |  2
  7  |  111 |  1

Answer 3

Well the solution for this particular problem is: move Disk1 to Peg B, move Disk2 to Peg C, move Disk1 to Peg C, move Disk3 to Peg B, move Disk1 to Peg A, move Disk2 to Peg B, move Disk1 to Peg B. Done.