Day 01 - Tower of Hanoi


Definition(s)

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

  1. Only one disk can be moved at a time.
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.
  3. No disk may be placed on top of a smaller disk.

Algorithm(s)


In [1]:
def move(n, source, target, auxiliary):
    if n > 1:
        move(n - 1, source, auxiliary, target)
        print("Move disk {0} from {1} to {2}".format(n, source, target))
        move(n - 1, auxiliary, target, source)
    elif n == 1:
        print("Move disk {0} from {1} to {2}".format(n, source, target))
    else:
        raise ValueError("n < 1")

In [4]:
def number_moves(n):
    if n < 1:
        raise ValueError("n < 1")
    else:
        return 2 ** n - 1

Run(s)


In [2]:
move(3, 'A', 'B', 'C')


Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Move disk 3 from A to B
Move disk 1 from C to A
Move disk 2 from C to B
Move disk 1 from A to B

In [3]:
move(0, 'A', 'B', 'C')


---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-3-bec78f908698> in <module>()
----> 1 move(0, 'A', 'B', 'C')

<ipython-input-1-af13aeafb0e3> in move(n, source, target, auxiliary)
      7         print("Move disk {0} from {1} to {2}".format(n, source, target))
      8     else:
----> 9         raise ValueError("n < 1")

ValueError: n < 1

In [5]:
move(4, 'A', 'B', 'C')


Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
Move disk 4 from A to B
Move disk 1 from C to B
Move disk 2 from C to A
Move disk 1 from B to A
Move disk 3 from C to B
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B

In [8]:
print("Number of moves for n=10 is", number_moves(10))


Number of moves for n=10 is 1023