# Tower of Hanoi
## Problem Statement
[Hanoi Towers](https://en.wikipedia.org/wiki/Tower_of_Hanoi) is a classic puzzle: given three rods and n disks of distinct sizes stacked on one rod in increasing order (largest at the bottom, smallest on top), move the entire stack to a target rod while preserving order.

### Rules
1. Move exactly one disk per step.
2. You may place a disk only on an empty rod or on top of a larger disk.
3. Only the topmost disk of any rod can be moved.

### Objective
Move all `n` disks from the source rod to the target rod (using the auxiliary rod if needed) in the minimum number of steps.

### Breakdown Problems
Let’s reason about how to move all disks to the target rod when n disks are given.

When there is only one disk `n = 1`, the solution is trivial — simply move that single disk from the source rod to the target rod. This requires one step in total.

Now, consider two disks `n = 2`.
We can observe that it takes three steps to complete the task:
1. Move the smaller (top) disk to the auxiliary rod.
2. Move the larger (bottom) disk to the target rod.
3. Finally, move the smaller disk from the auxiliary rod onto the target rod.

This leads to an interesting pattern — moving `n = 2` disks can be viewed as a sequence of smaller sub-problems:
1. First, move diskA (the top disks) to the auxiliary rod.
2. Then, move the largest diskB directly to the target rod.
3. Lastly, move the diskA from the auxiliary rod onto the target rod.

So based on above idea, if we want to move `n` disks to target rod, we need to
1. move `n-1` disks to auxiliary rod
2. move largest disk to target rod
3. move `n-1` disks to target rod

The recursive solution for this algorithm can be implemented as follows

void hanoi_tower(rod_t *ini, rod_t *aux, rod_t *tar, int c)
{
    if (c == 0)
        return;
    // Step 1: Move n-1 from ini to aux rod
    hanoi_tower(ini, tar, aux, c - 1);  
    // Step 2: Move the largest disk to tar           
    move(ini, tar);      
    // Step 3: Move n-1 from aux to tar
    hanoi_tower(aux, ini, tar, c - 1);  
    c--;
}

### Analysis of Recursive Approach
Let $S(D)$ denote the function that maps the number of disks $D$ to the minimum number of steps required to solve the Tower of Hanoi problem.

When only has one disk $D=1$, it requires exact one move, hence:
\begin{aligned}
S(1)=1
\end{aligned}
For large value of $D$, the problem can be recursivly decomposed as:
\begin{aligned}
S(D)=S(D-1)+1+S(D-1)=2S(D-1)+1
\end{aligned}
Expanding this recurssion for the first few values:
\begin{aligned}
&S(2) = 2S(1)+1=2^2-1\\
&S(3) = 2S(2)+1=2(2^2-1)+1=2^3-1\\
&S(4) = 2S(3)+1=2(2^3-1)+1=2^4-1\\
&S(5) = 2S(4)+1=2(2^4-1)+1=2^5-1\\
&...\\
&S(k) = S(k-1)+1+S(k-1)=2^k-1
\end{aligned}

Therefore, the minimum number of moves required to transfer $D$ disks from the source rod to the target rod follows an exponential growth pattern:
\begin{aligned}
S(D)=2^D-1
\end{aligned}
The time complexity is $O(2^D)$, indicating that the computational cost increases exponentially as the number of disks $D$ increases.

### No recurrsion
We have analyzed the total number of steps required for different numbers of disks. Can we achieve the same goal without recursion?
By observing $S(D)$, we can find that each total step corresponds to a specific range of bits. When a disk is moved, the system state changes, and each state can be uniquely represented as a binary number that is independent from the others.

For example, consider $D=1$. The total number of steps is $2^1-1$, meaning that only "one" bit is needed to represent all possible state transitions. For convenience, let the initial state be represented by all bits set to 0, as shown in the figure.

Let us consider $D=2$. The corresponding number of steps is $2^2-1$, which means that "two" bits are required to represent all possible states after each disk movement.

Yes, each state can be represented using two bits, but how should these bits be defined or encoded?
Below is an encoding method based on the step index, where the step count itself is used to represent the corresponding state.
Now we know that, for example, step 2 corresponds to the state transition `01 → 10`.
This transition implies a specific disk movement between rods.

#### Which disk should be moved?
Given a specific step index $m$, we can determine which disk should be moved during that step.

Let’s start with simple examples:

* When $D=1$:
The state transition is `0 → 1`.
Bit 0 flips from 0 to 1, which means disk A (the smallest disk) is moved.

* When $D=2$:
* Step 1: state `00 → 01`, bit 0 flips → move disk A.
* Step 2: state `01 → 10`, bit 1 flips → move disk B.

From these examples, we can observe that the disk to move at step $m$ corresponds to the bit position that changes between the binary representations of $m-1$ and $m$.

This behavior can be described mathematically. The total number of steps for $D$ disks follows:
\begin{aligned}
S(D)=S(D-1)+1+S(D-1)
\end{aligned}
Here, the middle “$+1$” represents the movement of the largest disk (disk $D$).Since $S(D-1) = 2^{D-1} - 1$, the step index when the largest disk moves is:
\begin{aligned}
S(D-1)+1 = 2^{D-1}
\end{aligned}which is always a **power of two**.
Therefore, for each new step $m$, we can count trailing zeros and add 1 to determine which disk should be moved.

For example, `m=00010100`, the 3(2+1)th disk should be moved during this step.
#### How disk come from and go to?
We need to consider how each disk transitions between the three rods.
Is there a specific routine that determines this movement?

Let’s denote the three rods as "A", "B", and "C", from left to right, respectively.
The objective is to move all disks that are initially placed on rod "A" to rod "C".

Now, let’s focus on diskA (the smallest disk).
In the first move, diskA can go either to rod "B" or rod "C".

Let’s analyze the case where it moves to rod "B" first.
The next time diskA moves, it must go to rod "C" because returning to its previous rod would be redundant and unnecessary.
Now diskA is on rod "C".
What happens next movement of diskA?
Yes, it will move to rod "A", since rod "B" is where it just came from.

Thus, we can construct a cyclic movement pattern:
\begin{aligned}
A\rightarrow B\rightarrow C\rightarrow A
\end{aligned}If, instead, diskA had initially moved to rod "C",
the same reasoning applies, producing the opposite direction of the cycle:
\begin{aligned}
A\rightarrow C\rightarrow B\rightarrow A
\end{aligned}

The direction of movement depends on the total number of disks $D$.

For example, if $D = 2$, then diskA (the smallest disk) must move to the auxiliary rod "B" first.
However, if $D = 3$, since the larger disk ($D=2$) must move to the auxiliary rod "B", this implies that diskA must move to the target rod "C" instead.

#### Computing the rod index from step $m$
Now that we understand how each step decides which disk moves and its movement direction,
we can further determine where each disk is located at a specific step $m$.

Right-shifting $m$ by the value of its trailing zeros gives the total number of times that this disk has already moved before the current step.

The movement direction can be determined by checking the parity of the total number of disks $D$ and the current disk index (starting from 1 for the smallest disk).
If both $D$ and the disk index have the same parity, the disk moves counterclockwise; otherwise, it moves clockwise.

Once we know the direction and how many times the disk has moved,
we can take the result modulo 3 to find its corresponding rod index.

For example, assume step `m` where diskA (1) has already moved twice, and the total number of disks is $D = 3$. The parity of 3 and 1 are the same, meaning it moves counterclockwise.
Therefore, after step `m`, the rod position of diskA (1) is B, because the movement pattern is $A \rightarrow C \rightarrow B\rightarrow A$,and after 2 moves $(2 \bmod 3)$, it reaches rod "B".

## Gray Code
[Gray code](https://en.wikipedia.org/wiki/Gray_code) is a sequence of binary numbers in which each successive value differs from the previous one by exactly one bit. The Gray code of $n$ bits is not unique; there exist many different variants, all of which follow the one-bit difference rule.

### Construct a Gray code sequence
Let $G_n$ denote n-bit Gray code sequence. It can be defined recursively as follows:
\begin{aligned}
G_n=[0\cdot G_{n-1}, 1\cdot rev(G_{n-1})]
\end{aligned}where $rev(G_{n-1})$ denotes the reversed order of $G_{n-1}$, and the dot ($\cdot$) represents concatenation (bit prefixing).
Given initial sequence $G_1=[0,1]$ and we can construct corresponding $G_n$ sequence recursively. For example, $n=2$:
\begin{aligned}
& G_2=[0\cdot G_{1}, 1\cdot rev(G_{1})], where \ G_1=[0,1]\ and \ rev(G_1)=[1,0]\\
\therefore &G_2 =[00, 01, 11,10]
\end{aligned}

### Why Gray code needed?

Let's consider a problem that arises when each step is encoded as a unique binary state.
When the state (step) changes from `1 → 2`, the corresponding binary representations are `01 → 10`.
In this transition, two bits flip simultaneously, which may cause an error if the signal is sampled at an improper time.
This happens because during the carry propagation from the lower bit to the higher bit, the intermediate state `00` may appear temporarily before reaching `10`. Gray code can solve this problem because it only flips one bit each state transition.

### Encode steps into Gray code
In the previous section, we used the step number to determine which disk should be moved. Now, our concern is how to encode each step into a Gray code to ensure system consistency.

Given the step $s$, the corresponding Gray code can be generated by:
\begin{aligned}
G(s) = s \oplus(s\text{>>}1)
\end{aligned}where $\oplus$ denotes bitwise XOR, and >> means right shift. The question is how it works?

Consider two successive steps $s$ and $s+1$, the corresponding Gray codes
$G(s)$ and $G(s+1)$ differ in exactly one bit. This single-bit difference arises naturally from the binary carry operation. When a carry occurs in binary counting—for example, from `01→10`—the relative difference between adjacent bits remains complementary (i.e., still different). By recording this bitwise difference instead of the binary value itself, we can generate a sequence in which only one bit changes per step.

This property ensures that consecutive Gray codes maintain one-bit transitions, which directly map to the movement of a single disk in the Tower of Hanoi process. Specifically, the position of the flipped bit indicates which disk should move, while the parity of the step and disk index determines its direction of movement.

Take 3 disks as example, the corresponding step and gray code:

Decimal(step) | Binary | Gray Code | Changed Bit
   0(init)    |  000   |    000    |     -
   1          |  001   |    001    |    bit 0
   2          |  010   |    011    |    bit 1
   3          |  011   |    010    |    bit 0
   4          |  100   |    110    |    bit 2
   5          |  101   |    111    |    bit 0
   6          |  110   |    101    |    bit 1
   7          |  111   |    100    |    bit 0

Based on Gray code approach, we can figure out each state transition by figure out which bit flipped.

int curr_gray = n_moves ^ (n_moves >> 1);
int prev_gray = (n_moves - 1) ^ ((n_moves - 1) >> 1);
int changed_bit = curr_gray ^ prev_gray;

## Gray code and Hanoi Tower

## Summary
In summary, the recursive, step-based, and Gray code approaches all describe the same Tower of Hanoi process, but from different perspectives and with different computational characteristics.

1. Recursive approach provides an intuitive and hierarchical explanation of the problem.
It defines the entire procedure by decomposing it into smaller subproblems, making it conceptually clear but computationally expensive due to recursive function calls and stack usage.

2. Step-based approach eliminates recursion by directly deriving the disk movement from the step index $s$. It achieves $O(1)$ time per move through simple arithmetic or bitwise analysis (e.g., counting trailing zeros), but still requires maintaining the current rod position of each disk to correctly perform the move.

3.Gray code approach represents each step as a unique binary state $G(s)=s\oplus(s>>1)$.
It ensures that consecutive states differ by exactly one bit, inherently identifying which disk should move.
However, similar to the step-based method, it does not inherently encode the rod assignment; thus, an external state table or mapping is still required to track the current rod of every disk.

In conclusion, recursion explains why the sequence works,
while the step and Gray code approaches explain how to generate it efficiently.
Yet, both iterative methods still rely on explicit state tracking to determine where each disk currently resides, which is essential for actual movement execution.