Practice › Recursion & Backtracking
Tower of Hanoi
Medium · Recursion & Backtracking · Asked at TCS, Infosys, Wipro, Accenture, Cognizant
Move n disks from rod A to rod C using rod B. Only the top disk can move, and a larger disk can never be placed on a smaller one. Print the moves of the standard recursive solution, then the total number of moves.
Input
One integer n.
Output
Each move on its own line as Move disk d from X to Y, then a final line with the number of moves.
Constraints
- 1 ≤ n ≤ 8
hanoi(n, from, to, via): hanoi(n−1, from, via, to); move disk n; hanoi(n−1, via, to, from).
Example 1
Input
2
Output
Move disk 1 from A to B Move disk 2 from A to C Move disk 1 from B to C 3
Example 2
Input
1
Output
Move disk 1 from A to C 1
Hints
- To move the biggest disk n from A to C, the n − 1 disks above it must first be parked on B.
- hanoi(n, from, to, via) = hanoi(n−1, from, via, to); move disk n from → to; hanoi(n−1, via, to, from). Base case: n = 0 does nothing.
Approach
Trust the recursion. Move the top n − 1 disks out of the way (to the spare rod), move disk n to its target, then bring the n − 1 disks back on top of it. The number of moves satisfies T(n) = 2·T(n − 1) + 1, so T(n) = 2^n − 1. Print every move as the recursion makes it, then the count.
Complexity: O(2^n) time · O(n) recursion depth
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int moves = 0;
void hanoi(int n, char from, char to, char via) {
if (n == 0) return;
hanoi(n - 1, from, via, to);
cout << "Move disk " << n << " from " << from << " to " << to << "\n";
moves++;
hanoi(n - 1, via, to, from);
}
int main() {
int n;
cin >> n;
hanoi(n, 'A', 'C', 'B');
cout << moves << "\n";
return 0;
}Python solution
out = []
def hanoi(n, src, dst, via):
if n == 0:
return
hanoi(n - 1, src, via, dst)
out.append(f"Move disk {n} from {src} to {dst}")
hanoi(n - 1, via, dst, src)
n = int(input())
hanoi(n, "A", "C", "B")
out.append(str(len(out)))
print("\n".join(out))Java solution
import java.util.*;
public class Main {
static StringBuilder out = new StringBuilder();
static int moves = 0;
static void hanoi(int n, char from, char to, char via) {
if (n == 0) return;
hanoi(n - 1, from, via, to);
out.append("Move disk ").append(n).append(" from ").append(from).append(" to ").append(to).append('\n');
moves++;
hanoi(n - 1, via, to, from);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
hanoi(n, 'A', 'C', 'B');
out.append(moves);
System.out.println(out);
}
}