# 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