Menara Hanoi: Contoh Klasik Rekursi

Oleh Samuel Wirajaya (website)

Co-founder, Acutis Academy. Software Engineer eks-FAANG, penggemar UNIX & Linux.

Demonstrasi Snap! di atas menunjukkan permainan Menara Hanoi secara visual. Mungkin beberapa sudah mengenal permainan ini, tapi masih ragu dengan solusinya, yang akan kita bahas sekarang ini.

Selain digunakan dalam menghitung faktorial dari sebuah angka, rekursi juga digunakan untuk memecahkan teka-teki Menara Hanoi. Sekilas kelihatan sulit, tapi dengan rekursi, solusinya jadi super elegan.

Apa itu Menara Hanoi?

Sebelum saya mendirikan Acutis Academy, di ruang istirahat kantor saya ada mainan kayu yang terdiri dari tiga tiang tegak, dan piringan-piringan yang ukurannya macam-macam. Semua piringan ada lubang di tengahnya sehingga bisa dimasukkan ke tiga tiang itu dalam berbagai rupa susunan.

Seperti yang gambar ini tunjukkan, Menara Hanoi adalah teka-teki matematika yang menggunakan mainan kayu tersebut. Dalam teka-teki ini, piringan-piringan tersebut pertama-tama disusun di tiang pertama hingga bentuknya seperti kerucut. Banyaknya piringan (yang kita bisa sebut dengan N) bisa diatur sesuai dengan tingkat kesulitan yang diinginkan.

Lalu, setelah menaranya disusun seperti Gambar 2, tugasnya adalah memindahkan semua piringan tersebut ke tiang ketiga. Tetapi ada dua aturan yang membuat teka-teki ini menjadi sulit:

• Piring-piring tersebut hanya bisa dipindahkan satu demi satu.
• Piring yang lebih besar tidak boleh ditumpuk di atas piring yang lebih kecil.

Solusi Menara Hanoi

Seperti yang kita ketahui, rekursi membutuhkan kasus dasar dan langkah rekursif, seperti yang dibahas dalam Rekursi: Konsep dan Penerapannya.

Jadi, kita bisa mencoba mendekati permasalahan ini dengan strategi seperti kita main game atau makan keripik pedas: kita coba mulai dari Level 1. Inilah yang akan menjadi kasus dasar rekursi kita.

Kasus dasar

Dalam kasus N = 1, hanya ada 1 piring yang perlu dipindahkan dari piring pertama ke piring ketiga, maka solusinya sangat mudah: kita tinggal pindahkan satu piring itu dari tiang pertama ke tiang ketiga.

Solusi Menara Hanoi untuk memindahkan N = 1 piring dari tiang awal ke tiang akhir dengan bantuan tiang aux bisa ditulis dalam kode Python sebagai berikut:

def solusiHanoi(N, awal, akhir, aux):
    if N == 1:
        # Tiang bantuan aux tidak perlu digunakan.
        return [{"dari": awal, "ke": akhir}]
    else:
        return "???"

# Contoh menjalankan kode di atas:
>>> solusiHanoi(N=1, from=1, to=3, aux=2)
[{'dari': 1, 'ke': 3}]
>>>

Membangun langkah rekursif

Sejauh ini oke-oke saja, tetapi bagaimana caranya kalau kita punya N = 2 piring? Caranya adalah, kita singkirkan dulu piring kecil ke tiang aux, lalu kita pindahkan piring besar ke tiang akhir, lalu piring kecilnya baru kita pindahkan dari tiang aux ke tiang akhir.

def solusiHanoi(N, awal, akhir, aux):
    if N == 1:
        # Tiang bantuan aux tidak perlu digunakan.
        return [{"dari": awal, "ke": akhir}]
    elif N == 2:
        return [
            # Singkirkan piring kecil yang ada di paling atas ke tiang aux
            {"dari": awal, "ke": aux},
            # Pindahkan piring besar ke tiang akhir
            {"dari": awal, "ke": akhir},
            # Taruh piring kecil di atas piring besar di tiang akhir
            {"dari": aux, "ke": akhir},
        ]
    else:
        return "???"

Beberapa dari Anda yang menyimak mungkin bertanya: Mana rekursinya?

Perhatikan bahwa kita bisa membangun solusi untuk Level N kalau kita mengetahui solusi untuk Level N - 1. Maka berdasarkan solusi untuk N = 2 di atas, bisa kita buat versi umumnya dengan langkah-langkah:

1. Singkirkan dulu yang ada di atas piring paling besar, dengan cara memindahkan N - 1 piring ke tiang aux, menggunakan tiang akhir sebagai tiang bantuan.
2. Pindahkan piring paling besar dari tiang awal ke tiang akhir.
3. Pindahkan N - 1 piring yang kita sudah singkirkan tadi ke atas piring yang paling besar. Dalam kata lain, kita memindahkan N - 1 piring dari tiang aux ke tiang akhir, menggunakan tiang awal sebagai tiang bantuan.

Kita tidak bisa memindahkan N - 1 piringan secara sekaligus, karena kita harus memindahkan piring satu per satu. Maka untuk memecahkan Menara Hanoi dengan N piring, kita menggunakan solusi yang berlaku untuk N - 1 sesuai Langkah 1 dan Langkah 3 di atas. Maka di sinilah kita melihat langkah rekursifnya, seperti dalam kode Python berikut.

def solusiHanoi(N, awal, akhir, aux):
    if N == 1:
        # Tiang bantuan aux tidak perlu digunakan.
        return [{"dari": awal, "ke": akhir}]
    else:
        return (
          # Singkirkan yang di atas Piring N
            solusiHanoi(N - 1, awal, aux, akhir)
          # Lalu pindahkan piring N
          + [{"dari": awal, "ke": akhir}]
          # Lalu taruh yang tadi disingkirkan di tiang akhir
          + solusiHanoi(N - 1, aux, akhir, awal)
        )

def printSolusi(N):
    for langkah in solusiHanoi(N, awal=1, akhir=3, aux=2):
        print(f"{langkah['dari']} -> {langkah['ke']}")

# Contoh keluaran setelah menjalankan kode di atas:
>>> printSolusi(N=4)
1 -> 2
1 -> 3
2 -> 3
1 -> 2
3 -> 1
3 -> 2
1 -> 2
1 -> 3
2 -> 3
2 -> 1
3 -> 1
2 -> 3
1 -> 2
1 -> 3
2 -> 3

Jadi, kode Python di atas menunjukkan solusi Menara Hanoi untuk berbagai macam N. Selain itu demonstrasi Snap! di awal artikel juga memanfaatkan rekursi untuk memvisualisasikan Menara Hanoi.

Kesimpulan

Menara Hanoi adalah contoh klasik teka-teki matematika yang agak ribet untuk diselesaikan, kecuali jika menggunakan konsep rekursi. Dan dengan menerapkan rekursi, solusi Menara Hanoi bisa diformulasikan dengan cara yang relatif mudah, karena solusi untuk Level N bisa dinyatakan dalam solusi untuk Level N - 1.

Walaupun hal ini hanyalah bersifat teka-teki untuk mengasah otak, terdapat suatu keindahan yang timbul dari aturan-aturan yang sederhana. Saya berharap bahwa kita bisa melihat indahnya rekursi melalui demonstrasi solusi Menara Hanoi dan pembahasan di atas.

Konsep rekursi juga dapat digunakan untuk membuat algoritma pengurutan (sort) yang lebih cepat dari insertion sort yang akan kita bahas dalam kesempatan berikutnya. Maka stay tuned!