The Hanoi Towers Problem

Hanoi Towers

The Towers of Hanoi is a mathematical game that resembles a puzzle but is played according to specific rules. It consists of three rods and a number of disks of different sizes, N. The game starts as shown below, with the disks arranged on the leftmost rod in ascending order of size. The objective is to move all the disks to another rod using the least number of moves possible. The rules to be followed while playing the game are as follows:

• Each move consists of taking the top disk from one of the rods and moving it to another rod. There may already be disks on the other rod.

• Only one disk can be moved at a time.

• No disk may be placed on top of a smaller disk.

• Disks can be moved freely among the three rods.

The Towers of Hanoi is a puzzle that Computer Science students are certain to encounter in their Algorithm Design or Data Structures courses.

Solution of the Towers of Hanoi in the C Programming Language

Programming is essentially about algorithms. To write the code for this problem, we first need to understand the working principle (solution method) of the Towers of Hanoi. Within our rules, we take a pen and paper and think about how to do it, and we find a very simple algorithm:

Let's say we have N disks, and if the number of operations to move N-1 of these disks is x, then the number of operations to move N disks will be 2x + 1.

This is how it works:

First, the N disks are moved from rod 1 to rod 2, which means we perform x operations.

Then, the Nth disk is moved from rod 1 to rod 3.

After that, the N - 1 disks on rod 2 are moved to rod 3 (x more operations).

The principle here is the same whether for a single disk or for 15 disks. However, if a person tries to solve this game within a limited number of moves, it would take a long time even to move 8 disks to another tower... It is virtually impossible for a person to transfer 15 disks from one rod to another even in 5 days.

So, we decided to tackle this problem with the help of a computer and used the C programming language for our solution. We utilized a state-of-the-art computer for our calculations. (Pentium Dual-Core inside E2200, Dual-core, 2.00 GHz, 1 GB RAM, 100 GB Hard Disk)

The Code:

#include<stdio.h>

FILE *oku,*yaz;

int DS;

void Oku()

{

                                 oku=fopen("hanoi.in","r");

                                 yaz=fopen("hanoi.out","w");

                                 fscanf(oku,"%d",&DS);

}

void Yap(int yer,int hedef,int N)

{

                                 if(N==1)

                                 {

                                                                                fprintf(yaz,"%d %c %c\n",N,yer,hedef);

                                                                                return;

                                 }

                                 int diger=198-(yer+hedef);

                                 Yap(yer,diger,N-1);

                                 fprintf(yaz,"%d %c %c\n",N,yer,hedef);

                                 Yap(diger,hedef,N-1);

                                 return ;

}

int main()

{

                                 Oku();

                                 Yap(65,67,DS);

                                 return 0;

}

Now, let's explain the algorithm we found earlier in more detail:

First, consider for N disks.

• If N=1, we can directly move the disk to its target location.

• If we can also find a solution in terms of (N-1) disks, we can utilize recursion to find the solution for N disks.

If we generalize the algorithm for every N value, the part of the program that solves the question would be as follows:

• If N=1, print the size of the disk, its current location, and its destination, then finish.

• Move the top N-1 disks to the other rod, away from the Nth disk.

• Print the size of the Nth disk, its current location, and its destination.

• Move the (N-1) disks from the other rod back to their destination, on top of the Nth disk.

For N=3, consider "source", "destination", and "auxiliary" as the labels for the movements.

When we compiled and ran the above codes for 3 disks, we obtained the following sequence of moves:

• Move disk 1 from tower A to tower C.

• Move disk 2 from tower A to tower B.

• Move disk 1 from tower C to tower B.

• Move disk 3 from tower A to tower C.

• Move disk 1 from tower B to tower A.

• Move disk 2 from tower B to tower C.

• Move disk 1 from tower A to tower C.

This sequence illustrates the process of moving 3 disks according to the rules and algorithm of the Towers of Hanoi puzzle, demonstrating the recursive nature of the solution.

Bilgisayarın 3 disk için bize verdiği sonuç aşağıdaki gibidir:

1 A C                 /* 1. diski A kulesinden alıp C kulesine yerleştir */

2 A B                 /* 2. diski A kulesinden alıp B kulesine yerleştir */

1 C B                 /* 1. diski C kulesinden alıp B kulesine yerleştir */

3 A C                 /* 3. diski A kulesinden alıp C kulesine yerleştir */

1 B A                 /* 1. diski B kulesinden alıp A kulesine yerleştir */

2 B C                        /* 2. diski B kulesinden alıp C kulesine yerleştir */

1 A C                 /* 1. diski A kulesinden alıp C kulesine yerleştir */

 Yukarıdaki kodları derleyip çalıştırdığımızda aşağıdaki tabloyu elde ettik: