Motivation§

Constraint satisfaction problems are a large family of problems that are solvable through specialised search algorithms.

Typically, the solution to these problems involves finding a configuration of the world that satisfies the constraints that restrict the possible solutions.

Examples:

• Limited resources that can only be used one at a time
• Satisfying constraints on the order of precedence
• Assignment of tasks to capable agents

Constraint Satisfaction Problems (CSPs)

The formal framework behind CSPs are:

• Variables, $\mathcal{V} = \{v_1, v_2, \dots, v_i\}.$
• Domains, $\text{dom}(v_k) = \{a_1, \dots, a_n\}$, a finite set of possible valuations for each variable.
• Constraints
• The form of constraints may vary with the problem in hand, but abstractly a constraint involving variables can be viewed as a restriction on the allowed set of tuples in the Cartesian product of domains, $$C_j = \{\langle x_1, \dots, x_n | x_k \in \text{dom}(v_k)\rangle\} \subseteq \prod_{k \in [1\dots c]} \text{dom}(v_k).$$
• Solution – a complete variable assignment that satisfies all constraints, some CSPs may have multiple solutions.

Examples§

Map Colouring§

Four Color Theorem

In general, we need at most four colors to color the individual partitions of a map such that no two adjacent partitions share the same colour.

(In 1997, this problem became one of the first major problems to be proved via computer.)

TODO: Add map of Australia with the six states + Northern Territory labelled.

One common example to illustrate this is to attempt to colour the six states and the Northern Territory of Australia using only three colours.

Here, we define a variable for each state – each variable will hold the state’s colouration,

$$\mathcal{V} = \{\text{WA}, \text{NT}, \text{SA}, \text{Q}, \text{NSW}, \text{V}, \text{T}\}.$$

Each variable will have the same domain – i.e. each variable can be one of red, green, or blue.

$$\forall\,S \in \mathcal{V},\ \text{dom}(S) = \{\text{R}, \text{G}, \text{B}\}$$

The (nonexhaustive) list of constraints are,

$$\text{WA} \neq \text{NT}, \text{WA} \neq \text{SA}, \text{NT} \neq \text{SA}, \dots$$

Then, a candidate solution would be

$$\{\text{WA} = \text{R}, \text{NT} = \text{G}, \text{SA} = \text{B}, \text{Q} = \text{R}, \text{NSW} = \text{G}, \text{V} = \text{R}, \text{T} = \text{G}\}.$$

There exists other solutions to this problem aside from the candidate above, suppose we added a constraint such that $\text{WA} = \text{G}$ or $\text{WA} \neq \text{R},$ then a solution for that instance of the problem could be

$$\{\text{WA} = \text{G}, \text{NT} = \text{R}, \text{SA} = \text{B}, \text{Q} = \text{G}, \text{NSW} = \text{R}, \text{V} = \text{G}, \text{T} = \text{R}\}.$$

Cryptarithmetic§

A basic version of the problem is, how may we assign valuations to the symbols in the expression $TWO + TWO = FOUR$ such that it holds?

In this case, we let the variables $\mathcal{V} = \{T, W, O, F, U, R\},$ $\forall\,S \in \mathcal{V},\ \text{dom}(S) = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}.$

Constraints:

• All bindings are distinct, i.e. $T \neq O, F \neq T, \dots$
• Leading symbols may not be zero, i.e. “two” starts with “t”, therefore $T \neq 0,$ likewise with “f” in “four”.
• Rules of carrying over a remainder must follow,
• For example, suppose we wanted to evaluate $O + O = R,$ wlog. assume $O = 6.$
• Then, $O + O = R = 11.$ Note that $11 \not\in \text{dom}(R),$ therefore, we must introduce a variable $c_1$ for the carry with $\text{dom}(c_1) = \{0, 1\}.$
• Using $c_1,$ we can now write $O + O = R - 10c_1.$

For the example problem, a possible solution is $\{T = 7, W = 6, O = 5, F = 1, U = 3, R = 0\}.$

Then, $TWO + TWO = FOUR$ is equivalent to saying $765 + 765 = 1530.$

$N$-queens§

We’ve discussed this problem many times at this point, refer to previous lectures or Wikipedia for an explanation.

Here, we formulate the question as asking: for a given column $i$, what row is the queen in?

Using the framework, $\mathcal{V} = \{Q_1, Q_2, Q_3, \dots, Q_N\},$ and $\forall\,Q \in \mathcal{V}, \text{dom}(Q) = \{1, 2, 3, \dots, N\}.$

Along with the constraints,

• No shared rows: $\forall\,i, j \in [1\dots N], i \neq j \iff Q_i \neq Q_j$
• No shared diagonal: $\forall\,i, j \in [1\dots N], |Q_i - Q_j| \neq |i - j|$

