Class TowersOfHanoi

java.lang.Object

TowersOfHanoi

public class TowersOfHanoi
extends Object

ACKNOWLEDGEMENTS: This assignment was heavily copied from the wonderfully competent faculty at Princeton University. Permission to use the assignment was granted via email by Dr. Robert Sedgewick. We gratefully acknowledge the material from Princeton University used in this assignment! The original Princeton assignment is here: http://introcs.cs.princeton.edu/java/23recursion/AnimatedHanoi.java.html Copyright © 2000–2011, Robert Sedgewick and Kevin Wayne.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	TowersOfHanoi.Move The Move class represents the action of moving one disc between pegs.

Constructor Summary

Constructors

Constructor and Description
TowersOfHanoi()

Method Summary

Modifier and Type	Method and Description
static void	iterativeHanoi(int disc, int from, int aux, int to) Iterative solution using stack.
static void	main(String[] args)
(package private) static void	move(int disc, int source, int dest) Method to report and move a disc.
static void	recursiveHanoi(int disc, int from, int aux, int to) The recursive solution for Towers of Hanoi.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

TowersOfHanoi

public TowersOfHanoi()

Method Detail

main

public static void main(String[] args)
                 throws InterruptedException

Throws:

InterruptedException

recursiveHanoi

public static void recursiveHanoi(int disc,
                                  int from,
                                  int aux,
                                  int to)

The recursive solution for Towers of Hanoi.
Implement the recursive solver for Towers of Hanoi, as follows:

1. The base case for the recursion is to return if asked to move disc 0.
2. Make a recursive call to move the stack above the current disc from the source to the auxiliary pole. For example, if the current disk is 5, you would want to recurse with disk 4 and the appropriate arguments.
3. Now the discs above are out of the way, move(int, int, int) the requested disc to the destination pole.
4. Make a recursive call to move the stack on the auxiliary pole back to the destination pole.

Verify that your solution works by running the program using the recursive option.

Parameters:

disc - the disc you are moving to the destination (auxiliary) pole.

from - the pole that the disk is currently on

aux - the auxiliary pole (provides supplementary or additional help) but won't be used to move this disk at this point of time.

to - the pole that the disk will move to

iterativeHanoi

public static void iterativeHanoi(int disc,
                                  int from,
                                  int aux,
                                  int to)

Iterative solution using stack.

1. Create a Move object using the arguments to iterativeHanoi() and push it onto the MyStack field named "moves". Initially, this bottom disc is covered of course. This represents the initial request to move the bottom disc.
2. Enter a loop that processes moves from the stack until the stack is empty. Within the loop:
   • pop a Move object from the top of the stack.
   • If the requested move is for disc 0, just continue the loop (no work is required).
   • If moving a currently covered disc:
     1. Push the Move object back onto the stack after marking it uncovered. By the time we see it again, it will be uncovered.
     2. Push a new Move object requesting that the disc covering it is moved out of the way (onto the auxiliary). This is the analog of the first recursive call in the recursive version.
   • If moving an uncovered disc:
     1. Perform the actual move of the disc by calling the move method (since it is uncovered, it is free to be moved now).
     2. Push a new Move object requesting that the disc that was previously moved off onto the auxiliary be moved from there back on top of the just-moved disc. This is analogous to the second recursive call.
   • If you continue until the stack is empty, this will solve the puzzle, effectively tracing the same steps as the recursive version, modeling the state of the algorithm with an explicit stack, rather than the runtime stack.

Parameters:

disc - the current disc

from - what pole the disc is on

aux - the auxiliary pole

to - what pole the disc is being moved to

move

static void move(int disc,
                 int source,
                 int dest)

Method to report and move a disc.

Parameters:

disc - the current disc

source - the pole the disc is on

dest - the pole the disc is being moved to