Algoritma Menara Hanoi

Menara Hanoi merupakan sebuah permainan teka-teki matematis dengan menggunakan tiga buah tiang dan sejumlah n cakram yang berbeda-beda ukurannya. Tiga buah tiang itu bisa disebut sebagai menara asal, menara bantu dan menara tujuan. Permainan ini dimulai dengan semua cakram tersusun rapi di menara asal, cakram terbesar di bawah dan cakram terkecil di atas. Goal dari permainan ini adalah memindahkan semua cakram dari menara asal ke menara tujuan dengan bantuan menara bantuan, dengan langkah yang sesingkat mungkin, tapi dengan syarat :

1. Hanya satu cakram yang bisa dipindah dalam satu kesempatan
2. Cakram yang dipindah harus diletakkan di tempat teratas pada menara lain
3. Cakram yang terkecil di tiap menara harus berada pada posisi paling atas

Menurut cerita, permainan ini sering dimainkan oleh biarawan-biarawan di Hanoi. Menurut legenda, jika ada yang bisa menyelesaikan permainan ini dengan menggunakan n=64 cakram, maka dunia akan kiamat.

Pada mata kuliah Algoritma Pemrograman yang membahas bahasan tentang Algoritma Rekursif, problem menara Hanoi menjadi sesuatu yang harus bisa dipecahkan. Berikut merupakan algoritma untuk menyelesaikan permasalahan Menara Hanoi dengan menggunakan bahasa Java.

import javax.swing.JOptionPane;

public class TugasHanoi{

static int i=0;

public static int Hanoi(int N,char asal, char bantu, char tujuan){

if (N==1){

i++;

System.out.println(“Langkah ke “+i+” Pindahkan Piringan “+N+” dari “+asal+” ke “+tujuan);

return 0;

}

Hanoi(N-1, asal, tujuan, bantu);

i++;

System.out.println(“Langkah ke “+i+ ” Pindahkan Piringan “+N+” dari “+asal+” ke “+tujuan);

Hanoi(N-1, bantu, asal, tujuan);

return 0;

}

public static void main(String[] args){

int N;

String input=JOptionPane.showInputDialog

(“Masukkan Jumlah Piringan”);

N=Integer.parseInt(input);

Hanoi(N,’A',’B',’C');

}

}

Output :

Langkah ke 1 Pindahkan Piringan 1 dari A ke C

Langkah ke 2 Pindahkan Piringan 2 dari A ke B

Langkah ke 3 Pindahkan Piringan 1 dari C ke B

Langkah ke 4 Pindahkan Piringan 3 dari A ke C

Langkah ke 5 Pindahkan Piringan 1 dari B ke A

Langkah ke 6 Pindahkan Piringan 2 dari B ke C

Langkah ke 7 Pindahkan Piringan 1 dari A ke C

Langkah ke 8 Pindahkan Piringan 4 dari A ke B

Langkah ke 9 Pindahkan Piringan 1 dari C ke B

Langkah ke 10 Pindahkan Piringan 2 dari C ke A

Langkah ke 11 Pindahkan Piringan 1 dari B ke A

Langkah ke 12 Pindahkan Piringan 3 dari C ke B

Langkah ke 13 Pindahkan Piringan 1 dari A ke C

Langkah ke 14 Pindahkan Piringan 2 dari A ke B

Langkah ke 15 Pindahkan Piringan 1 dari C ke B

Langkah ke 16 Pindahkan Piringan 5 dari A ke C

Langkah ke 17 Pindahkan Piringan 1 dari B ke A

Langkah ke 18 Pindahkan Piringan 2 dari B ke C

Langkah ke 19 Pindahkan Piringan 1 dari A ke C

Langkah ke 20 Pindahkan Piringan 3 dari B ke A

Langkah ke 21 Pindahkan Piringan 1 dari C ke B

Langkah ke 22 Pindahkan Piringan 2 dari C ke A

Langkah ke 23 Pindahkan Piringan 1 dari B ke A

Langkah ke 24 Pindahkan Piringan 4 dari B ke C

Langkah ke 25 Pindahkan Piringan 1 dari A ke C

Langkah ke 26 Pindahkan Piringan 2 dari A ke B

Langkah ke 27 Pindahkan Piringan 1 dari C ke B

Langkah ke 28 Pindahkan Piringan 3 dari A ke C

Langkah ke 29 Pindahkan Piringan 1 dari B ke A

Langkah ke 30 Pindahkan Piringan 2 dari B ke C

Langkah ke 31 Pindahkan Piringan 1 dari A ke C