Tutorial

How to use JConstraints to solve your constraint satisfaction problems

JConstraints is a Java framework strongly based on the constraint satisfaction paradigm. There are three main concepts that describes any cosntraint problem:

1) Variables: the variables represents the "agents" that compound the constraint problem. For example, in the N-queens problem, each queen could be a variable in the problem. Each variable has to be assigned a value that don't harm any constraint attached to it.

2) Values: the values that can be assigned to the variables. The set of values that a variable can be assigned is called domain.

3) Constraints: the restrictions that has to be satisfied in order to find a solution to the problem.

Based on these three main concepts, JConstraints provides a set of interfaces/classes that enables developers to model any kind of constraint problem easily:

• jconstraints.elements.Variable: In the majority of the problems, the developer won't have do inherit from
  this class. Just set it's values domain and name in order to use it in any constraint problem.

• jconstraints.elements.Value: This interface has to be implemented in order to represent any kind of value
  that the problem demands. Just override the method equals(Value value) to allow the framework to differ on
  value from the others.

• jconstraints.elements.Constraint: This abstract class has to be inherited in order to represent a constraint specific to the problem. Just implements the method satisfies(), allowing the framework to know when the constraint is satisfied.

• jconstraints.elements.ComposedVariable: Class that extends from jconstraints.elements.Variable to represent a composed variable usually useful for constraint with order higher than 2 (N-ary constraints).

• jconstraints.elements.ComposedValue: Class that extends from jconstraints.elements.Value to represent
  a compound values values. Useful when handling N-ary constraints. Store this kind of values inside a ComposedVariable.

After modeling the problem using the above classes/interfaces, the developer is able to use the classes below to initiate the problem resolution:

• jconstraints.elements.CSPSolver: The solver that will find a solution to the problem.

• jconstraints.elements.CSPAlgorithm: An Enum that provides an array of algorithms to be chosen by the developer that will solve the problem. Just set the chosen algorithm in the CSPSolver using the method setAlgorithm(). At the end of this tutorial, there is a list of algorthms tha can be used to solve constraints problems.

• jconstraints.elements.CPSProblem: Class that represent a problem to be solved. The problem is passed to the CSPSolver before initiate the resolution process.

• jconstraints.elements.PerformanceReport: Class tha stores the performance report of the last resolution process. This classes provide information about the number of backtracks performed, backjumps realized, the number of tries that a local search does and etc.

So, after this massive amount of information, let's show how to use the framework by examples.

Example 1: N-Queens problem

The N-Queen problem is described as a set of queens in a board and each of then that has to be placed in a manner that no queen attacks each other (no queen in the same line, column and diagonal).

First, create a class that implements the Value interface in order to represent the position of the queen on the board:

public class QueenValue implements Value{

    private int colValue;
    private int lineValue;

    public int getColValue() {
        return colValue;
    }

    public void setColValue(int colValue) {
        this.colValue = colValue;
    }

    public int getLineValue() {
        return lineValue;
    }

    public void setLineValue(int lineValue) {
        this.lineValue = lineValue;
    }

    @Override
    public boolean equals(Value value) {
        QueenValue v = (QueenValue) value;

        if(colValue == v.getColValue() && lineValue == v.getLineValue()){
            return true;
        }
        return false;
    }

    public String toString(){
        return "line "+lineValue+" column "+colValue;
    }
}

Then, extends the abstract class Constraint to model the queen constraint (no queen can attack each other):

public class QueenConstraint extends Constraint {

    private Variable var1;
    private Variable var2;

    public QueenConstraint(ArrayList<Variable> variables) {

        super(variables);
        var1 = variables.get(0);
        var2 = variables.get(1);
    }

    @Override
    public boolean satisfies() {

        if (!var1.hasAssignedValue() || !var2.hasAssignedValue()) {
            return true;
        }

        if (var1 != var2) {
            QueenValue value1 = (QueenValue) var1.getAssignedValue();
            QueenValue value2 = (QueenValue) var2.getAssignedValue();

            if (value1.getColValue() == value2.getColValue()
                    || value1.getLineValue() == value2.getLineValue()) {
                return false;
            }

            //Is it at the same diagonal?
            if (Math.abs(value1.getColValue() - value2.getColValue()) == Math
                    .abs(value1.getLineValue() - value2.getLineValue())) {
                return false;
            }
        }

        return true;
    }

}

The last step is to create the variables, the domain of each variable and set a relation between the variables using the constraints (in the N-Queen problem, each variable has constraints connecting each of the others):

~~~~~~~~~~~~
:::java

public static void main(String args[]) {

    //Number of queens
    int QUEEN_NUMBER = 9;

    ArrayList<Variable> variables = new ArrayList<Variable>();
    ArrayList<Constraint> constraints = new ArrayList<Constraint>();

    // Creates a domain for each variable
    ArrayList<Value> domain = null;

    for (int i = 0; i < QUEEN_NUMBER; i++) {
        if (domain == null) {
            domain = new ArrayList<Value>();
            for (int line = 0; line < QUEEN_NUMBER; line++) {
                for (int col = 0; col < QUEEN_NUMBER; col++) {
                    QueenValue value = new QueenValue();
                    value.setColValue(col);
                    value.setLineValue(line);
                    domain.add(value);
                }
            }
        }

                //Creates a variable
        Variable variable = new Variable(domain);
        variable.setName("Queen " + (i + 1));
        variables.add(variable);
    }

            // Create the constraints between each variable
    for (Variable var1 : variables) {
        for (Variable var2 : variables) {
            if (var1 != var2) {
                ArrayList<Variable> vars = new ArrayList<Variable>();
                vars.add(var1);
                vars.add(var2);
                QueenConstraint constraint = new QueenConstraint(vars);
                constraints.add(constraint);
            }
        }
    }

        //Creates the solver, set an algorithm and run the resolution process.
    CSPSolver solver = new CSPSolver();
    solver.setAlgorithm(CSPAlgorithm.BACKTRACKING);
    variables = solver.solve(new CSProblem(variables, constraints));

    if (variables == null) {
        System.out.println("No solution!");
    } else {

        System.out.println("Used algorithm: "
                + solver.getReport().getAlgorithmName());
        for (Variable var : variables) {
            System.out.println(var.getName() + " line: "
                    + ((QueenValue) var.getAssignedValue()).getLineValue()
                    + " column: "
                    + ((QueenValue) var.getAssignedValue()).getColValue());
        }

        // Print the performance report
        System.out.println("");
        System.out.println("Number of Backtracks:"
                + solver.getReport().getBackTracksNumber());
        System.out.println("Total time: "
                + solver.getReport().getTotalTime() + " seconds");
    }
}

~~~~~~~~~~~

Example 2: N-ary Constrains problem

N-ary constraints problems is a kind of problem on which a variable depends on two or more variables simultaneously. In other words, a variable is restricted by two or more other variables using the same constraint. As an example, let's find the solution for the inequation X + Y = Z