Constraint Satisfaction Problems

This notebook serves as a supporting material for Chapter 6 Constraint Satisfaction Problems. In this notebook, we demonstrate how the csp package can be used to solve problems that can be formulated as CSPs. We use factored representation for the states in a CSP. We will see that by deviating from the notion of atomic states, we can use general purpose inference techniques and search heuristics to solve any CSP. Hence, a CSP solver can be used to solve any problem once it has been formulated as a CSP. Let's begin by loading the aima-core jar file.



In [1]:

    
%classpath add jar ../out/artifacts/aima_core_jar/aima-core.jar

Defining constraint Satisfaction Problems

Let's begin with formally defining a CSP. Later, we will dive into the code repository and explore the CSP class.

As per the textbook, a constraint satisfaction problem consists of three components, $X$, $D$, and $C$:

$X$ is a set of variables, $\{X_1,...,X_n\}$.
$D$ is a set of domains, $\{D_1,...,D_n\}$, one for each variable.
$C$ is a set of constraints that specify allowable combinations of values.

Each domain $D_i$ consists of a set of allowable values, $\{v_1,...,v_k\}$ for variable $X_i$. Each constraint $C_i$ consists of a pair $<scope,rel>$, where $scope$ is a tuple of variables that participate in the constraint and $rel$ is a relation that defines the values that those variables can take on. A relation can be represented as an explicit list of all tuples of values that satisfy the constraint, or as an abstract relation that supports two operations: testing if a tuple is a member of the relation and enumerating the members of the relation.

Let's take a look at the CSP class in the code repository and then we will move on to formally defining our first problem.

The class takes generics VAR and VAL for the type of variables and the values they can take respectively. The data structures used in the class include:

List<VAR> variables: The list of all variables in the CSP
List<Domain<VAL>> domains: The corresponding domains of the variables
List<Constraint<VAR, VAL>> constraints: The list of different constraints in the CSP
Hashtable<Variable, Integer> varIndexHash: A lookup table that stores the index of variable $X_i$ in the variables list
Hashtable<Variable, List<Constraint<VAR, VAL>>> cnet: This is an adjacency list representation of the constraint hypergraph

The class also contains the following useful methods:

CSP(): constructor that initializes an empty CSP
CSP(List<VAR> vars): constructor that initializes the CSP with given variables
void addVariable(VAR var): Adds a new variable to the CSP
List<VAR> getVariables(): Lists all variables currently in the CSP
void setDomain(VAR var, Domain<VAL> domain): Used to specify the domain of the variable var
Domain<VAL> getDomain(Variable var): Returns the domain of the variable var
boolean removeValueFromDomain(VAR var, VAL value): Modifies the domain of the variable var by removing a particular value from it
void addConstraint(Constraint<VAR, VAL> constraint): Adds a constraint to the CSP
boolean removeConstraint(Constraint<VAR, VAL> constraint): Removes a constraint from the CSP
List<Constraint<VAR, VAL>> getConstraints(): Returns all constraints in the CSP
List<Constraint<VAR, VAL>> getConstraints(Variable var): Returns all constraints that concern with the variable var
VAR getNeighbor(VAR var, Constraint<VAR, VAL> constraint): Returns the second variable $neighbor$ in the constraint for a binary constraint $<(var,neighbor),rel>$

Before moving further, let's talk about an Assignment. An assignment can be considered as a state in the CSP where values are assigned to some or all variables. An assignment that obeys each and every constraint is called a consistent assignment. If all variables have been assigned some value, then it's a complete assignment otherwise it's known as a partial assignment.

Example Problems

Map coloring

This simple problem is taken from the textbook (3rd edition: Section 6.1.1, Page 207). The task is simple. We need to color the regions in the australia map such that no two region sharing a boundary have the same color.

Only constraint we will be using in the map coloring CSP is the Alldiff constraint. Alldiff constraint is a global constraint (constraint involving arbitrary number of variables) that restricts the variables to not take the same value. For e.g., let $A$, $B$ and $C$ be variables with the same domain $D_A=D_B=D_C=\{1,2,5,6,7\}$. Then, the constraint Alldiff$(A,B,C)$ can be enumerated as $$\{(1,2,5),(1,2,6),(1,2,7),(1,5,6),(1,5,7),(1,6,7),(2,5,6),(2,5,7),(2,6,7),(5,6,7)\}$$

The map coloring problem can be represented as a CSP as follows:

