The Towers of Hanoi is a famous puzzle, invented in 1883 by mathematician Edouar

Question

The Towers of Hanoi is a famous puzzle, invented in 1883 by mathematician Edouard Lucas, used today primarily for teaching recursion. The most natural solution exhibits a classic recursive algorithm. An iterative solution is not at all obvious. The puzzle consists of three pegs with n disks of decreasing size, stacked upon one of them. To solve the puzzle, move all of the disks to one of the other pegs one at a time without ever placing any disk on top of a smaller one. See Figure 8.13. Write and test a recursive method that solves the Towers of Hanoi puzzle. Your method hanoi(...) should have four parameters: int n, char start, char finish, char using. Your test call should be hanoi(5, 'A', 'B', 'C'); where the pegs are called 'A', 'B', and 'C', and you are trying to move five disks from 'A' to 'B', Using 'C'.

Explanation / Answer

/**
* @author
*
*/
public class TowersOfHanoi {

   /**
   * @param args
   */
   public static void main(String[] args) {

       honoi(5, 'A', 'B', 'C');
   }

   /**
   * recursive method to generate towers of honoi
   *
   * @param n
   * @param start
   * @param using
   * @param finish
   */
   public static void honoi(int n, char start, char using, char finish) {
       if (n == 1) {
           System.out.println("Disk 1 from " + start + " to " + finish);
       } else {
           honoi(n - 1, start, finish, using);
           System.out
                   .println("Disk " + n + " from " + start + " to " + finish);
           honoi(n - 1, using, start, finish);
       }
   }
}

OUTPUT:

Disk 1 from A to C
Disk 2 from A to B
Disk 1 from C to B
Disk 3 from A to C
Disk 1 from B to A
Disk 2 from B to C
Disk 1 from A to C
Disk 4 from A to B
Disk 1 from C to B
Disk 2 from C to A
Disk 1 from B to A
Disk 3 from C to B
Disk 1 from A to C
Disk 2 from A to B
Disk 1 from C to B
Disk 5 from A to C
Disk 1 from B to A
Disk 2 from B to C
Disk 1 from A to C
Disk 3 from B to A
Disk 1 from C to B
Disk 2 from C to A
Disk 1 from B to A
Disk 4 from B to C
Disk 1 from A to C
Disk 2 from A to B
Disk 1 from C to B
Disk 3 from A to C
Disk 1 from B to A
Disk 2 from B to C
Disk 1 from A to C

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.