MENARA HANOI

MENARA HANOI ALGORITMA

Program permainan ( game ) merupakan salah satu implementasi dari   bidang  ilmu  komputer.  Perkembangan  permainan  pada  masa  kini  sudah sangat pesat dan telah menjadi mode tersendiri di dunia karena mayoritas pengguna komputer menghabiskan sebagian besar waktu mereka di depan   komputer dalam program permainan. Salah satu algoritma yang  digunakan  untuk  mengembangkan  program  permainan  adalah  algoritma berbasis  pohon  ruang  pencarian  (searching  algorithm).  Salah  satu  game yang  menggunakan  algoritma  berbasis  pohon  ruang  pencarian  dalam   menyelesaikan permainannya yaitu  menara hanoi. 

Menara Hanoi merupakan salah satu diantara berbagai teka-teki dalam matematika. Teka-teki ini ditemukan Edouard Lucas, ahli matematika Perancis di tahun 1883.Teka-teki ini berdasarkan pada sebuah cerita legenda tentang candi Indian atau menara Benares di India yang memiliki tiga tiang dan salah satu tiangnya terdapat 64 tumpukan cakram emas. Para pendeta mendapat tugas untuk memindahkan cakram emas itu ke tiang yang lain sesuai dengan suatu aturan. Tidak jelas apakah ini benar-benar legenda, atau inspirasi dari Lucas sendiri. Konon, Dewa Brahma menciptakan tiga tiang pada candi tersebut. Pada salah satu tiang terdapat tumpukan cakram emas sebanyak 64 keping, dengan urutan keping yang terbesar terletak di bawah, makin ke atas makin kecil. Selanjutnya Dewa Brahma memerintahkan para pendeta untuk memindahkan keping-keping emas itu dengan aturan : setiap perpindahan hanya boleh memindah 1 cakram dan cakram yang besar tidak boleh diletakkan di atas cakram yang lebih kecil. Dalam legenda itu dikatakan bahwa dunia akan berakhir jika para pendeta tersebut selesai memindahkan ke 64 cakram.

Dilihat  dari  karakteristik  persoalan  slide  puzzle ,  puzzle   ini  membentuk ruang  solusi  yang  diorganisasikan  ke  dalam  struktur  pohon  dinamis.   Struktur pohon dinamis sendiri dibangun dengan 2 metode traversal yaitu   Breadth  First  Search   (BFS)  dan  Depth  First  Search   (DFS)  [MUN04].   Untuk itu penulis menerapkan algoritma Depth   First Search dalam menyelesaikan permainan  menara hanoi .

Hanoi sendiri adalah sebuah permainan dimana sejumlah piringan dipindahkan dari tonggak satu ke tonggak lainnya dan dapat menggunakan tonggak bantuan .

 Caranya semua piringan di tonggak A akan dipindahkan ke tonggak C secara satu persatu dan piringan yang besar tidak boleh diletakkan di atas piringan yang kecil.

Untuk lebih jelasnya soal prosesnya bisa lihat gambar di bawah ini 

Untuk menyelesaikan puzzle di atas dalam pemrograman, kita dapat menggunakan teknik rekursif. Rekursif adalah fungsi atau prosedure yang dapat memanggil dirinya sendiri.
Jadi algoritmanya adalah

Kalau N = 1 maka                                                       catatan :

N dipindahkan dari A ke C secara langsung              N = banyaknya piringan

Tapi kalau N > 1 maka

pindahkan N-1 dari A ke B

pindahkan N dari A ke C

pindahkan N-1 dari B ke C

Dan inilah adalah program dari code blok :

#include <iostream>

using namespace std;

void MenaraHanoi(int N, char asal, char bantu, char tujuan);

int main()

{

    int p;

    cout<<"------- Selamat datang di program------"<<endl;

    cout<< "---------PROGRAM MENARA HANOI--------\n";

    cout<< "Masukkan Banyaknya piringan: ";

    cin >> p;

    cout<< endl;

    MenaraHanoi(p,'A','B','C');

    cout<<endl;

    cout<<"create by: Muhammad Nur Fauzi\n";

    return 0;

}

void MenaraHanoi(int z, char asal, char bantu, char tujuan)

{

    if(z == 1)

        cout<<"Piringan 1 dari "<<asal<< " ke " << tujuan <<endl;

    else

    {

        MenaraHanoi(z-1,asal,tujuan, bantu);

        cout<<"Piringan " << z <<" dari " << asal << " ke " << tujuan<<endl;

        MenaraHanoi(z-1, bantu, asal, tujuan);

    }

}

Dan di bawah ini adalah hasil dari pemograman di atas,