variables: Each region in the map represents a variable in the CSP. For keeping things simple, we will name the variables with the initials of the region (e.g., Northern Territory -> NT). Thus, $X = \{WA,NT,Q,NSW,V,SA,T\}$
domains: The domain of a variable includes various colors that the corresponding region can be colored with. In this case, all the variables have the same domain consisting of colors red, green and blue. That is, $D_i = \{red,green,blue\}$ for $i=1,2,...,7$.
constraints: Since any set of regions having a common boundary can't be of same color, we introduce the constraints Alldiff$(WA,NT,SA)$, Alldiff$(NT,SA,Q)$, Alldiff$(SA,Q,NSW)$ and Alldiff$(SA,NSW,V)$. These Alldiff constraints can be simplified to binary NotEqualConstraint constraints (as shown in the constraint graph above), but we will proceed with Alldiff as the NotEqualConstraint is already implemented in the code repository.

Now that we have formally defined our problem as a CSP, we can begin writing code using the general classes and interfaces in the CSP package.

We begin by creating the variables for this CSP:



In [2]:

    
package aima.notebooks.csp;

import aima.core.search.csp.Variable;
import java.util.Arrays;
import java.util.List;

public class Variables {
    public static final Variable WA = new Variable("WA");
    public static final Variable NT = new Variable("NT");
    public static final Variable Q = new Variable("Q");
    public static final Variable NSW = new Variable("NSW");
    public static final Variable V = new Variable("V");
    public static final Variable SA = new Variable("SA");
    public static final Variable T = new Variable("T");
    
    public static final List<Variable> list = Arrays.asList(WA, NT, Q, NSW, V, SA, T);
    
    private Variables() {}
}









    Out[2]:





aima.notebooks.csp.Variables

What about domains? We will declare a class that encapsulates the domains of the variables we just instantiated.



In [3]:

    
package aima.notebooks.csp;

public class Values {
    public static final String RED = "red";
    public static final String GREEN = "green";
    public static final String BLUE = "blue";
    
    private Values() {}
}









    Out[3]:





aima.notebooks.csp.Values



In [4]:

    
package aima.notebooks.csp;

import aima.core.search.csp.Domain;
import java.util.List;
import java.util.Arrays;
import java.util.ArrayList;

public class Domains {
    private static final List<String> commonDomain = Arrays.asList(Values.RED, Values.GREEN, Values.BLUE);
    public static final Domain<String> WA = new Domain(new ArrayList<String>(commonDomain));
    public static final Domain<String> NT = new Domain(new ArrayList<String>(commonDomain));
    public static final Domain<String> Q = new Domain(new ArrayList<String>(commonDomain));
    public static final Domain<String> NSW = new Domain(new ArrayList<String>(commonDomain));
    public static final Domain<String> V = new Domain(new ArrayList<String>(commonDomain));
    public static final Domain<String> SA = new Domain(new ArrayList<String>(commonDomain));
    public static final Domain<String> T = new Domain(new ArrayList<String>(commonDomain));
    
    public static final List<Domain> list = Arrays.asList(WA, NT, Q, NSW, V, SA, T);
    
    private Domains() {}
}









    Out[4]:





aima.notebooks.csp.Domains

Last hurdle that remains are the constraints. There's no Alldiff constraint in the CSP package. But we can create a class that implements the Constraint interface and doesn't allows the variables to take same values. We will need the Assignment class to denote a mapping of variables to their values. This class contains useful query methods like isComplete(), isConsistent(), isSolution(), etc.. It also contains other methods to modify the state of the class.



In [26]:

    
package aima.notebooks.csp;

import aima.core.search.csp.Constraint;
import aima.core.search.csp.Variable;
import aima.core.search.csp.Assignment;
import aima.core.search.csp.examples.NotEqualConstraint;
import aima.core.util.math.permute.CombinationGenerator;
import java.util.List;
import java.util.ArrayList;
import java.util.HashSet;

public class AllDiffConstraint<VAR extends Variable, VAL> implements Constraint<VAR, VAL>, Cloneable {
    
    private List<VAR> variables;
    
    public AllDiffConstraint(List<VAR> variables) {
        this.variables = variables;
    }
    
    @Override
    public List<VAR> getScope() {
        return variables;
    }
    
    @Override
    public boolean isSatisfiedWith(Assignment<VAR, VAL> assignment) {
        HashSet<VAL> valueSet = new HashSet();
        for (VAR variable: variables) {
            if (assignment.contains(variable)) {
                VAL value = assignment.getValue(variable);
                if (!valueSet.add(value)) {
                    return false;
                }
            }
        }
        return true;
    }
    
    @Override
    public String toString() {
        StringBuilder sbl = new StringBuilder();
        sbl.append("AD(");
        for (Variable variable: variables.subList(0, variables.size() - 1)) {
            sbl.append(variable.toString()).append(", ");
        }
        sbl.append(variables.get(variables.size() - 1)).append(")");
        return sbl.toString();
    }
        
