ปัญหาหอคอยฮานอย (Tower of Hanoi Problem)

บทนำ

Tower of Hanoi เป็นปริศนา (Puzzle) ที่มี 3 ไม้กางเขน (Stands) และ n แผ่นกลม (Discs) เริ่มต้น แผ่นกลมวางอยู่ที่ไม้กางเขนแรก ต้องย้ายแผ่นกลมไปไม้กางเขนที่สามหรือปลายทาง ไม้กางเขนที่สองหรือช่วย (Auxiliary) ใช้เป็นไม้ช่วย

แตมีกฎที่ต้องปฏิบัติ:

• ย้ายได้เพียงแผ่นเดียวต่อการเคลื่อนที่หนึ่งครั้ง
• เฉพาะแผ่นบนสุดเท่านั้นที่สามารถยกได้จากไม้กางเขน
• ห้ามวางแผ่นใหญ่บนแผ่นเล็ก

ปัญหานี้แก้ได้ง่ายด้วย Recursion (การเรียกซ้ำ) ขั้นแรก ใช้ Recursion ย้ายแผ่นบน (n-1) จาก Source ไป Auxiliary แล้วย้ายแผ่นสุดท้ายจาก Source ไป Destination แล้วย้าย (n-1) จาก Auxiliary ไป Destination อีกครั้งด้วย Recursion

อินพุตและเอาต์พุต

Input: จำนวนแผ่น: 3
Output:
1. Move disk 1 from A to C
2. Move disk 2 from A to B
3. Move disk 1 from C to B
4. Move disk 3 from A to C
5. Move disk 1 from B to A
6. Move disk 2 from B to C
7. Move disk 1 from A to C

อัลกอริทึม

toh(n, s, a, d)
Input: จำนวนแผ่น, source, auxiliary, destination
Output: ขั้นตอนการย้ายแผ่นจาก source ไป destination ตามกฎ

Begin
    if n = 1, then
        display move disc from s to d
    toh(n-1, s, d, a)
    display move disc from s to d
    toh(n-1, a, s, d)
End

ตัวอย่างโค้ด (C++)

#include <iostream>
using namespace std;

void TOH(int n, char s, char a, char d) {
    static int count = 0;  // เก็บจำนวนการนับ
    if (n == 1) {
        count++;
        cout << count << ". Move disk " << n << " from " << s << " to " << d << endl;
        return;  // base case, เมื่อมีแผ่นเดียว
    }
    TOH(n-1, s, d, a);  // เรียกซ้ำฟังก์ชัน
    count++;
    cout << count << ". Move disk " << n << " from " << s << " to " << d << endl;
    TOH(n-1, a, s, d);
}

int main() {
    int n;
    cout << "Enter the number of disks: ";
    cin >> n;
    TOH(n, 'A', 'B', 'C');
}

ผลลัพธ์

Enter the number of disks: 3
1. Move disk 1 from A to C
2. Move disk 2 from A to B
3. Move disk 1 from C to B
4. Move disk 3 from A to C
5. Move disk 1 from B to A
6. Move disk 2 from B to C
7. Move disk 1 from A to C