Constraint Satisfaction

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

Examples§

Map Colouring§

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§

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.

Backtracking§

The basic search for CSPs strongly resembles DFS.

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.

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.

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

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