Constraint Satisfaction Problems
In some search problems, we are more interested in how we got from the initial state to the goal state. In Search algorithms such as Best-First Search and A*, the main goal is to get to the goal state as fast as possible, for example A* is used as a path finding algorithm for computer strategy games.
Constraint Satisfaction Problem, is a set of variables with a domain of possible values, and a set of constraints that specify the possible values that a variable can take.
X = { X1, X2, …, Xn} : The variables of the problem.
D : is the domain of values that a variable of X can take.
C = {C1, C2, …, Ck} : set of constraints.
Let’s consider the following example:
D(a) = D(b) = D(c) = D(d) = {0,1}.
C = { a ≠ b, c ≠ d, a+c < b }.
This problem has four variables a, b, c and d. Each one of them can take two values: 0 or 1.
These variables have to respect the following constraints: a is different than b, c is different than d, a plus c is inferior to b.
So now with all that being said, to represent a problem as a CSP, first we have to identify the set of variables X, the domain D and the identify the set of constraints C.
Solving a Constraint Satisfaction Problem:
In order to find a solution for a CSP, there are multiple algorithms specifies for these kind of problems.
An algorithm is complete if it guarantees to return a correct answer for any arbitrary input (or, if no answer exists, it guarantees to return failure). [1]
An incomplete algorithm is one that does not provide the guarantee
that it will eventually either report a satisfying assignment or declare that the
given formula is unsatisfiable. This kind of algorithm tend to find an acceptable solution as fast as possible.
The most simple algorithm to identify a solution for a CSP is: Generate and Test.
This algorithm tries every possible affectation till it finds the solution as we can see in the following tree of the previous example.
Even though when it was obvious that the algorithm was leading to a false result, it keeps affecting the values until it reaches leafs of the tree, which is inefficient, it takes too much time and memory. We can see in the next table the estimated time needed to affect values to all the variables of a problem:
It is obvious that this method is inefficient.
Backtracking algorithm:
It is an improvement in Generate and Test, it works with the same concept(Depth-First search), the only difference is that backtracking algorithm, checks the values at each node, if constraints are violated it backtracks to the previous and tries another value, if not it continues towards the solution. We will apply this algorithm to the famous N-queens problem:
As we can see, once the algorithm finds illegal nodes, it backtracks to the previous node and tries other variants.
N-Queens problem: The N-queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal. The problem was first posed in the mid-19th century.
Anticipation Algorithm:
To improve the backtracking algorithm, we can anticipate the consequences of affectations. This algorithm is called anticipation algorithm or “Look Ahead” Algorithm. In this algorithm, instead of evaluating nodes based on current instantiated value, all subsequent to be instantiated variables are instantiated given the currently instantiated values.
We can use different filters, that will reduce the domain of variables, (less variables = less memory used and faster search).
Node consistency: “A variable is node consistent if all values within its domain are consistent with the all unary constraints on the variable”.
So in this case, we look ahead and eliminate all the values that the next variable can’t take, we can see that in the next tree of N-queens problem:
Arc consistency: An arc [x,r(x,y)] is arc consistent if for each value x in the domain(X) there is some value y in the domain(Y) such that r(x,y) is satisfied.
We can see in this example that the first arc of A, is not consistent because there A=3 doesn’t have a value in B that satisfies A<B. But in the B arc, both values have a value in A that satisfies the constraint A<B : B=2 has A=1, B=3 has A=1 and A = 2, so it is arc consistent.
The second network, is the arc consistent? No it is not, because A=7 doesn’t have a value in B that satisfies the constraint A<B/2.
A CSP is arc consistent if all variable pairs are arc consistent.
If we apply arc consistency to N-queens problem, we will get this result:
One of the most popular CSPs is Graph Coloring. The problem is, we have a graph and a set of colors, and we have to colors the nodes(states) such that each two adjacent nodes shouldn’t have the same color.
Lets take an example, we have three colors: Blue, Red and Yellow. Can we color a given graph using only these three colors?
We consider the following graph for this example:
This is a simple exercise you could try solving using CSP algorithms.
Before solving a CSP, as I mentioned earlier, we should identify the set of variables:
X = {A, B, C, D, E, F, G}
The domain of the possible values:
D={Blue, Red, Yellow}
And constraints are: (Two adjacent nodes shouldn’t have the same color)
C = {Color(A)≠ [Color(B),Color(C)]; Color(B)≠[Color(A), Color(D), Color(C)]; Color(D)≠ Color(B); Color(C)≠[Color(A),Color(B),Color(F),Color(E)]; Color(F)≠[Color(C), Color(E), Color(G)]; Color(E)≠[Color(C), Color(G), Color(F)]; Color(G)≠[Color(E), Color(F)]}
We can solve this using one of CSP algorithms, Backtracking will do just fine since we don’t have many variables. A solution example is : {A=Red, B=Blue, C=Yellow, D=Red, E=Red, F=Blue, G=Yellow}.
Omar El Yousfi.
