Tower of Hanoi

medium Recursion and Backtracking

There are three pegs A, B and C. n disks lie on peg A (disk 1 is the smallest). Move all disks to peg C. A bigger disk may never lie on a smaller disk. Read n and print the moves, one per line, in the form Move disk d from X to Y. Use the standard recursive solution.

Constraints

1 <= n <= 10

Examples

Input

Output

Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C

Recursion
Base case
Exponential growth

Solutions

Best approachTime O(2^n)Space O(n)

To move n disks from A to C: (1) move n - 1 disks from A to B, (2) move the biggest disk from A to C, (3) move the n - 1 disks from B to C. Each of the two smaller problems is the same problem with n - 1. The total is 2^n - 1 moves.

Same code works in Java810172125Basic features only, so nothing changes between versions.

/*
 * Problem : Solve Tower of Hanoi.
 * Input   : One integer n.
 * Output  : The list of moves.
 * Approach: Move n - 1 disks away first.
 * Time    : O(2^n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // This method moves "count" disks from peg "from" to peg "to". It uses peg "via" as the helper peg.
        static void move(int count, char from, char to, char via, java.util.List<String> moves) {
            // Step 1: With 0 disks there is nothing to do. This is the base case.
            if (count == 0) {
                return;
            }

            // Step 2: Move the top count - 1 disks out of the way, to the helper peg.
            move(count - 1, from, via, to, moves);

            // Step 3: Move the biggest disk to the target peg.
            moves.add("Move disk " + count + " from " + from + " to " + to);

            // Step 4: Move the count - 1 disks from the helper peg onto the biggest disk.
            move(count - 1, via, to, from, moves);
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(long n) {
        java.util.List<String> moves = new java.util.ArrayList<>();
        move((int) n, 'A', 'C', 'B', moves);
        return moves.toArray(new String[0]);
    }

    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        System.out.println(String.join("\n", solve(n)));
    }
}

Hints (2)

What is the smallest case you can solve at once?
Which peg do you use as the helper?