Definition(s)

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

Only one disk can be moved at a time.
Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.
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