algorithmtowers-of-hanoi

Binary solution for Tower of Hanoi

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
Solution

  • 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