Permainan Menara Hanoi (Tower of Hanoi)

Penjelasan Permainan

Menara Hanoi adalah permainan puzzle matematika yang terdiri dari:

Komponen:

3 tiang (A, B, C) atau disebut: sumber, bantuan, dan tujuan
n buah piringan dengan ukuran berbeda, ditumpuk dari yang terbesar di bawah hingga terkecil di atas pada tiang A

Tujuan:

Memindahkan seluruh tumpukan piringan dari tiang A (sumber) ke tiang C (tujuan)

Aturan:

Hanya satu piringan yang dapat dipindahkan dalam satu waktu
Piringan yang lebih besar tidak boleh diletakkan di atas piringan yang lebih kecil
Hanya piringan paling atas dari suatu tiang yang boleh dipindahkan
Tiang B dapat digunakan sebagai tiang bantuan sementara

Ilustrasi Permainan (n = 3)

Keadaan Awal:
Tiang A      Tiang B      Tiang C
  |            |            |
 [1]           |            |
 [2]           |            |
 [3]           |            |
=====        =====        =====

Langkah-langkah:
1. Pindah piringan 1: A → C
2. Pindah piringan 2: A → B
3. Pindah piringan 1: C → B
4. Pindah piringan 3: A → C
5. Pindah piringan 1: B → A
6. Pindah piringan 2: B → C
7. Pindah piringan 1: A → C

Keadaan Akhir:
Tiang A      Tiang B      Tiang C
  |            |            |
  |            |           [1]
  |            |           [2]
  |            |           [3]
=====        =====        =====

Total: 7 langkah = 2³ - 1

Algoritma Rekursif

def hanoi(n, asal, tujuan, bantuan):
    if n == 1:
        print(f"Pindahkan piringan 1 dari {asal} ke {tujuan}")
    else:
        # Langkah 1: Pindahkan n-1 piringan dari asal ke bantuan
        hanoi(n-1, asal, bantuan, tujuan)
        
        # Langkah 2: Pindahkan piringan terbesar dari asal ke tujuan
        print(f"Pindahkan piringan {n} dari {asal} ke {tujuan}")
        
        # Langkah 3: Pindahkan n-1 piringan dari bantuan ke tujuan
        hanoi(n-1, bantuan, tujuan, asal)

Mengapa Big-Oh adalah O(2ⁿ)?

Analisis Rekursif

Mari kita definisikan T(n) sebagai jumlah langkah yang diperlukan untuk memindahkan n piringan.

Kasus Dasar:

T(1) = 1 (hanya perlu 1 langkah untuk memindahkan 1 piringan)

Kasus Rekursif (n > 1):

Untuk memindahkan n piringan:

Pindahkan n-1 piringan dari tiang asal ke tiang bantuan → T(n-1) langkah
Pindahkan 1 piringan terbesar dari tiang asal ke tiang tujuan → 1 langkah
Pindahkan n-1 piringan dari tiang bantuan ke tiang tujuan → T(n-1) langkah

Sehingga:

T(n) = T(n-1) + 1 + T(n-1)
T(n) = 2·T(n-1) + 1

Penyelesaian Relasi Rekurensi

Relasi: T(n) = 2·T(n-1) + 1, dengan T(1) = 1

Mari kita hitung beberapa nilai:

T(1) = 1
T(2) = 2·T(1) + 1 = 2·1 + 1 = 3
T(3) = 2·T(2) + 1 = 2·3 + 1 = 7
T(4) = 2·T(3) + 1 = 2·7 + 1 = 15
T(5) = 2·T(4) + 1 = 2·15 + 1 = 31

Pola yang terlihat:

T(1) = 2¹ - 1 = 1
T(2) = 2² - 1 = 3
T(3) = 2³ - 1 = 7
T(4) = 2⁴ - 1 = 15
T(5) = 2⁵ - 1 = 31

Rumus Umum:

T(n) = 2ⁿ - 1

Pembuktian dengan Induksi Matematika

Teorema: T(n) = 2ⁿ - 1

Basis Induksi (n = 1):

T(1) = 1
2¹ - 1 = 2 - 1 = 1 ✓

Hipotesis Induksi: Asumsikan T(k) = 2^k - 1 benar untuk k = n-1

Langkah Induksi: Buktikan T(n) = 2ⁿ - 1

T(n) = 2·T(n-1) + 1                    [dari relasi rekurensi]
     = 2·(2^(n-1) - 1) + 1             [substitusi hipotesis]
     = 2^n - 2 + 1
     = 2^n - 1                         ✓

Terbukti bahwa T(n) = 2ⁿ - 1

Kesimpulan Big-Oh

Karena T(n) = 2ⁿ - 1, maka:

T(n) = 2ⁿ - 1 < 2ⁿ

Dengan memilih konstanta c = 1 dan n₀ = 1:

T(n) = 2ⁿ - 1 ≤ 1·2ⁿ untuk semua n ≥ 1

Oleh karena itu, T(n) = O(2ⁿ)

Tabel Pertumbuhan Kompleksitas

n	T(n) = 2ⁿ - 1	Waktu (jika 1 detik/langkah)
3	7	7 detik
5	31	31 detik
10	1,023	~17 menit
20	1,048,575	~12 hari
30	1,073,741,823	~34 tahun
64	18,446,744,073,709,551,615	~584 miliar tahun

Ini menunjukkan bahwa kompleksitas eksponensial O(2ⁿ) membuat permainan Menara Hanoi dengan jumlah piringan besar menjadi tidak praktis untuk diselesaikan!

Mengapa Tidak Bisa Lebih Cepat?

Menara Hanoi memiliki kompleksitas optimal O(2ⁿ) karena:

Setiap piringan harus dipindahkan setidaknya sekali
Untuk memindahkan piringan terbesar, semua piringan di atasnya harus dipindahkan dua kali (ke tiang bantuan, lalu ke tiang tujuan)
Tidak ada cara untuk "memotong" langkah-langkah ini tanpa melanggar aturan permainan
Ini adalah batas bawah (lower bound) yang tidak dapat dihindari

Menara Hanoi adalah contoh klasik dari masalah yang secara inheren eksponensial dan tidak dapat diselesaikan lebih efisien.

Tower Of Hanoi