MENARA HANOI

        Pemrograman dinamis (dynamic programming) adalah metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan (stage) sedemikian rupa sehingga solusi dari permasalahan ini dapat dipandang dari serangkaian keputusan-keputusan kecil yang saling berkaitan satu dengan yang lain. Penyelesaian persoalan dengan pemrograman dinamis ini akan menghasilkan sejumlah berhingga pilihan yang mungkin dipilih, lalu solusi pada setiap tahap-tahap yang dibangun dari solusi pada tahap sebelumnya, dan dengan metode ini kita menggunakan persyaratan optimasi dan kendala untuk membatasi sejumlah pilihan yang harus dipertimbangkan pada suatu tahap.

    

Permainan Menara Hanoi (Tower of Hanoi), disebut juga Tower of Brahma atau Tower of Brahmas, adalah sebuah permainan matematis atau teka-teki. Permainan ini terdiri dari tiga tiang dan sejumlah cakram dengan ukuran berbeda-beda yang bisa dimasukkan ke tiang mana saja. Permainan dimulai dengan cakram-cakram yang tertumpuk rapi berurutan berdasarkan ukurannya dalam salah satu tiang, cakram terkecil diletakkan teratas, sehingga membentuk kerucut. Permainan ini dimulai dengan kepingan yang tersusun dengan susunan seperti gambar dibawah ini:  

dengan kepingan berdiameter terkecil berada di atas, dan membentuk piramida. Tujuan dari permainan ini adalah untuk memindahkan semua stack ke tiang yang berbeda dengan posisi yang sama seperti posisi semula. Permainan Permainan Menara Hanoi (Tower of Hanoi), atau disebut juga Tower of Brahma (Tower of Brahmas) merupakan sebuah permainan matematika yang kuno, dibuat oleh matematikawan dari prancis, Edouard Lucas pada tahun 1883.

Ada sebuah legenda tentang candi Indian yang berisi ruang besar dengan tiga tiang yang dikelilingi 64 cakram emas. Pendeta Brahma, melaksanakan tugas dari peramal di masa lalu, sesuai dengan aturan teka-teki ini. Menurut legenda ini, bila teka-teki ini diselesaikan, dunia akan kiamat. Tidak jelas benar apakah Lucas menemukan legenda ini atau terinspirasi olehnya. Bila legenda ini benar, dan pendeta itu bisa memindahkan satu cakram tiap detik, menggunakan pemindahan paling sedikit, maka akan memakan waktu 2⁶⁴−1 detik atau kurang lebih 584,582 miliar tahun.

Soal dari permainan ini dalam bahasa inggris tertulis demikian:

“Legend has it that a group of Eastern monks are the keepers of three towers on which sit 64 golden rings. Originally all 64 rings were stacked on one tower with each ring smaller than the one beneath. The monks are to move the rings from this first tower to the third tower one at a time but never moving a larger ring on top of a smaller one. Once the 64 rings have all been moved, the world will come to an end”. 

Sudah banyak tertulis di berbagai sumber bahwa solusi optimal untuk permasalahan ini adalah gerakan. Dengan asumsi satu gerakan akan memakan waktu 1 detik, maka dengan perhitungan singkat akan didapat bahwa untuk Menara Hanoi dengan ketinggian 64 akan memakan waktu sampai tahun.

Atau dapat ditawarkan lagi soal lain:

“Take only 5 rings and try all possible solutions. Then the Universe will come to an end”.

Jika kita mengambil asumsi bahwa setiap solusi (yang memiliki biaya yang berbeda) hanya satu detikpun, akan memakan waktu hingga tahun untuk mencoba semua kemungkinan solusi. Terlalu banyak waktu untuk membuat kemungkinan terjadi Big Bang berkali-kali.

Bahkan, untuk bahan lelucon, hingga ditawarkan soal seperti ini:

“Take only 4 rings and let each human on Earth solve the game in different way. When all different solutions are used the Universe will come to an end”.

      Demikian sejarah yang membuat permainan ini menarik untuk orang-orang pada jaman itu. Dan dalam berjalannya waktu hingga sekarang banyak ahli yang mencoba menerapkan banyak algoritma untuk menyelesaikan permasalahan Menara Hanoi ini.

Permainan ini terdiri dari sebuah papan main yang diatasnya sudah tertancap tiga tiang dengan ketinggian yang sama. Selain itu, kakas lain dalam permainan ini adalah kepingan-kepingan lingkaran dengan diameter yang berbeda dan dapat berpindah ke tiang yang lain. Permainan ini dimulai dengan kepingan yang tersusun dengan susunan yang sudah ditentukan, yaitu kepingan berdiameter terkecil berada di atas, dan membentuk piramida. Tujuan dari permainan ini adalah untuk memindahkan semua tumpukan kepingan ke tiang yang berbeda, dengan posisi yang sama seperti posisi semula.

     Ada beberapa aturan yang telah ditetapkan untuk menyelesaikan permainan ini, antara lain:

 Hanya satu kepingan puzzle yang boleh dipindahkan oleh pemain pada satu giliran.

 Setiap giliran gerakan terdiri dari memindahkan kepingan paling atas yang terdapat pada satu tiang, dan memasukkan kepingan tersebut ke tiang lain, sehingga kepingan tersebut menjadi kepingan paling atas di tiangnya yang baru, baik dibawahnya ada kepingan maupun tidak.

Sebuah kepingan tidak dapat dipindahkan ke tiang yang lain apabila pada puncak tumpukan di tiang tersebut terdapat kepingan dengan ukuran diameter yang lebih kecil daripada kepingan yang ingin dipindahkan.

Untuk memainkan permainan ini, silahkan klik (menara hanoi).

Sumber : siomah.blogspot.com/2012/03/tower-of-hanoi-description.html

              id.wikipedia.org/wiki/Menara_Hanoi

              http://p4tkmatematika.org/permainan/Html/Permainan/menara_hanoi.htm