Tower of Hanoi

Tower of Hanoi#

Tower of Hanoi is a mathematical puzzle where we have three rods and $n$ disks. 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 i.e. a disk can only be moved if it is the uppermost disk on a stack.
No disk may be placed on top of a smaller disk.

Define a function $f(n, a, b, c)$ where:
- $n$: Number of disks;
- $a$: The starting rod;
- $b$: The temporary rod;
- $c$: The ending rod.
The function $f$ is responsible to print out the steps of moving $n = k$ disks from $a$ to $c$.
We intend to find a recurrence relation of $f$ at step $n=k$ (i.e. $k$ rods). In other words, we seek to find $$ f(n=k, a, b, c) = f(n=k-1, a, b, c) \cdots $$

where at step number $k$, the function $f$ consist of steps made by $k-1, k-2 \ldots 1$. We see with an example.

Define rods $A, B, C$.
The base case:
- $f(n=1, a=A, b=B, c=C)$;
- Move $1$ disk from the starting rod $A$ to ending rod $C$ and we are done.
- We will denote this movement as $A \to C$ in future.
$n = 2$:
- $f(n=2, a=A, b=B, c=C)$;
- $A \to B$;
- $A \to C$;
- $B \to C$
- At this stage, the recursion and induction is not obvious.
$n = 3$:
- $f(n=3, a=A, b=B, c=C)$;
- $A \to C$;
- $A \to B$;
- $C \to B$;
- $A \to C$ (Base case)
- $B \to A$;
- $B \to C$;
- $A \to C$
Dissect $n=3$:
- One observes that the first three steps is defined by $f(n=2, a=A, b=C, c=B)$. Pay attention that $C$ is now our temporary rod. In short, the first three steps is to move the top 2 rods from $A$ to $B$. This is in fact the problem when $n=2$! Make a mental note that we are acting as if there are only 2 rods here as we are ignoring the bottom most rod for now, this makes sense since moving the top 2 rods is independent of the bottom most rod.
- Now we are left with the bottom most rod, let us move it to $C$. This is done by calling the base case, or more simply, just $A \to C$.
- Lastly, we will move the two rods residing in rod $B$ to $C$, and this is also done by calling $f(n=2, a=B, b=A, c=C)$ where $A$ is now our temporary rod! Be very clear here that we are just treating this problem as if $n=2$.
- The above steps make sense for me, but I do not see the recursion properly yet. This is because we didn’t think “recursively” in step $n=2$. Let us go back and take a look.
Going back to $n=2$:

def f(n:int, a, b, c):
    # if n==0:
    #     return 
    if n==1:
        print("me")
        print(f"Move from {a} to {c}")
        return
    f(n-1, a=a, b=c, c=b) # r1 = recursive call 1
    print(f"Move from {a} to {c}") # r2
    f(n-1, a=b, b=a, c=c) # r3

f(n=1,a="A", b="B", c="C")

me
Move from A to C

$f(n=2, a=A, b=B, c=C)$:
- $f(n=1, a=A, b=C, c=B)$
- This goes to base case, moving $A$ to $B$.
- At r2, we print $A$ to $C$ because at $n=2$, our arguments are still $a=A, b=B, c=C$.
- Then go r3, we have $f(n=1, a=B, b=A, c=C)$ and thus hits base case again which is $B$ to $C$.

f(n=2,a="A", b="B", c="C")

me
Move from A to B
Move from A to C
me
Move from B to C

f(n=3,a="A", b="B", c="C")

me
Move from A to C
Move from A to B
me
Move from C to B
Move from A to C
me
Move from B to A
Move from B to C
me
Move from A to C

$f(3, a=A, b=B, c=C)$
- Checks if $n=1$ for base case
- calls $f(n=2, a=A, b=C, c=B)$ which we already know the pattern from above example:
  - $f(n=1, a=A, b=B, c=C)$ be very careful here, when we reach here the $b$ and $c$ are swapped once more because at the base case we do want to put $A$ to $C$.
  - call stack ends and returns, function goes back to $f(n=2, a=A, b=C, c=B)$
- $f(n=2, a=A, b=C, c=B)$: function is released from $r_1$ and goes to $r_2$ which prints move $A \to B$ and this function is popped;
- Now we go to

Tower of Hanoi

Tower of Hanoi#

Going back to \(n=2\):