public class TowerOfHanoi {    public static void main (String[] argv)    {        // A 3-disk puzzle:        System.out.println ("3-Disk solution: ");        solveHanoi (2, 0, 1);        // A 4-disk puzzle:        System.out.println ("4-Disk solution: ");        solveHanoi (3, 0, 1);    }    static void solveHanoi (int n, int i, int j)    {        // Bottom-out.        if (n == 0) {            // The smallest disk.            move (0, i, j);            return;        }        int k = other (i, j);        solveHanoi (n-1, i, k);    // Step 1.        move (n, i, j);            // Step 2.        solveHanoi (n-1, k, j);    // Step 3.    }    static void move (int n, int i, int j)    {        // For now, we'll merely print out the move.        System.out.println ("=> Move disk# " + n + " from tower " + i + " to tower " + j);    }    static int other (int i, int j)    {        // Given two towers, return the third.        if ( (i == 0) && (j == 1) ) {            return 2;        }        else if ( (i == 1) && (j == 0) ) {            return 2;        }        else if ( (i == 1) && (j == 2) ) {            return 0;        }        else if ( (i == 2) && (j == 1) ) {            return 0;        }        else if ( (i == 0) && (j == 2) ) {            return 1;        }        else if ( (i == 2) && (j == 0) ) {            return 1;        }        // We shouldn't reach here.        return -1;    }}

The Tower of Hanoi In the Tower of Hanoi puzzle: There are three stacks (towers), numbered 0, 1, 2. Tower 0 Tower 1 There are N disks numbered 0, ..., N-1. 0 is the smallest. Tower 2 Initially, the disks are placed in tower 0, in the order largest to smallest. Smallest on top. Goal: to move the disks to tower 1 using only legal moves. What's a legal move? You can move only a disk at the top of a tower. You can move only one disk at a time. You cannot place a disk on top of a smaller one. In-Class Exercise 1: Work out the moves for the ToH problem with three disks. You can either cut out pieces of paper or find an interactive applet on the web. Write down the moves on paper as in "Step 1: Move disk 0 from tower 0 to tower 1 ..."