JEOPS Examples

The Towers of Hanoi

The Problem

The goal of the Towers of Hanoi problem is to move a certain amount of disks from one pin to another in a 3-pin base, as shown in the figure below.

There are two restrictions to the disks movement: only one disk can be moved at any time; and a bigger disk can never be atop a smaller one.

This is a classical recursive problem. It can be solved easily as follows: to pass n disks from pin A to pin B, pass the (n-1) disks to pin C, then pass the larger disk from pin A to pin B, and then pass the (n-1) disks from pin C to pin B.

Rule Base

package jeops.examples.hanoi;

/**
 * Rule base used to solve the towers of hanoi problem.
 */
public ruleBase BaseHanoi {

  rule createsFirstSubProblem {  // Passing (n-1) discs to the intermediary pin
    declarations
      Hanoi p;
    conditions
      p.getDiscs() > 1;
      !p.getOk();
      p.getSub1() == null;
    actions
      Hanoi ps1;
      ps1 = new Hanoi(p.getDiscs() - 1, p.getSource(), p.getIntermediate());
      p.setSub1(ps1);
      assert(ps1);
      modified(p);
  }

  rule createsSecondSubproblem {  // First one is ok, doing the second.
    declarations
      Hanoi p, ps1;
    conditions
      p.getDiscs() > 1;
      !p.getOk();
      ps1 == p.getSub1();
      ps1.getOk();
      p.getSub2() == null;
    actions
      p.addMove(p.getSource(), p.getDestination());
      Hanoi ps2;
      ps2 = new Hanoi(p.getDiscs() - 1, p.getIntermediate(), p.getDestination());
      p.setSub2(ps2);
      assert (ps2);
      modified(p);
  }
  
  rule bothSubproblemsOk { // If both subproblems are ok, then the problem is ok.
    declarations
      Hanoi p, ps1, ps2;
    conditions
      ps1 == p.getSub1();
      ps2 == p.getSub2();
      !p.getOk();
      ps1.getOk();
      ps2.getOk();
    actions
      p.setOk(true);
      modified(p);
  }
  
  rule oneDisc {  // Base case
    declarations
      Hanoi p;
    conditions
      p.getDiscs() == 1;
      !p.getOk();
    actions
      p.addMove(p.getSource(), p.getDestination());
      p.setOk(true);
      modified(p);
  }

}
Classes

jeops.examples.hanoi.Hanoi 
package jeops.examples.hanoi;

import java.util.Vector;

/**
 * This class models an encapsulation for a solution for the Towers
 * of Hanoi problem.
 *
 * @version 0.01  15 Mar 1998
 * @author Carlos Figueira Filho (csff@cin.ufpe.br)
 */
public class Hanoi {

  /**
   * The number of discs in this problem.
   */
  private int discs;

  /**
   * The pin from where the discs come.
   */
  private int source;

  /**
   * The pin the disks have to be moved to.
   */
  private int destination;

  /**
   * The first subproblem used to solve this problem.
   */
  private Hanoi sub1;

  /**
   * The second subproblem used to solve this problem.
   */
  private Hanoi sub2;

  /**
   * Flag which indicates whether this problem is solved.
   */
  private boolean ok;

  /**
   * The problem solution, made up by several Strings in the
   * form " moved to ".
   */
  private Vector solution = new Vector();

  /**
   * Class constructor.
   *
   * @param numDiscs the number of the discs for this instance.
   * @param source the source pin
   * @param destination the destination pin
   */
  public Hanoi (int numDiscs, int source, int destination) {
    this.discs = numDiscs;
    this.source = source;
    this.destination = destination;
  }

  /**
   * Adds a movement to the solution.
   *
   * @param from the pin from where the disc is moved.
   * @param to the pin to where the disc is moved.
   */
  public void addMove(int from, int to) {
    solution.addElement(from + " moved to " + to);
  }

  /**
   * Prints the tree for the expression of this precondition. Useful
   * for debugging.
   */
  public void dump() {
    dump(0);
  }

  /**
   * Prints the tree for the expression of this precondition. Useful
   * for debugging.
   *
   * @param spaces the identation for the printed output.
   */
  public void dump(int spaces) {
    int i, j;
    if (sub1 != null)
      sub1.dump(spaces);
    for (i = 0; i < solution.size(); i++) {
      for (j = 0; j < spaces; j++)
        System.out.print(" ");
      System.out.println("Disk " + solution.elementAt(i) + ".");
    }
    if (sub2 != null)
      sub2.dump(spaces);
  }

  /**
   * Returns the destination pin for this problem.
   *
   * @return the destination pin for this problem.
   */
  public int getDestination() {
    return destination;
  }

  /**
   * Returns the number of discs of this problem.
   *
   * @return the number of discs of this problem.
   */
  public int getDiscs() {
    return discs;
  }

  /**
   * Returns the intermediate pin form this problem.
   *
   * @return the intermediate pin form this problem.
   */
  public int getIntermediate() {
    return (6 - source - destination);
  }

  /**
   * Returns the state of this problem.
   *
   * @return true if this problem has already been
   *          solved; false otherwise.
   */
  public boolean getOk() {
    return ok;
  }

  /**
   * Returns the source pin for this problem.
   *
   * @return the source pin for this problem.
   */
  public int getSource() {
    return source;
  }

  /**
   * Returns the first subproblem for this problem.
   *
   * @return the first subproblem for this problem.
   */
  public Hanoi getSub1() {
    return sub1;
  }

  /**
   * Returns the second subproblem for this problem.
   *
   * @return the second subproblem for this problem.
   */
  public Hanoi getSub2() {
    return sub2;
  }

  /**
   * Determines whether this problem has already been solved.
   *
   * @param newValue the new value for the state of this problem.
   */
  public void setOk(boolean newValue) {
    this.ok = newValue;
  }

  /**
   * Determines the first subproblem for this problem.
   *
   * @param sub1 the new value for the first subproblem of this one.
   */
  public void setSub1(Hanoi sub1) {
    this.sub1 = sub1;
  }

  /**
   * Determines the second subproblem for this problem.
   *
   * @param sub1 the new value for the second subproblem of this one.
   */
  public void setSub2(Hanoi sub2) {
    this.sub2 = sub2;
  }
}

The Test Program

TestHanoi 
package jeops.examples.hanoi;

/**
 * Class used to test the Towers of Hanoi example for JEOPS.
 *
 * @version 0.01  06 Apr 2000
 * @author Carlos Figueira Filho (csff@cin.ufpe.br)
 */
public class TestHanoi {

  /**
   * Starts the application.
   *
   * @param args a command-line arguments array. None is needed,
   *          but one can pass the number of discs to be moved.
   */
  public static void main(java.lang.String[] args) {
    int noDiscs;
    if (args.length == 0) {
      noDiscs = 3;
    } else {
      noDiscs = Integer.parseInt(args[0]);
    }
    Hanoi h = new Hanoi(noDiscs, 1, 3);
    BaseHanoi kb = new BaseHanoi();
    kb.assert(h);
    kb.run();
    System.out.println("Problem solution:");
    h.dump(2);
  }

}

Back to manual