tut_base
Tutorial : first steps with Choco
This tutorial is aimed at presenting the basic information needed to be able to write one's first application with Choco :
- how to create a problem,
- how to solve it,
- how to explore the set of solution(s).
Our running example will be the n-queens problem.
Problem modeling
In order to solve the n-queens problem with Choco, the first thing to do is to create a problem. Here is how it is done in Choco:
Problem nQueens = new Problem();
This object will be the basis for all the subsequent information that will be added. A classical model for the n-queens problem consists in defining n variables taking their value between 1 and n : those variables represent the position of each queen on each line. In Choco, we can therefore declare an array of variables and ask to the Problem to initialise them:
IntVar[] queens = new IntVar[n]; // declaring an array of n variables
for (int i = 0; i < queens.length; i++) {
queens[i] = nQueens.makeEnumIntVar("Queen" + i, 1, n);
}
The next step consists in adding constraints to our problem:
- any two queens should be positionned in different lines (the model itself enforces this constraint)
- any two queens should be in different columns
- any two queens should not be in the same diagonal
We will use difference and linear combination constraints:
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
nQueens.post(nQueens.neq(queens[i], queens[j])); // different columns
nQueens.post(nQueens.neq(queens[i],
nQueens.plus(queens[j], j – i))); // diagonal
nQueens.post(nQueens.neq(queens[i],
nQueens.minus(queens[j], j – i))); // diagonal
}
}
Our problem is now completed: the problem has been created, variables have been created, constraints have been created and posted (they are now active in the problem). Now, it is time to actually solve the problem.
Solving the problem
The Problem object provides three methods that can be used to solve a problem: propagate, solve, and solveAll.
The first one can be used to propagate the constraints of the problem i.e. as much filtering as possible impossible values from the domain of the variables (no enumeration is performed here).
try {
nQueens.propagate();
}
catch (ContradictionException e) {
System.err.println("This problem is over-constrained");
System.exit(-1);
}
The second one is used to really solve the problem i.e. looking for one solution. It returns a Boolean:
- Boolean.TRUE if the problem does have a solution
- Boolean.FALSE if it does not
if (nQueens.solve() == Boolean.TRUE) {
System.out.println("the problem has at least one solution");
}
else {
System.out.println("the problem has no solution");
}
The third one is used to compute all the solutions of the problem.
nQueens.solveAll();
System.out.println("the problem has " + nQueens.getSolver().getNbSolutions()
+ " solutions");
Exploring the set of solutions
Choco allows the user to print or explore the set of solutions. Using the solve method leaves the variables with the values of the computed solution if it exists.
nQueens.solve();
System.out.println("One solution is:");
for (int i = 0; i < queens.length; i++) {
System.out.println(queens[i] + " = " + queens[i].getValue());
}
for (int = 0; i < nQueens.getNbIntVars(); i++) {
System.out.println(nQueens.getIntVar(i) + " = "
+ nQueens.getIntVar(i).getValue());
}
Choco can also be used to enumerate the set of solutions for a problem. The first step is to solve the problem, and then to enumerate the solutions using the nextSolution() method.
if (nQueens.solve() == Boolean.TRUE) {
do {
for (int i = 0; i < nQueens.getNbIntVars(); i++) {
Systemm.out.println(nQueens.getIntVar(i) + " = "
+ pb.getIntVar(i).getValue());
}
} while (pb.nextSolution() == Boolean.TRUE)
}
Finally, at any time the nQueens.getSolver().getSearchSolver().maxNbSolutionStored (5 by default) solutions are accessible in the nQueens.getSolver().getSearchSolver().solution array (the cell number 0 containing the last computed one).
System.out.println("the current solution is: ");
for (int = 0; i < nQueens.getNbIntVars(); i++) {
System.out.println(nQueens.getIntVar(i) + " = "
+ nQueens.getIntVar(i).getValue());
}
Solution previousSolution =
nQueens.pb.getSolver().getSearchSolver().solutions;
System.out.println("the previsous solution was: ");
for (int = 0; i < nQueens.getNbIntVars(); i++) {
System.out.println(nQueens.getIntVar(i) + " = "
+ previousSolution.getValue(i));
}
At the end of this tutorial, we are now able to model, solve and explore the set of solutions on the n-queens problem.