Introduction

Ireland, 2008 - The basis for this tutorial were laid when I started as a summer intern at the Cork Constraint Computation Centre (4C) in summer of 2005. Although there exist several variations of this tutorial, this is being constantly updated to reflect the newest version of JaCoP. This tutorial should provide you with a sufficient background knowledge on Constraint Programming in order for you to persue your own CP endavours. Originally this tutorial served as a personal reference and was not intended to be published, hence please excuse the lack of references. Enough talk. Let's get started.

Constraints are methods of describing problems. All problems which we encounter can be described in terms of restrictions imposed on the set of possible solutions, and constraint programming is a problem-solving technique that works by implementing those restrictions in your environment.

This tutorial uses a popular game known as "Suduko" (aka Sudoku") to illustrate the concept of Constraint Satisfaction.

For those not familiar with Suduko: The Suduko board is a 9 x 9 grid, divided into smaller 3 x 3 sections. Some cells in the grid will have some pre-set numbers from 1 to 9. The solvers task is to fill the remaining empty cells so that each row, column and region contains one instance of every number from one to nine. Most people are not aware that all that they are doing is “Constraint Programming”, through applying complex propagation schemes to their “Suduko Puzzle”.

Constraint Programming

“Constraint programming represents one of the closest approaches computer science has yet
made to the Holy Grail of programming: the user states the problem, the computer solves it”
- Eugene C. Freuder, April 1997-

Constraints are ways of describing problems. Constraints arise from planning and scheduling to design and configuration. Constraints are natural mediums for people to express problems. Pretty much everything we do is a Constraint: from making enough money to live on, to travelling to work on the most efficient way possible.
Constraint Programming is the study of computational systems based on constraints. The idea of Constraint Programming is to solve problems by enforcing certain conditions on them which must be satisfied by the solution. The first work done on Constraint Programming was back in the sixties, however it was only within the past 10 years that Constraint Programming properly emerged – Scientists started to realise that Constraint Programming provides the basis for a powerful approach to problem solving. Currently there are two branches of Constraint Programming – Constraint Solving and Constraint Satisfaction – the later of which we will cover in this tutorial.

Constraint Satisfaction Problems
So, what exactly is a CSP (short: Constraint Satisfaction Problem)? As can be inferred from the name, this set of problems deal with constraints. Constraints equal to those mention above. We mostly run into problems (or find solutions that we don’t really want) mostly because of our limited capacity to deal with problems involving a large amount of variables and constraints. Now this is where constraint satisfaction problems (CSPs) come into action. Like most problems in artificial intelligence, CSPs are solved through search. What makes CSPs unique, however, is the structure of the problem; unlike other AI problems, there is a standard structure to CSPs that allows general search algorithms using heuristics (with knowledge about the structure of the problem and not necessarily domain-specific knowledge) to be implemented for any CSP. In addition to this, all CSPs can be searched in any order and still give the same result. A CSP consists of a set of variables and for each variable a finite set of possible values (known as it’s domain) and a set of constraints restricting the values that the variables can take. A solution to a CSP is an assignment of a value from its domain to every variable, in such as way that every constraint is satisfied.
So:

· A set of variables
· For each variable in the CSP, a finite set of possible values
· A set of constraints that restrict the values that the variables can take

Thus a solution to a Constraint Satisfaction Problem is an assignment of a value from its domain to every variable, so that every constraint is satisfied.
So what we want to find is:

· Just one solution
· All solutions
· An optimal solution

As already mentioned above, CSPs are solved through searching systematically through all the possible assignments of values to variables. But now you may ask yourself why not to simply represent the problem as a mathematical programming problem? There are several reasons for this:

· The representation of a CSP is most of the time much closer to the original problem
than a mathematical problem: the variables of the CSP directly correspond to the
problem entities and the constraints can be expressed without having to be translated
into linear inequalities. This makes the formulation simpler, the problem and solution
easier to understand and the choice of heuristics more straight forward.
· Sometimes solution may be found much faster than as if integer programming* is
involved.
· With the development of CP tools (eg Prolog, ILOG solvers, Eclipse) it has become a
lot easier to express and solve CSPs.

Examining a constraint
The Constraints of a CSP are usually represented by an expression involving affected
variables, eg

x1 ≠ x2
2x1 = 10x2 + x3
x1x2 < x3

Although the constraints of real-world problems are not represented this way in practice, the definition does emphasise that constraints need not correspond to simple expressions. They
can be expressed as inequalities, or equations, but don’t have to be.

A constraint can affect any number of variables from 1 to n (n is the number of variables in
the problem). The number of affected variables is called the arity of the constraint.
A constraint is considered n-ary if it involves n variables. So if a constraint affects just a
single variable, it is considered unary. This leads to our next topic: Unary Constraints, Binary
Constraints and Global Constraints.

Unary Constraints affect just one variable. The constraint can be used to remove any value which does not satisfy the constraint from the domain of the variable at the outset. Binary Constraints are constraints that involve two variables. They can be presented as a constraint graph, where the nodes of the graph represent the variables and an edge connects two nodes if a constraint exists between the two variables. Any constraint which is of higher arity be reduced to a set of binary constraints. However in most cases this is very impractical and is not worth doing.

Global Constrains are constraints with of arity > 2. A simple example of a global constraint is the Alldifferent constraint; this constraint forces all the variables it touches to have different values. We will come back to the aspects of Global Constraints and especially the Alldifferent constraint later on.

Search
Searching a CSP involves first, choosing a variable, and then assigning a value to it. In a search tree, each node is a variable and branches leading away from that node are the different values that can be assigned to that variable. Therefore, a CSP with x variables will generate a search tree of depth x.

Backtracking
If we consider a simple depth-first search on a CSP, we realize that because of the constraints imposed a variable returns a value we do not want, if in this case it is a node where there are no branches leading away from that node, we must “reverse” or “go backwards”. This method is called backtracking.

Forward checking
The forward checking does just as the name implies. Once an assignment is made to a variable, all other variables connected to the variable by constraints are retrieved and the values in their domains which are inconsistent with the current assignment are temporarily removed. In this way the domain of a variable can become empty and another value must be chosen for the current assignment. If there are no values left with which to assign the current variable, the search may need to backtrack, in which case those values that were temporarily removed as a result of the original assignment are reinstated to their respective domains.

Consistency
Forward checking utilizes a basic notion of consistency: an assignment to a variable is consistent with other assignments given a set of constraints. k-consistency is a term that defines the extent to which constraints are propagated. By definition, a CSP is k-consistent if for any subset of k – 1 variables in the problem, a consistent assignment to one of those variables allows a consistent assignment to any kth variable. In addition to a problem being k-consistent, it can also be strongly k-consistent, which means it is consistent for k and all weaker consistencies less than k. The benefit of a strongly kconsistent problem is that we will never have to backtrack! As with most things CSP, determining the correct level of consistency checking for a given problem is done empirically.

Constraint programming may have close ties with integer programming: one way of representing constraints is to form equations using subsets of the variables. One example of a simple constraint modelled as an equation, where X1 and X2 are variables, is X1 < X2. A more complex constraint is one we would use in the SEND + MORE = MONEY problem. Without elaborating the problem, the basic idea is that we try to find decimals to represent each letter in the equation.

Getting started
You will need to make a very schematic approach to modelling a CSP. Don’t rush into things.
Think about what exactly your aim is, then model the CSP:

· A set of variables
· A FDV
· Impose a constraint.

Usually, when investigating a problem, you will end up writing your own implementation of
this problem.
Here a few general tips when getting started:

· Don’t trust yourself
· Check your solutions as often as possible
· Make sure to fully understand your problem, before attempting to find a solution to it
· Make sure to vary the relevant factors

Suduko as a Constraint Satisfaction Problem

Definition 1 A Suduko square consists of n4 variables formed into n² x n² grid with values
from 1 to n² such that the entries in each row, each column and in each of the n² major n x n
blocks are AllDifferent? .

Definition 2 A Suduko problem consists of a partial assignment of the variables in a Suduko
square. The objective is to find a completion of the assignment which extends the partial
assignment and satisfies the constraints.

Definition 3 A Suduko Problem is well posed if it admits exactly one correct solution.

By looking at the above definitation, we conclude that

· All Suduko Puzzles solved by our Solver should have a unique solution. If a partial
assignment allows more than one solution we need to add hints until it is well posed.
· The puzzle should not contain any redundant information.

The CSP Model
Let’s look at the interaction of a single row(column) with a single box. The row Alldifferent constraint and the Alldifferent constraint for the box coincide in three variables. One necessary condition is that the set of variables A = {x1,x2,x3,x4,x5,x6} uses the same set of values as the set B = {x7,x8,x9,x10,x11,x12} of variables. Now all we have to do is remove all the values in set B which are not supported in set A, and vice versa. We can also consider the interaction of all major blocks in a line(column) with the three intersecting rows(columns). Each value must occur exactly once in each row, but also in each block. For every value we can express this as a matching problem between rows and blocks, which are the nodes in the graph show below. There is an arc between a row and a block if the given value is in the domain of any of the three overlapping variables. If that edge doesn’t belong to any matching, we can remove the value from the domain of all three variables. The algorithm works in the usual way, we first find a maximal matching, reorient the edges not in the matching search for strongly connected components. Edges which are not in the matching and whose ends do not belong to the same component can be removed. There are 54 of these
constraints. Now we’ll have a look at the interaction of row, column and block constraints. We now have three sets of nodes to consider. Thus bipartite matching is no longer of any use.

Moving on to JaCoP

JaCoP is a Finite Domain constraint solver created in 2001 and provides constraint programming paradigm implemented in Java. JaCoP is written entirely in Java 1.5. and supports a number of primitive constraints as well as conditional and reified constraints. Moreover, there is a handful of global constraints, such as three versions of alldifferent constraint, circuit, cumulative, diffn, and element. To date, JaCoP was used in a number of research works. An icomplete compilation can be found here - ResearchArticlesUsingJaCoP .

Finite Domain Variables
FDV X :: 1::100 is specified in JaCoP using the following general statement:

FDV x = new FDV(Store, “X”, 1, 100);

One can access the actual domain of FDV using the method dom(). Minimal and
maximal values in the domain can be accessed using min() and max() methods. The
FD can contain .holes. This is specified by adding intervals to FDV domain.

FDV x = new FDV(Store, “X”, 1, 100);
x.addDom(120,160);

This represents X :: 1::100 _ 120::160.
FDVs can also be defined without specifying their actual identifiers. In this case a system will
create an identifer which starts with ._. and then has a generated sequential number
of this variable, for example ._123..
Jacop contains many more features relating Finite Domain Variables; however the above is all
that is needed for now.

Constraints
Constraints are imposed using the impose method:

Store.impose(new Alldistinct(x[i]));

I could also define a constraint and then impose it into the FD store like this:

Constraint xyz = new XeqY? (a,b);
Xyz.impose(Store);

The Alldifferent constraint assures that all FDVs on a given list have different values assigned. This constraint uses a simple consistency technique which removes a value which is assigned to a given FDV from the domains of the other FDVs.
For example, a constraint

FDV a = new FDV(Store, “a”, 1, 9);
FDV b = new FDV(Store, “b”, 1, 9);
FDV c = new FDV(Store, “c”, 1, 9);
FDV[] v = {a,b,c};
Constraint ctr = new Alldifferent(v);
Store.impose(ctr);

enforces that the FDVs a, b, and c have different values.
Alldifferent constraints is provided using two implementations. Constraint Alldifferent
uses a simple implementation that does the following:

· If the domain of a finite domain variable gets assigned a value, the propagation
algorithm will remove this value from the other variables.
· Constraint Alldiff implements this basic pruning method and,
in addition, bounds consistency.

The constraints will produce the following results after consistency enforcement.
Store.impose(new Alldifferent (v));
a :: {2..9}, b :: {2..9}, c :: {1..9}
and
Store.impose(new Alldiff(v));
a :: {2..9}, b :: {2..9}, c = 1

Search for solutions
When all the FDVs and constraints are defined a search for a solution can be started. JaCoP offers a number of methods for this. It makes it possible to search for a single
solution or to try to find a solution which minimizes/maximizes a given cost function. This is achieved by using depth-first-search together with consistency checking. Consistency checking can be achieved by using the following function from the store class.

boolean result = store.consistency();

When the procedure returns false the store is inconsistent and no solution can be found. The result true indicates that inconsistency cannot be found. Since the FD solver is not complete it does not mean that the store is really consistent. To find a single solution the DepthFirstSearch? can be used.

SelectChoicePoint select = new SimpleSelect? (FDVList, new SmallestDomain? (), new IndomainMin? ());
DepthFirstSearch search = new DepthFirstSearch? ();
booleand result = search.labeling(store, select);

The method requires the following information:

· How to assign values for each FDV from its domain; this is defined by Indomain
object (in our case we start from the minimal value in the domain and assign
successive values).
· How to select FDV for assignment from the list of FDVs (FDVList); this is decided
by SelectVariable? object (in our case we select FDVs from the list using the order based on the size of the variable).
· How to perform depth-first-search; this is specified by Search object (in this case
it is ordinary depth-first-search).

Search
JaCoP offers methods for finding one, all, and/or optimal solution. In order to find an optimal minimal solution a cost variable must be provided as an additional third parameter to labeling() function of DepthFirstSearch? . Every time a solution is found a solution listener within a search is informed about the solution. The solution listener decides if the search should continue or stop. The following code can instruct the solution listener to search for all solutions - search.getSolutionListener().searchAll(true). In case if we are interested only in the number of solutions then we can call the following function to save memory by not storing the solutions explicitly - search.getSolutionListener().recordSolutions(true).

Depth First Search
A solution satisfying all constraints can be found using a depth first search algorithm. This algorithm searches for a possible solution by organizing the search space as a search tree. In every node of this tree a value is assigned to a domain variable and a decision whether the node will be extended or the search will be cut in this node is made. The search is cut if the assignment to the selected domain variable does not fulfill all constraints. Since assignment of a value to a domain variable triggers the constraint propagation and possible adjustment of the domain variable representing the cost function, the decision can easily be made to continue or to cut the search at this node of the search tree.

Credit search
Credit search combines credit based exhaustive search at the beginning of the tree with local search in the rest of the tree. The search is controlled by three parameters: number of credits, number of backtracks during local search. A credit search is obtained by transforming a DepthFirstSearch? into one. This is done by using a CreditCalculator? listener. The following code attaches listener and transforms a DepthFirstSearch? into CreditSearch? .

SelectChoicePoint select = new SimpleSelect? (FDVList, new SmallestDomain? (), new IndomainMin? ());
DepthFirstSearch search = new DepthFirstSearch? ();

CreditCalculator credit ) new CreditCalculator? (64, 5000);
if (search.getConsistencyListener() == null) search.setConsistencyListener(credit);
else search.getConsistencyListener().setChildrenListeners(credit);
search.setExitListener(credit);
search.setTimeOutListener(credit);

