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
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$:
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 CSPList<Domain<VAL>> domains: The corresponding domains of the variablesList<Constraint<VAR, VAL>> constraints: The list of different constraints in the CSPHashtable<Variable, Integer> varIndexHash: A lookup table that stores the index of variable $X_i$ in the variables listHashtable<Variable, List<Constraint<VAR, VAL>>> cnet: This is an adjacency list representation of the constraint hypergraphThe class also contains the following useful methods:
CSP(): constructor that initializes an empty CSPCSP(List<VAR> vars): constructor that initializes the CSP with given variablesvoid addVariable(VAR var): Adds a new variable to the CSPList<VAR> getVariables(): Lists all variables currently in the CSPvoid setDomain(VAR var, Domain<VAL> domain): Used to specify the domain of the variable varDomain<VAL> getDomain(Variable var): Returns the domain of the variable varboolean removeValueFromDomain(VAR var, VAL value): Modifies the domain of the variable var by removing a particular value from itvoid addConstraint(Constraint<VAR, VAL> constraint): Adds a constraint to the CSPboolean removeConstraint(Constraint<VAR, VAL> constraint): Removes a constraint from the CSPList<Constraint<VAR, VAL>> getConstraints(): Returns all constraints in the CSPList<Constraint<VAR, VAL>> getConstraints(Variable var): Returns all constraints that concern with the variable varVAR 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. Hence a solution to a CSP is a consistent, complete assignment.
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:
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(NSW, WA, NT, Q, SA, V, T);
private Variables() {}
}
Out[2]:
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]:
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]:
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 [5]:
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[5]:
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]:
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]:
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]:
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 [9]:
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);
Out[9]:
Above map coloring problem can be visualized here.
Many real-world CSP's include preference constraints indicating which solutions are preferred. Preference constraints can often be encoded as costs on individual variable assignments. With this formulation, CSPs with the preferences can be solved with optimization search methods, either path based or local. We call such a problem a constraint optimization problem.
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]:
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 appliedboolean 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);
Out[11]:
The reduced domains of $X$ and $Y$ are now arc-consistent.
Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables. A two-variable set $\{X_i, X_j\}$ is path consistent with respect to third variable $X_m$ if, for every assignment $\{X_i = a, X_j = b\}$ consistent with the constraints on $\{X_i, X_j\}$, there is assignment to $X_m$ the satisfies the constraints on $\{X_i, X_m\}$ and $\{X_m, X_j\}$. This is path consistency.
A CSP is $k$-consistent if, for any set of $k-1$ variables and for any consistent assignment to those variables, a consistent value can always be assigned to any $k_th$ variable. A CSP is strongly $k$-consistent if it is $k$-consistent and is also $(k-1)$-consistent, $(k-2)$-consistent,...all the way down to 1-consistent. Now suppose we have a CSP with $n$ nodes and make it strongly $n$-consistent. We can then solve the problem as follows: First, we choose a consistent value for $X_1$. We are then guaranteed to choose a value for $X_2$ because the graph is 2-consistent, for $X_3$ because it is 3-consistent and so on.
Many CSPs cannot be solved by inference alone; there comes a time when we must SEARCH for a solution. We could apply a standard depth-first search. A state would be a partial assignment, and an action would be adding $var = value$ to the assignment. But for a CSP with $n$ variables of domain size $d$, the branching factor at the top level is $nd$ because any of the $d$ values can be assigned to any of $n$ variables. At next level, the branching factor is $(n-1)d$, and so on for the $n$ levels. We generate a tree with $n!.d^n$ leaves, even though there are only $d^n$ possible complete assignments. Note that, this formulation ignores a crucial property common to all the CSPs: commutativity. CSPs are commutative because when assigning values to the variable, we reach the same partial assignment regardless of the order. Therefore, we need to consider only a single variable at each node in the search tree. With this restriction, the number of leaves is $d^n$, as we would hope.
The term backtracking search is used for a depth-first search that chooses values for one variable at a time and backtracks when a variable has no legal values left to assign. It repeatedly chooses an unassigned variable, and then tries all values in the domain of that variable in turn, trying to find a solution. If an inconsistency is detected, then BACKTRACK returns a failure, causing the previous call to try another value.
Let's have a look at its pseudo code.
In [12]:
%%python
from notebookUtils import *
pseudocode('Backtracking Search')
Out[12]:
Above pseudo code is implemented in the abstract class named AbstractBacktrackingSolver.java in the code repository. Let's try to solve the map coloring problem using backtracking search.
In [13]:
package aima.notebooks.csp;
import aima.core.search.csp.*;
MapCSP csp = new MapCSP();
CspSolver<Variable, String> solver = new FlexibleBacktrackingSolver<>();
CspListener.StepCounter<Variable, String> stepCounter = new CspListener.StepCounter<>();
solver.addCspListener(stepCounter);
stepCounter.reset();
System.out.println("Map Coloring (Backtracking)");
System.out.println(solver.solve(csp));
System.out.println(stepCounter.getResults() + "\n");
Out[13]:
Notice that, we can add some sophistication to the unspecified functions in the above algorithm in order to improve its performance. Let's take a look at these sophistications one by one:-
- Which variable should be assigned next?
var <- SELECT-UNASSIGNED-VARIABLE(csp)- In what order its value be tried?
ORDER-DOMAIN-VALUES(var, assignment, csp)
Choosing the variables with the fewest legal values generally results in the most efficient search. It is known as the minimum-remaining-values (MRV) heuristic. If some variable X has no legal values left, the MRV heuristic will select X and failure will be detected immediately-avoiding pointless searches through other variables. However, the MRV heuristic doesn't help at all if all the variables have the same number of legal values left in their domains. In such cases, the degree heuristic comes in handy. It attempts to reduce the branching factor on future choices by selecting the variable that is involved in the largest number of constraints on other unassigned variables. The minimum-remaining-value heuristic is usually a more powerful guide, but the degree heuristic can be useful as the tie-breaker.
Once a variable has been selected, the algorithm must decide on the order in which to examine its values. For this, the least-constraint-value heuristic can be effective in some cases. It prefers the value that rules out the fewest choices for the neighboring values in the constraint graph.
These heuristics are implemented here in the code repository.
What inferences should be performed at each step in the search?
inferences ← INFERENCE(csp, var, value)
Every time we make a choice of a value for a variable, we infer new domain reductions on the neighboring variables. One of the simplest forms of inference is called forward checking. Whenever a variable X is assigned, the forward-checking process establishes arc consistency for it: for each unassigned variable Y that is connected to X by a constraint, delete from Y's Domain any value that is inconsistent with the value chosen for X. Remember that forward checking only does arc consistency inferences.
We'll now set these heuristics in our map coloring problem and will compare the results. (Note that, for this comparison, we can't use the CSP with AllDiff constraints as they are not binary. First, we need to create a MapCSP class with NotEqualConstraint for this problem.)
In [14]:
package aima.notebooks.csp;
import static aima.notebooks.csp.Variables.*;
import aima.core.search.csp.examples.NotEqualConstraint;
import java.util.List;
import java.util.Arrays;
public class BinaryConstraints {
public static final List<NotEqualConstraint> list = Arrays.asList(
new NotEqualConstraint<>(WA, NT),
new NotEqualConstraint<>(WA, SA),
new NotEqualConstraint<>(NT, SA),
new NotEqualConstraint<>(NT, Q),
new NotEqualConstraint<>(SA, Q),
new NotEqualConstraint<>(SA, NSW),
new NotEqualConstraint<>(SA, V),
new NotEqualConstraint<>(Q, NSW),
new NotEqualConstraint<>(NSW, V)
);
private BinaryConstraints() {}
}
Out[14]:
In [15]:
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 MapCSPwithBinaryConstraints extends CSP<Variable, String> {
public MapCSPwithBinaryConstraints() {
super(Variables.list);
Iterator<Domain> domainIter = Domains.list.listIterator();
Variables.list.forEach(
variable -> super.setDomain(variable, domainIter.next())
);
BinaryConstraints.list.forEach(super::addConstraint);
}
}
Out[15]:
In [16]:
package aima.notebooks.csp;
import aima.core.search.csp.*;
MapCSPwithBinaryConstraints mapCSP = new MapCSPwithBinaryConstraints();
CspListener.StepCounter<Variable, String> stepCounter = new CspListener.StepCounter<>();
CspSolver<Variable, String> solver;
solver = new FlexibleBacktrackingSolver<>();
solver.addCspListener(stepCounter);
stepCounter.reset();
System.out.println("Map Coloring (Backtracking)");
System.out.println(solver.solve(mapCSP));
System.out.println(stepCounter.getResults() + "\n");
solver = new FlexibleBacktrackingSolver<Variable, String>().setAll();
solver.addCspListener(stepCounter);
stepCounter.reset();
System.out.println("Map Coloring (Backtracking + MRV & DEG + LCV + AC3)");
System.out.println(solver.solve(mapCSP));
System.out.println(stepCounter.getResults() + "\n");
Out[16]:
Local search uses a complete state formation i.e. the initial state assigns a value to every variable, and the search changes the value of one variable at a time. Typically, the initial guess violates several constraints. The point of local search is to eliminate the violated constraints. In choosing a new value for a variable, the most obvious heuristic is to select the value that results in the minimum number of conflicts with other variables- the min-conflicts heuristic.
Let's take a look at the pseudo code of the local search algorithm with the min-conflicts heuristic function.
In [17]:
%%python
from notebookUtils import *
pseudocode("Min Conflicts")
Out[17]:
Above pseudo code is implemented here in the code repository. Let's solve the map coloring problem using local search.
In [18]:
package aima.notebooks.csp;
import aima.core.search.csp.*;
MapCSP mapCSP = new MapCSP();
CspListener.StepCounter<Variable, String> stepCounter = new CspListener.StepCounter<>();
CspSolver<Variable, String> solver = new MinConflictsSolver<>(1000);
solver.addCspListener(stepCounter);
stepCounter.reset();
System.out.println("Map Coloring (Minimum Conflicts)");
System.out.println(solver.solve(mapCSP));
System.out.println(stepCounter.getResults() + "\n");
Out[18]:
Here, we'll examine the ways in which the structure of the problem can be used to find solutions quickly. For example, any tree-structured CSP can be solved linear in the number of variables(constraint graph is a tree when any two variables are connected by only one path). The key is the new notion of consistency called directed arc consistency or DAC. A CSP is defined directed arc-consistent under any ordering of variables $X_1, X_2,...., X_n$ if and only if every $X_i$ is arc consistent with each $X_j$ for $j>i$.
To solve a tree-structured CSP, first pick any variable to be the root of the tree, and choose an ordering of the variable such that each variable appears after its parent in the tree. Such an ordering is called a topological sort. Any tree with $n$ nodes has $n-1$ arcs, so we can make this graph directed arc consistent in $O(n)$ steps. Once we have a directed arc consistent graph, we can just march down the list of variables and choose any remaining value. Since each link from parent to child is arc consistent, we know that for any value we choose for the parent, there will be a valid value left to choose for the child. That means we don't have to backtrack; we can move linearly through the variables. Let's take a look at the pseudo code of this algorithm.
In [19]:
%%python
from notebookUtils import *
pseudocode("Tree CSP Solver")
Out[19]:
Implementation of this pseudo code can be found here in the code repository. We'll now solve a tree structured CSP described in Figure 6.12(b) of the textbook using this algorithm.
In [20]:
package aima.notebooks.csp;
import aima.core.search.csp.*;
import aima.core.search.csp.examples.NotEqualConstraint;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
public class TreeCSP extends CSP<Variable, String> {
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 List<Variable> variableList = Arrays.asList(WA, NT, Q, NSW, V);
public static final String RED = "red";
public static final String GREEN = "green";
public static final String BLUE = "blue";
private static final List<String> commonDomain = Arrays.asList(Values.RED, Values.GREEN, Values.BLUE);
public static final Domain<String> domainWA = new Domain(new ArrayList<String>(commonDomain));
public static final Domain<String> domainNT = new Domain(new ArrayList<String>(commonDomain));
public static final Domain<String> domainQ = new Domain(new ArrayList<String>(commonDomain));
public static final Domain<String> domainNSW = new Domain(new ArrayList<String>(commonDomain));
public static final Domain<String> domainV = new Domain(new ArrayList<String>(commonDomain));
public static final List<Domain> domainList = Arrays.asList(domainWA, domainNT, domainQ, domainNSW, domainV);
public static final List<NotEqualConstraint> constraintList = Arrays.asList(
new NotEqualConstraint<>(WA, NT),
new NotEqualConstraint<>(NT, Q),
new NotEqualConstraint<>(Q, NSW),
new NotEqualConstraint<>(NSW, V)
);
public TreeCSP() {
super(variableList);
Iterator<Domain> domainIter = domainList.listIterator();
variableList.forEach(
variable -> super.setDomain(variable, domainIter.next())
);
constraintList.forEach(super::addConstraint);
}
}
Out[20]:
In [22]:
package aima.notebooks.csp;
import aima.core.search.csp.*;
TreeCSP treeCSP = new TreeCSP();
CspListener.StepCounter<Variable, String> stepCounter = new CspListener.StepCounter<>();
CspSolver<Variable, String> solver = new TreeCspSolver<>();
solver.addCspListener(stepCounter);
stepCounter.reset();
System.out.println("Map Coloring (Tree CSP)");
System.out.println(solver.solve(treeCSP));
System.out.println(stepCounter.getResults() + "\n");
Out[22]:
Now that we have an efficient algorithm for trees, we can consider the ways by which a constraint graph can be reduced to a tree. There are two primary ways to do this, one based on removing nodes and one based on collapsing nodes together.
The first approach involves assigning values to some variables so that the remaining variables form a tree. We can then solve the remaining tree with the algorithm discussed above and thus solve the whole problem. The general algorithm is as follows:
The second approach is based on constructing a tree decomposition of the constraint graph into a set of connected subproblems. Each subproblem is solved independently, and the resulting solutions are then combined. A tree decomposition must satisfy the following three requirements:
The first two conditions ensure that all the variables and constraints are represented in the decomposition. The third condition simply reflects the constraint that any given variable must have the same value in every subproblem in which it appears. We can solve each subproblem independently; if anyone has no solution, the entire problem has no solution. If we can solve all the subproblems, then we attempt to construct a global solution as follows. First, we view each subproblem as a "mega-variable" whose domain is the set of all solutions for the subproblem. The constraints between the subproblem simply insist that the subproblem solutions agree on their shared variables.