The Tower of Hanoi is a classic mathematical puzzle that involves moving a set of disks from one rod to another, following specific rules:
The problem can be solved using recursion, where we break the problem into smaller subproblems and solve them step by step.
public class TowerOfHanoi {
// Recursive function to solve Tower of Hanoi
public static void solveHanoi(int n, char source, char auxiliary, char destination) {
if (n == 1) {
System.out.println("Move disk 1 from " + source + " to " + destination);
return;
}
// Move (n-1) disks from source to auxiliary using destination
solveHanoi(n - 1, source, destination, auxiliary);
// Move the nth disk from source to destination
System.out.println("Move disk " + n + " from " + source + " to " + destination);
// Move the (n-1) disks from auxiliary to destination using source
solveHanoi(n - 1, auxiliary, source, destination);
}
public static void main(String[] args) {
int n = 3; // Number of disks
System.out.println("Tower of Hanoi solution for " + n + " disks:");
solveHanoi(n, 'A', 'B', 'C'); // A = Source, B = Auxiliary, C = Destination
}
}
Tower of Hanoi solution for 3 disks:
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
n == 1
), we move it directly from the source to the destination.Since each move follows the rules, the entire stack of disks is moved correctly to the destination rod in minimal steps (2ⁿ – 1 moves for n disks).
The Tower of Hanoi is an excellent example of a recursive problem where a larger problem is broken into smaller subproblems. The recursive solution efficiently finds the optimal sequence of moves. However, as n
increases, the number of moves grows exponentially (O(2ⁿ) complexity
), making it impractical for very large values of n
.