Solving Tower of Hanoi Program in C
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.
Thus, 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.
FAQs
What is the Tower of Hanoi problem?
The Tower of Hanoi is a mathematical puzzle that consists of three rods and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top. The objective of the puzzle is to move the entire stack to another rod, obeying the following rules: 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 another stack, and no disk may be placed on top of a smaller disk.
How do you solve the Tower of Hanoi problem in C?
The Tower of Hanoi problem is typically solved using recursion in C. The recursive solution involves moving a smaller stack to the buffer rod, then moving the largest disk to the target rod, and finally moving the smaller stack from the buffer rod to the target rod.
What is the base case in the recursive solution for the Tower of Hanoi?
The base case for the Tower of Hanoi recursive solution is when there is only one disk to move. In this case, the disk can be directly moved to the target rod without needing further recursive calls.
How do you calculate the minimum number of moves required to solve the Tower of Hanoi for 'n' disks?
The minimum number of moves required to solve the Tower of Hanoi puzzle with 'n' disks is 2^n - 1. This is because each move effectively splits the problem into a smaller version of itself, doubling the number of moves required each time.
Can the Tower of Hanoi be solved iteratively?
Yes, the Tower of Hanoi can be solved iteratively using a stack-based approach or by following certain patterns and rules. However, the recursive solution is more intuitive and widely used due to its simplicity and direct mapping to the problem's nature.
Hello, world! I'm Esha Gupta, your go-to Technical Content Developer focusing on Java, Data Structures and Algorithms, and Front End Development. Alongside these specialities, I have a zest for immersing myself in v... Read Full Bio
Top Picks & New Arrivals