booleand result = search.labeling(store, select).;

Writing the Suduko Solver
Obviously enough the first thing we need to do is get our hands on JaCoP.jar, include it as a required library in our project properties and then import the library. The next thing would be to define the Finite Domain Variables for the X-axis and the Y-axis:
Taking the diagram below as our Suduko board then X would refer to the X-axis and Y to the Y-axis (since we need numbers1-9 on both the X and Y-axis) Remember: we need a matrix of 9x9 for both X and Y.
Now let’s throw in the FD store, and our code will look something like this:

import JaCoP.*;
…
FDV[][] x = new FDV[9][9];
FDV[][] y = new FDV[9][9];
FDstore store = new FDstore();

Now we will need to initialize X using two for loops. The code itself is pretty much selfexplanatory, however note that, since we are using JOptionPane? we will need to import javax.swing.*
Note: Field is a JTextField matrix consisting of 9x9 elements:

for(int i=0; i<9; i++)
for(int j = 0; j<9; j++) {
x[i][j] = new FDV(store, new String(""+i+j),1,9);
if(field[i][j].getText().equals("")) {
store.impose(new XeqC? (x[i][j],
Integer.parse Int(field[i][j].getText())));
if(x[i][j] == null) {
JOptionPane? .showMessageDialog(SSOLVERMC.this,"Error:" + i + "" + j, "Error", JOptionPane? .WARNING_MESSAGE);
}
}
}