    public List<NotEqualConstraint> toNotEqualConstraint() {
        List<NotEqualConstraint> constraints = new ArrayList();
        CombinationGenerator.generateCombinations(variables, 2).forEach(
            list -> constraints.add(new NotEqualConstraint(list.get(0), list.get(1)))
        );
        return constraints;
    }
    
}









    Out[26]:





aima.notebooks.csp.AllDiffConstraint

Time to see the AllDiffConstraint class in action!



In [6]:

    
package aima.notebooks.csp;

import aima.core.search.csp.*;

Assignment<Variable, String> assignment = new Assignment();
assignment.add(Variables.WA, Values.BLUE);
assignment.add(Variables.NT, Values.RED);
assignment.add(Variables.SA, Values.GREEN);

Assignment<Variable, String> nonConsistentAssignment = assignment.clone();
nonConsistentAssignment.add(Variables.NSW, Values.RED);

AllDiffConstraint alldiff = new AllDiffConstraint(Variables.list);

return alldiff.isSatisfiedWith(assignment) + ", " + alldiff.isSatisfiedWith(nonConsistentAssignment);









    Out[6]:





true, false

We can now define the Map CSP constraints using the AllDiffConstraint class we just created.



In [7]:

    
package aima.notebooks.csp;

import static aima.notebooks.csp.Variables.*;
import java.util.List;
import java.util.Arrays;

public class Constraints {
    public static final List<AllDiffConstraint> list = Arrays.asList(
        new AllDiffConstraint(Arrays.asList(WA, NT, SA)),
        new AllDiffConstraint(Arrays.asList(NT, SA, Q)),
        new AllDiffConstraint(Arrays.asList(SA, Q, NSW)),
        new AllDiffConstraint(Arrays.asList(SA, NSW, V))
    );
    private Constraints() {}
}









    Out[7]:





aima.notebooks.csp.Constraints

We can now encapsulate the variables, their respective domains and the constraints involved in a class MapCSP.java that extends the CSP class in the csp package.



In [8]:

    
package aima.notebooks.csp;

import aima.core.search.csp.CSP;
import aima.core.search.csp.Variable;
import aima.core.search.csp.Domain;
import java.util.Iterator;

public class MapCSP extends CSP<Variable, String> {
    
    public MapCSP() {
        super(Variables.list);
        Iterator<Domain> domainIter = Domains.list.listIterator();
        Variables.list.forEach(
            variable -> super.setDomain(variable, domainIter.next())
        );
        Constraints.list.forEach(super::addConstraint);
    }
    
}









    Out[8]:





aima.notebooks.csp.MapCSP

Or we can instantiate an object of the CSP class and add the variables, domains and constraints manually using its public methods. The object thus created will represent our Map CSP. The code for this is very similar hence, it is not shown here. Now let's see our MapCSP class in action.



In [32]:

    
package aima.notebooks.csp;

import aima.core.search.csp.*;
import org.apache.commons.lang3.StringUtils;

MapCSP mapCSP = new MapCSP();
System.out.println("Constraints = " + mapCSP.getConstraints());
String line = new String(new char[101]).replace('\0', '-');
System.out.println(line);
System.out.format("| %-9S | %18S |%66S|\n", "variables", StringUtils.center("domains", 18),
                  StringUtils.center("corresponding constraints", 66));
System.out.println(line);
mapCSP.getVariables().forEach(
    var -> System.out.format("| %-9s | %-18s | %-64s |%n", var, 
                             mapCSP.getDomain(var), mapCSP.getConstraints(var))
);
System.out.println(line);









    



Constraints = [AD(WA, NT, SA), AD(NT, SA, Q), AD(SA, Q, NSW), AD(SA, NSW, V)]
-----------------------------------------------------------------------------------------------------
| VARIABLES |      DOMAINS       |                    CORRESPONDING CONSTRAINTS                     |
-----------------------------------------------------------------------------------------------------
| WA        | {red, green, blue} | [AD(WA, NT, SA)]                                                 |
| NT        | {red, green, blue} | [AD(WA, NT, SA), AD(NT, SA, Q)]                                  |
| Q         | {red, green, blue} | [AD(NT, SA, Q), AD(SA, Q, NSW)]                                  |
| NSW       | {red, green, blue} | [AD(SA, Q, NSW), AD(SA, NSW, V)]                                 |
| V         | {red, green, blue} | [AD(SA, NSW, V)]                                                 |
| SA        | {red, green, blue} | [AD(WA, NT, SA), AD(NT, SA, Q), AD(SA, Q, NSW), AD(SA, NSW, V)]  |
| T         | {red, green, blue} | []                                                               |
-----------------------------------------------------------------------------------------------------






    Out[32]:





null

Constraint Propagation: Inference in CSPs

We can do more than just search in the state space of a CSP problem. We can do constraint propagation, a technique used to reduce domain of variables in the CSP hence reducing the search space. This type of inference is very powerful since it can alone be used to solve many problems (without the need of applying any sort of search algorithm).

