# 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;
localdecl
Hanoi ps1 = p.getSub1();
conditions
p.getDiscs() > 1;
!p.getOk();
ps1 != null;
ps1.getOk();
p.getSub2() == null;
actions
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;
localdecl
Hanoi ps1 = p.getSub1();
Hanoi ps2 = p.getSub2();
conditions
ps1 != null;
ps2 != null;
!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.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