Having done this, we will now define an ArrayList? (older versions of JDK may have to use Vector) as well as search and add the elements of X into the ArrayList? . Then we will initialize Y, using the elements in X. This way we now have the X-axis and Y-axis represented.

ArrayList list = new ArrayList? ();
DepthFirstSearch? search = new DepthFirstSearch? ();
search.setPrintInfo(true);

for(int i=0; i<9; i++ )
for(int j=0; j<9; j++ )
list .add(x[i][j]);

for (int i=0; i<9; i++)
for(int j=0; j < 9; j++)
y[j][i] = x[i][j];

Now we will impose constraints on the rows in X and Y:

for(int i=0; i<9; i++) {
store.impose(new Alldistinct(x[i]));
store.impose(new Alldistinct(y[i]));
}

setPrintInfo is unfamiliar: it’s a simple, handy little feature to JaCoP which outputs the search info. It takes one boolean argument – either true or false – we will disable it, since we don’t really need it just yet.

The following line of code is not part of the “solving process” and we don’t really need it, but I put it in there anyway, for the results Message Dialog which we will Display once the Suduko puzzle has been successfully solved. System.currentTimeMillis() retrieves the current time according to the System clock in Milliseconds, which we will store in the variable begin:

long begin = System.currentTimeMillis();

Now we will search for our solutions – again these lines are straightforward enough, having
them explained already in the Chapter 7 – “Using JaCoP Library”:

SelectChoicePoint select = new SimpleSelect? (list, new SmallestDomain? (), new IndomainMin? ());
DepthFirstSearch search = new DepthFirstSearch? ();
booleand result = search.labeling(store, select);

Running the above code, we would (depending on the puzzle) have X and Y filled with the numbers one to nine respectively:

1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
3 4 5 6 7 8 9 1 2
4 5 6 7 8 9 1 2 3
5 6 7 8 9 1 2 3 4
6 7 8 9 1 2 3 4 5
7 8 9 1 2 3 4 5 6
8 9 1 2 3 4 5 6 7
9 1 2 3 4 5 6 7 8

As you have probably noticed, each row and each column correctly contains the numbers one to nine (note: this applies to a empty sample Suduko field with no pre-defined numbers).
However the separate boxes are incorrect. Looking at the first box, we notice that two, three and four occur more than once and that six, seven, eight and nine are missing. In order to solve the puzzle correctly we need to apply constraints to each box so that each number can only occur once. Here is an example of the first box:

for(n = 0; n < 3; n++)
for(m = 0; m < 3; m++)
{
for(a = 0; a < 3; a++)
{
for(b = 0; b < 3; b++)
{
if(n = a && m = b)
store.impose(new XneqY? (x[n][m], x[a][b]));
}
}
}

If we do this for all the boxes, we will eventually obtain the correct result. Now we will retrieve the current System time once more and store it inside the variable end.
This way, all we need to do is subtract begin from end and we will get the time needed to solve the puzzle.

long end = System.currentTimeMillis();

Finally we will output the results into the appropriate text fields. Using two for-loops we will iterate through the arrays. If the current textbox is empty, we will set its foreground colour to 0,0,0 (black) and then set its text equal to that in X. Then we will simply remove the unwanted text and catch any BadLocationExceptions? .

for(int i=0; i<9; i++)
for(int j=0; j<9; j++)
{
if(field[i][j].getText().equals(""))
{
String tmp;
field[i][j].setForeground(new Color(0,0,0));
field[i][j].setText("" + x[i][j]);
try {
tmp = field[i][j].getText(3,1);
field[i][j].setText(tmp);
}
catch(BadLocationException? ble)
{
JOptionPane.showMessageDialog(ssolverMC.this,""+ble,"…",
JOptionPane.WARNING_MESSAGE);
}

}
}