Implementasi Rekursi Menara Hanoi – Bahasa C

Permainan Tower of Hanoi atau Menara Hanoi merupakan permainan klasik yang sudah sangat sering digunakan sebagai contoh permasalahan yang dapat diselesaikan dengan cara rekursi.

Secara singkat Menara Hanoi adalah permainan untuk memindahkan n piringan dari tiang A ke tiang C dengan tiang bantu B, dimana kepingan yang lebih besar harus berada di bawah kepingan yang lebih kecil.

Gambaran Menara Hanoi

Ini adalah cara penyelesaian Menara Hanoi atau Tower of Hanoi secara rekursif beserta animasi tiap pergerakannya :

#include <stdio.h>      //definisi printf,scanf
#include <conio.h>      //definisi getch
#include <stdlib.h>     //definisi system
#include <windows.h>    //definisi Sleep

int initialize(int arr1[],int x[]);
void print(int arr1[],int arr2[],int arr3[],int x[]);
void Hanoi(int arr1[],int arr2[],int arr3[],int x[],int n,char asal,char bantu,char tujuan);

int main()
{
    int n;
    int arr1[100],
        arr2[100],
        arr3[100],
        x[3] = {0,0,0};

    n = initialize(arr1,x);
    print(arr1,arr2,arr3,x);
    Hanoi(arr1,arr2,arr3,x,n,'A','B','C');
    getch();
    return 0;
}

int initialize(int arr1[],int x[]){
     int n;
     while (true){
         system("cls");
         printf("= = = = | T O W E R   O F   H A N O I - tutorialpemrograman.wordpress.com | = = = =\n\n");
         printf("Jumlah Kepingan :  ");
         if (scanf("%d",&n) == 1 ) break;
         fflush(stdin);
     }
     puts("");
     for (int i=n;i>=1;i--){
        arr1[x[0]++] = i;
     }
     return n;
}

void print(int arr1[],int arr2[],int arr3[],int x[]){
     int i,
         j = 0;
     for (j=0;j<3;j++){
         if (j == 0)printf("A : ");
         if (j == 1)printf("B : ");
         if (j == 2)printf("C : ");
         for (i=0;i<x[j];i++){
             if (j == 0) printf("%3d",arr1[i]);
             if (j == 1) printf("%3d",arr2[i]);
             if (j == 2) printf("%3d",arr3[i]);
         }
         printf("\n");
     }
     printf("\n");
}

// pindahkan piringan ke n dari asal menuju tujuan melalui bantu
void Hanoi(int arr1[],int arr2[],int arr3[],int x[],int n,char asal,char bantu,char tujuan)
{ 

    if (n == 0) return;
    //pindahkan piringan ke n-1 dari asal ke bantu melalui tonggak tujuan
    Hanoi(arr1,arr2,arr3,x,n-1,asal,tujuan,bantu); 

    printf("... Memindahkan kepingan ke-%d dari %c ke %c ...\n\n",n,asal,tujuan);
    x[asal-65] -= 1;
    switch (tujuan){
           case 'A' :
                arr1[x[0]++] = n;
                break;
           case 'B' :
                arr2[x[1]++] = n;
                break;
           case 'C' :
                arr3[x[2]++] = n;
                break;
    }
    print(arr1,arr2,arr3,x);
    Sleep(1000);
    //pindahkan piringan ke n – 1 dari bantu menuju tujuan melalui asal
    Hanoi(arr1,arr2,arr3,x,n-1,bantu,asal,tujuan);
}

Langkah-langkah pemanggilan fungsi rekursinya adalah sebagai berikut :

3 A B C
	2 A C B
		1 A B C
			0 A C B
		1 A B C
		Pindahkan piringan ke 1 ke dari A ke C
			0 C A B
		1 A B C
	2 A C B
	Pindahkan piringan ke 2 ke dari A ke B
		1 C A B
			0 C B A
		1 C A B
		Pindahkan piringan ke 1 dari C ke B
			0 A C B
		1 C A B
	2 A C B
3 A B C
Pindahkan piringan ke 3 ke dari A ke C
	2 B A C
		1 B C A
			0 B A C
		1 B C A
		Pindahkan piringan ke 1 ke dari B ke A
			0 C B A
		1 B C A
	2 B A C
	Pindahkan piringan ke 2 ke dari B ke C
		1 A B C
			0 A C B
		1 A B C
		Pindahkan piringan ke 1 dari A ke C
			0 B A C
		1 A B C
	2 B A C
3 A B C