###### tags: `ADA 2.3` `Hanoi Tower`

# ADA 2.3 Hanoi Tower

# Tower of Hanoi（河內塔）

- Problem: move n disks from A to C
- Rules
- Move one disk at a time
- Cannot place a larger disk onto a smaller disk

沒玩過得去線上版本玩一下 [Play Online](https://www.mathsisfun.com/games/towerofhanoi.html)

簡易規則：一定要在大盤子上面，一次只能移動一個

---

# Hanoi(1)


- Move 1 from A to C
當只有一個盤子時，很直覺的A移動到Ｃ
:::info
💡 1 move in total
Base case
:::

---

# Hanoi(2)


- Move 1 from A to B
- Move 2 from A to C
- Move 1 form B to C

:::info
💡 3 moves in total
:::

---

# Hanoi(3)

- How to move 3 disks?

- 1 A → C
- 2 A → B
- 1 C → B
- 3 A → C
- 1 B → A
- 2 B → C
- 1 A → C
- How many moves in total?
- 7 步

---

# Hanoi(n)


- How to move n disks?
- How many moves in total?

- To move n disks from A to C (for n > 1):
1. Move Disk 1~n-1 form A to B
2. Move Disk n from A to C
3. Move Disk 1~n-1 from B to C

:::info
💡 2Hanoi(n-1) + 1 moves in total
recursive case
:::

---

# Pseudocode for Hanoi

Hanoi(n, src, dest, spare)
	if n == 1 // base case
		Move disk from src to dest
	else // recursive case
		Hanoi(n-1, src, spare, dest)
		Move disk from src to dest
		Hanoi(n-1, spare, dest, src)

:::info
💡 No need to combine the results in this case
:::

- Call tree

Hanoi(3, A, C, B)

→

:::info
💡 Hanoi(2, A, B, C)
Hanoi(2, B, C, A)
:::

→

:::info
💡 Hanoi(1, A, C, B)
Hanoi(1, C, B, A)
:::

:::info
💡 Hanoi(1, B, A, C)
Hanoi(1, A, C, B)
:::
較沒有效率，重複做很多事

---

# Algorithm Time Complexity

Hanoi(n, src, dest, spare)
	if n == 1 // base case
		Move disk from src to dest
	else // recursive case
		Hanoi(n-1, src, spare, dest)
		Move disk from src to dest
		Hanoi(n-1, spare, dest, src)

- T(n) = #moves with n disks
- Base case: T(1) = 1
- Recursive case (n > 1): T(n) = 2T(n - 1) + 1

:::info
💡 $T(n)=2^n-1=O(2^n)$
:::

- We will learn how to derive T(n) later

---

# Further Questions

- Q1: Is $O(2^n)$ tight for Hanoi? Can $T(n) < 2^n - 1$
- Q2: What about more than 3 pegs?
- Q3: Double-color Hanoi problem
- Input: 2 interleaved-color towers
- Output: 2 same-color towers

## Q2 What about more than 3 pegs?
> Before the start, try to play Tower of Hanoi 3up pegs, click bellow linked.
[Towers of Hanoi](http://towersofhanoi.info/Play.aspx)

:::info
In Chapter [ADA 2.2](https://hackmd.io/@30life-algorithm/B1ZfrgZXs)

Recurrence and Divide-and-Conquer :
- Defined the base case. (the logic of smallest)
- Find the stop point.
- Answer maybe is not the tight.
**It's maybe a simple way to find an answer is not the best solution.**
:::

### So, is it suitable of 3up Hanoi ?
#### Tower of Hanoi 4 pegs

:::info
In my colleage days, the case of 4 pegs is often called Reves’s problem – the problem being to determine the least number of moves to move all disks was not verified until 2014, by Bousch.
:::

### Try to Divide-and-Conquer

- There are 4 pegs
- The other rules are the same of Tower of Hanoi

:::warning
### Step 1.
**move f(n-2)**

### Step2.
**move f(1)**

### Step3.
**move f(1) + f(1)**

### Step4.
**move f(n-2)**

void Hanoi4Pegs::step(int n) {
    if (n == 0) {
        return;
    }
    
    if (n == 1) {
        move += 1;
        return;
    }
    
    step(n-2);
    step(1);
    step(1);
    step(1);
    step(n-2);
}

:::

#### Compare the best solutions

         Normal - Best
0 Disks -     0 - 0
1 Disks -     1 - 1
2 Disks -     3 - 3
3 Disks -     5 - 5
4 Disks -     9 - 9
5 Disks -    13 - 13
6 Disks -    21 - 17
7 Disks -    29 - 25
8 Disks -    45 - 33
9 Disks -    61 - 41
10 Disks -   93 - 49
20 Disks - 3069 - 289
23 Disks - 8189 - 449

:::spoiler **Solutions using math functions**
:::warning
**n > 1;**
**f(n) = 2^(g(2) + f(n-1)**
**g(n) = ROUND(√(2x-1)) - 1**

void Hanoi4Pegs::step(int n) {
    if (n < 1)
    {
        return;
    }

    int a = round(sqrt(2 * n - 1)) - 1;
    
    move += pow(2, a);
    
    step(n-1);
};

:::

### Summary
The complexity has increased to the point where it is not easy to use Divide-and-Conquer to find the best answer.

### Reference Paper
- [Explorations in 4-peg Tower of Hanoi](http://service.scs.carleton.ca/sites/default/files/tr/TR-04-10.pdf)
- [On the Frame–Stewart algorithm for the multi-peg Tower of Hanoi problem](https://www.sciencedirect.com/science/article/pii/S0166218X01002876)

## Q3. Double-color Hanoi problem:
We maybe can not use the same of solutions to find the best answer for 4 pegs Tower of Hanoi.
But we still try to just find a answer.

AKA Bicolour Towers of Hanoi (用這個可以找到滿多的)

:::danger
I had not tried to proof this answer.

// The first solution
int first2ColorsHanoi(int n) {
   if (n <= 0) {
      return 0;
   }
   
   if (n == 1) {
      return 1;
   }
   
   return first2ColorsHanoi(1) + first2ColorsHanoi(n-1) + first2ColorsHanoi(n-1);
}

// second

int second2ColorHanoi(int n) {

if (n <= 0) {
      return 0;
   }
   
   if (n == 1) {
      return 1;
   }
   
   return second2ColorHanoi(n-1) + second2ColorHanoi(n-1);
}

:::