JEOPS Examples

The 8-Queens Problem

The Problem

The objective of the 8-queens problem is to place 8 queens in a chess board so that no queen can attack another. It is a classical problem used to ilustrate several techniques such as general search and backtracking. The figure below illustrates one of the solutions for this problem

The naive approach to solve it using a production system would be to assert 64 queens in the board (one for each position), and then stating a rule whose conditions checked for the non-attacking conditions. Though this approach works, it is very inefficient, because several permutations of the same solution would be found. A simple restriction in the row of each queen solves this problem.

Rule Base

package jeops.examples.queens;

/**
 * Rule base to solve the 8-queens problem. It will enumerate all
 * possible solutions to the problem.
 *
 * @author Carlos Figueira Filho (csff@cin.ufpe.br)
 */
public ruleBase EightQueens {

  private int solutionNumber = 1;

  rule findSolution {
    declarations
      Queen q1;
      Queen q2;
      Queen q3;
      Queen q4;
      Queen q5;
      Queen q6;
      Queen q7;
      Queen q8;
    conditions
      q1.getRow() == 1;
      q2.getRow() == 2;
      q3.getRow() == 3;
      q4.getRow() == 4;
      q5.getRow() == 5;
      q6.getRow() == 6;
      q7.getRow() == 7;
      q8.getRow() == 8;

      !q1.attacks(q2); !q1.attacks(q3); !q1.attacks(q4);
      !q1.attacks(q5); !q1.attacks(q6); !q1.attacks(q7);
      !q1.attacks(q8);
      
      !q2.attacks(q3); !q2.attacks(q4); !q2.attacks(q5);
      !q2.attacks(q6); !q2.attacks(q7); !q2.attacks(q8);

      !q3.attacks(q4); !q3.attacks(q5); !q3.attacks(q6);
      !q3.attacks(q7); !q3.attacks(q8);

      !q4.attacks(q5); !q4.attacks(q6); !q4.attacks(q7);
      !q4.attacks(q8);

      !q5.attacks(q6); !q5.attacks(q7); !q5.attacks(q8);

      !q6.attacks(q7); !q6.attacks(q8);

      !q7.attacks(q8);
    actions
      System.out.println("Solution " + solutionNumber + " to the problem:");
      boolean[][] aux = new boolean[9][9]; // To begin couting by 1.
      aux[q1.getRow()][q1.getColumn()] = true;
      aux[q2.getRow()][q2.getColumn()] = true;
      aux[q3.getRow()][q3.getColumn()] = true;
      aux[q4.getRow()][q4.getColumn()] = true;
      aux[q5.getRow()][q5.getColumn()] = true;
      aux[q6.getRow()][q6.getColumn()] = true;
      aux[q7.getRow()][q7.getColumn()] = true;
      aux[q8.getRow()][q8.getColumn()] = true;
      System.out.println("/-------------------------------\\");
      for (int i = 1; i <= 8; i++) {
        for (int j = 1; j <= 8; j++) {
          if (aux[i][j]) {
            System.out.print("| o ");
          } else {
            System.out.print("|   ");
          }
        }
        System.out.println("|");
        if (i < 8) {
          System.out.println("|---|---|---|---|---|---|---|---|");
        } else {
          System.out.println("\\-------------------------------/");
        }
      }
      solutionNumber++;
  }

}
Classes

jeops.examples.queens.Queen 
package jeops.examples.queens;

/**
 * Represents a queen in a chess board.
 *
 * @version 0.01  06 Apr 2000
 * @author Carlos Figueira Filho (csff@cin.ufpe.br)
 */
public class Queen {

  /**
   * The row of the board (1-8).
   */
  private int row;

  /**
   * The column of the board (1-8).
   */
  private int column;

  /**
   * Class constructor.
   *
   * @param row the row of the board.
   * @param column the column of the board.
   */
  public Queen(int row, int column) {
    this.row = row;
    this.column = column;
  }

  /**
   * Returns the row of this queen.
   *
   * @return the row of this queen.
   */
  public int getRow() {
    return row;
  }

  /**
   * Returns the column of this queen.
   *
   * @return the column of this queen.
   */
  public int getColumn() {
    return column;
  }

  /**
   * Checks whether this queen can be attacked by the given one.
   *
   * @param the queen that tries to attack this one
   * @return true if this queen can be attacked by the
   *          given one; false otherwise.
   */
  public boolean attacks(Queen q) {
    if (q.getRow() == this.row || q.getColumn() == this.column)
      return true;
    int x = Math.abs(this.row - q.getRow());
    int y = Math.abs(this.column - q.getColumn());
    return (x == y);
  }

}

The Test Program

TestQueens 
package jeops.examples.queens;

/**
 * Test class used to test the eight queens problem solved using JEOPS.
 *
 * @author Carlos Figueira Filho (csff@cin.ufpe.br)
 */
public class TestQueens {
  
  /**
   * Main entry point of the application.
   *
   * @param args command line arguments. None is needed.
   */
  public static void main(String[] args) {

    EightQueens kb = new EightQueens();
    long l1 = System.currentTimeMillis();
    for (int i = 1; i <= 8; i++) {
      for (int j = 1; j <= 8; j++) {
        kb.assert(new Queen(i,j));
      }
    }
    long l2 = System.currentTimeMillis();
    System.out.println("Asserting time: " + (l2 - l1) + "ms");
    kb.run();
  }

}

Back to manual