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

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

---

Hanoi(1)

• Move 1 from A to C
  當只有一個盤子時，很直覺的A移動到Ｃ

💡 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

💡 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

  💡 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)

💡 No need to combine the results in this case

• Call tree
  

  Hanoi(3, A, C, B)

  →

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

  →

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

  💡 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

💡

$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

In Chapter ADA 2.2

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

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

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

Solutions using math functions

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
• On the Frame–Stewart algorithm for the multi-peg Tower of Hanoi problem

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 (用這個可以找到滿多的)

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);
}