Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. To move the biggest disk n from A to C, the n − 1 disks above it must first be parked on B.
  2. 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);
    }
}

Solve Tower of Hanoi online · All practice problems