# 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 :

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 :

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

``````

# Run(s)

``````

In :

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 :

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 :

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 :

print("Number of moves for n=10 is", number_moves(10))

``````
``````

Number of moves for n=10 is 1023

``````