Then, each $Q_i \in \mathcal{V}$ corresponds to the queen in the $i$th column, the value of $Q_i$ represents the row that it belongs to.

An alternative formulation would be creating a subset of $\text{dom}(Q) \times \text{dom}(Q)$ that describes all allowable pairs between any two queens.

Constraint Graphs§

Constraint Graphs

A constraint graph has nodes that correspond to each variable in a CSP, each node may contain a value consistent with the domain of its associated variable.

The edges in the graph correspond to the constraints of the CSP.

Australia Map Coloring

Below is a visualisation of how coloring the map of the states of Australia plus Northern Territory may look like as a constraint graph.

Then, each node in the graph may have a value $R, G,$ or $B.$

Take the constraint that the Northern Territory may not be colored the same as Queensland; so, we connect the nodes NT and Q with an edge.

The edge between NT and Q may only link between pairs of nodes <R, G>, <G, R>, <R, B>, <B, R>, <B, G>, or <G, B>.

In the case of binary constraints, constraint graphs can be easily represented as shown above. For ternary or $n$-order constraints, we end up with a hypergraph where there exists edges connecting three or more nodes.

Decomposition of a Hypergraph into Binary Constraint Graph

It is possible to perform a decomposition of a hypergraph into a binary graph. First, we create new nodes for each constraint, the new nodes are labelled with all possible tuples based on the Cartesian product of domains. The new nodes are then connected to the constrained variables, with the edges labelled to enforce consistency of the variable assignment with position in tuple.

Below, we use the cryptarithmetic problem as a hypergraph example.

For the decomposition, the new nodes that were inserted are represented using a square, the original nodes in circles.

The domains for a few of the nodes are as follows:

• $\text{dom}(O) = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$
• $\text{dom}(A) = \text{dom}(\langle O, R, C_1\rangle) = \{\langle 0, 0, 0\rangle, \langle 0, 1, 0\rangle, \langle 1, 0, 0\rangle, \dots, \langle 9, 9, 1\rangle\}$
• $\text{dom}(C_1) = \{0, 1\}$

The possible labels for the edges:

• $E_1 = [0, \langle 0, x, y\rangle],$ $[1, \langle 1, x, y\rangle], \dots,$ $[9, \langle 9, x, y\rangle]$
• $E_2 = [0, \langle x, y, 0\rangle], \dots,$ $[1, \langle x, y, 1\rangle]$
• $E_3,$ the edge connecting nodes $O$ and $B,$ has possibilities $[0, \langle x, 0, y\rangle],$ $[1, \langle x, 1, y\rangle], \dots,$ $[9, \langle x, 9, y\rangle]$

Backtracking§

The basic search for CSPs strongly resembles DFS.

Backtracking Search

In backtracking search, each node represents the possible assignments for each variable.

The root node represents the empty assignment.

For a chosen variable, the branches represent the choices from the domain, each level assigns one additional variable.

Australia Map Coloring

Reusing the Australian states and Northern Territory example,

the backtracking search tree may look like

The important differences between backtracking and DFS are that:

1. the backtracking tree has uniform depth of the number of variables, all goal nodes appear at the fringe of the tree, and
2. as soon as any variable assignment causes an inconsistency, the subtree is pruned and we backtrack immediately.
function BacktrackingSearch(csp) -> Assignment? {
let empty_assignment : Assignment = {}

return Backtrack(csp, empty_assignment)
}

function Backtrack(csp, assignment) -> Assignment? {
if assignment.is_complete()
return assignment

let variable := SelectUnassignedVariable(csp, assignment)

for value in OrderDomainValues(csp, variable, assignment) {
if assignment.consistent_with(value) {
assignment.set(variable, value)
let result := Backtrack(csp, assignment)

if result
return result

assignment.unset(variable)
}
}

return None
}


The helpers SelectUnassignedVariable() and OrderDomainValues() can do better than randomly choosing variables/values; instead we can use the MRV and LCV heuristics, respectively.

Minimum Remaining Values (MRV) Heuristic

Given a partial assignment, some variable bindings may preclude choices in the domains for unbound variables based on constraints.

For each unbound variable, first rule out values that are inconsistent with current assignment. Then, choose the variable with the fewest choices (or the variable with the minimum remaining values).

The best case of MRV occurs if there exists a variable with only one valid choice, and it takes it. MRV ensures that backtracking occurs sooner.

Least Constraining Value (LCV) Heuristic

Once a variable is chosen, the order in which we attempt to assign its value also matters.

It is prudent to choose a value that would remove the fewest choices for the remaining variables.

By keeping as many options open, LCV may prevent premature backtracking.

Degree Heuristic

If the domains for the variables have the same cardinality, we may choose the variable that is involved with the most constraints amongst the other unassigned variables.

The degree heuristic can be thought of by removing all assigned nodes in a constraint graph, then finding the node with the highest degree.