Arc Consistency algorithm works on binary CSPs. Here's the formal definition of an arc-consistent variable from the textbook:

A variable in a CSP is arc-consistent if every value in its domain satisfies the variable's binary constraints. More formally, $X_i$ is arc-consistent ith respect to another variable $X_j$ if for every value in the current domain $D_i$ there is some value in the domain $D_j$ that satisfies the binary constraint on the arc $(X_i, X_j)$. A network is arc-consistent if every variable is arc consistent with every other variable.

AC-3 is one of the most popular algorithm for estabilishing arc consistency in a constraint graph. Let's take a look at it's pseudocode.



In [10]:

    
%%python
from notebookUtils import *
pseudocode("AC-3")









    Out[10]:




AIMA3e
function AC-3(csp) returns false if an inconsistency is found and true otherwise

 inputs: csp, a binary CSP with components (X, D, C)

 local variables: queue, a queue of arcs, initially all the arcs in csp
 while queue is not empty do

   (X_i, X_j) ← REMOVE-FIRST(queue)

   if REVISE(csp, X_i, X_j) then

     if size of D_i = 0 then return false

     for each X_k in X_i.NEIGHBORS − {X_j} do

      add(X_k, X_i) to queue

 return true

function REVISE(csp, X_i, X_j) returns true iff we revise the domain of X_i

 revised ← false

 for each x in D_i do

   if no value y in D_j allows (x, y) to satisfy the constraint between  X_i and X_j then

    delete x from D_i

    revised ← true

 return revised

Figure ?? The arc-consistency algorithm AC-3. After applying AC-3, either every arc is arc-consistent, or some variable has an empty domain, indicating that the CSP cannot be solved. The name "AC-3" was used by the algorithm's inventor (Mackworth, 1977) because it's the third version developed in the paper.

The AC-3 algorithm in csp package can be found here. It implements an interface InferenceStrategy which have the following two methods:

InferenceLog apply(CSP<VAR, VAL> csp): This method applies the inference strategy on the whole CSP (preferably used before Search starts to reduce the search state space)
InferenceLog<VAR, VAL> apply(CSP<VAR, VAL> csp, Assignment<VAR, VAL> assignment, VAR var): This overloaded method is applied in the course of a search (we'll talk about this later)

The InferenceLog class is an extremely useful interface which provides information about the inference carried out that has following three methods:

boolean isEmpty(): returns true if no changes occurred in the CSP after inference procedure was applied
boolean inconsistencyFound(): returns true if for a variable an "empty domain" was inferred. If an empty domain is inferred, it implies that no consistent assignment is possible for the CSP.
void undo(CSP<VAR, VAL> csp): this method is used to undo the inference carried out. That is, it restores the CSP to the state it was before the inference strategy was applied.

Let's use the AC-3 algorithm on a simple constraint $Y=X^2$. Let the domain of $X$ be $D_X={0,1,2,3,4,5}$ and the domain of $Y$, $D_Y={0,1,3,5,9,12,16}$. Let's see the how the AC3 algorithm reduces the domains of these variables.



In [11]:

    
package aima.notebooks.csp;

import aima.core.search.csp.*;
import aima.core.search.csp.inference.AC3Strategy;
import java.util.*;
import org.apache.commons.lang3.StringUtils;

Variable x = new Variable("X");
Variable y = new Variable("Y");
CSP<Variable, Integer> csp = new CSP(Arrays.asList(x, y));
csp.setDomain(x, new Domain<Integer>(0,1,2,3,4,5));
csp.setDomain(y, new Domain<Integer>(0,1,3,5,9,12,16));
csp.addConstraint(new Constraint<Variable, Integer>() {
    public List<Variable> getScope() {
        return Arrays.asList(x, y);
    }
    public boolean isSatisfiedWith(Assignment<Variable, Integer> assignment) {
        return assignment.getValue(y) == assignment.getValue(x) * assignment.getValue(x);
    }
});

// Let's apply the ac3 inference algorithms on this two variable csp
AC3Strategy ac3Strategy = new AC3Strategy();
ac3Strategy.apply(csp).isEmpty();
String line = new String(new char[34]).replace('\0', '-');
System.out.println(line);
System.out.format("| %-12S | %-15S |%n","variable","domain");
System.out.println(line);
for (Variable var: csp.getVariables()) {
    System.out.format("| %-12S | %-15S |%n", var.getName(),csp.getDomain(var));
}
System.out.println(line);









    



----------------------------------
| VARIABLE     | DOMAIN          |
----------------------------------
| X            | {0, 1, 3, 4}    |
| Y            | {0, 1, 9, 16}   |
----------------------------------






    Out[11]:





null

The reduced domains of $X$ and $Y$ are now arc-consistent.