Tower of Hanoi Puzzle is a brainteaser that involves moving a stack of discs between three pegs, adhering to specific constraints. Let us read more about it!
The Tower of Hanoi is a classic mathematical puzzle. It consists of three rods (or pegs) and several disks which are of different sizes, which can slide onto any rod. The puzzle starts with the disks that are neatly stacked in ascending order of size on one rod, the smallest disk on top, thus forming a conical shape. Here, we will see a Tower of Hanoi Program in C.
Explore Online C Programming Courses
Objective :
The goal is to move the entire stack to another rod, following these very basic rules given below:
- Only one disk can be moved at a time.
- Each move consists of taking the upper disk from one of the stacks and placing it on top of the other.
- No disk may be placed on top of a smaller disk.
Source: Mathspp
Let’s Write a Simple C Program for Solving this Puzzle :
#include <stdio.h>
// Recursive C function to demonstrate the solution of the Tower of Hanoi problemvoid towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod){ if (n == 1) { printf("\n Shift disk 1 from peg %c to peg %c", from_rod, to_rod); return; } towerOfHanoi(n-1, from_rod, aux_rod, to_rod); printf("\n Shift disk %d from peg %c to peg %c", n, from_rod, to_rod); towerOfHanoi(n-1, aux_rod, to_rod, from_rod);}
int main(){ int n = 4; // Setting the count of disks towerOfHanoi(n, 'A', 'C', 'B'); // Here, A, B, and C represent the pegs' identifiers return 0;}
Output :
Shift disk 1 from peg A to peg B Shift disk 2 from peg A to peg C Shift disk 1 from peg B to peg C Shift disk 3 from peg A to peg B Shift disk 1 from peg C to peg A Shift disk 2 from peg C to peg B Shift disk 1 from peg A to peg B Shift disk 4 from peg A to peg C Shift disk 1 from peg B to peg C Shift disk 2 from peg B to peg A Shift disk 1 from peg C to peg A Shift disk 3 from peg B to peg C Shift disk 1 from peg A to peg B Shift disk 2 from peg A to peg C Shift disk 1 from peg B to peg C
The Tower of Hanoi puzzle with n disks can be solved in a minimum of 2n−1 steps. This presentation shows that a puzzle with 4 disks has taken 24 – 1 = 15 steps.
The output illustrates the solution to the Tower of Hanoi puzzle with 4 disks. Starting with all disks on peg A, the moves sequentially shift disks between pegs, ensuring a larger disk never lands on a smaller one. The steps gradually relocate the disks, with the largest disk (disk 4) reaching its target peg (peg C) midway through. The subsequent moves rearrange the smaller disks around it until all disks are stacked on peg C in their original order.
Thus, our puzzle is solved.
Conclusion :
The Tower of Hanoi program in C showcases the power of recursion to solve problems that might initially seem complex. This centuries-old puzzle demonstrates how breaking a problem down into simpler instances of itself can lead to an elegant solution. The C implementation effectively translates the iterative nature of the puzzle into clear code steps. By understanding this algorithm, one gains insights into the recursive problem-solving approach and appreciates the efficiency and simplicity with which C handles such challenges.
Download this article as PDF to read offline
Download as PDF
I'm Esha Gupta, a B.Tech graduate in Computer Science & Engineering, specializing in Front End Web Dev. I've interned at GeeksforGeeks & Coding Minutes, fueling my passion for crafting appealing and functional digit... Read Full Bio
Trending Technology Courses
Top Picks & New Arrivals
Comments