Class Notes

Lab 03

Constraint Satisfaction Problems

CSP Backtracking Min-conflicts N-Queens
Work in progress These notes are still being written and reviewed: content may change, and some parts may still contain mistakes.

Overview of the lab

  1. Introduction to Constraint Satisfaction Problems (CSP)
  2. Solving Constraint Satisfaction Problems
  3. Min-conflicts
  4. Solving the N-queens problem

Introduction to Constraint Satisfaction Problems

Unlike search problems, CSPs are a type of identification problem: problems in which we must simply identify whether a state is a goal state or not, with no regard to how we arrive at that goal. CSPs are defined by three factors:

  1. Variables — CSPs possess a set of N variables X1, …, XN that can each take on a single value from some defined set of values.
  2. Domain — a set {x1, …, xd} representing all possible values that a CSP variable can take on.
  3. Constraints — constraints define restrictions on the values of variables, potentially with regard to other variables.
📐 Shortly, a CSP

• state is defined by variables Xi with values from domain Di
• goal test is a set of constraints specifying allowable combinations of values for subsets of variables

Example

Example: Map colouring

Map colouring solves the problem where we're given a set of colours and must colour a map such that no two adjacent states or regions have the same colour.

  • Variables: WA, NT, Q, NSW, V, SA, T
  • Domains: Di = {red, green, blue}
  • Constraints: adjacent regions must have different colours, e.g., WA ≠ NT (if the language allows this), or (WA, NT) ∈ {(red, green), (red, blue), (green, red), (green, blue), …}
  • Solutions are assignments satisfying all constraints, e.g., {WA = red, NT = green, Q = red, NSW = green, V = red, SA = blue, T = green}

The map and its constraint graph below are linked. They start with the solution above; click a region or a node to cycle its colour (none → red → green → blue) and watch violated constraints light up.

Map of Australia

Constraint graph

Constraint graph

Constraint satisfaction problems are often represented as constraint graphs, where nodes represent variables and edges represent constraints between them. In the map-colouring problem the constraints are simply that no two adjacent states can be the same colour — so drawing an edge between every pair of adjacent states gives the constraint graph above.

There are many different types of constraints, and each is handled slightly differently:

  • Unary constraints — involve a single variable in the CSP. They are not represented in constraint graphs, instead simply being used to prune the domain of the variable they constrain when necessary, e.g. SA ≠ green.
  • Binary constraints — involve two variables. They're represented in constraint graphs as traditional graph edges, e.g. SA ≠ WA.
  • Higher-order constraints — constraints involving three or more variables can also be represented with edges in a CSP graph.
  • Preferences (soft constraints) — e.g., red is better than green; often representable by a cost for each variable assignment → constrained optimization problems.

Example: University course timetabling

The variables are the assignment of a time slot and a room to each class (e.g., specific lectures, tutorials, and labs): V = {C1, C2, …, Cn}. The domain for each variable Ci is a set of possible (Time Slot, Room) pairs, but other things should be taken into account, which leads to higher-order constraints:

Maximum capacity (order k ≥ 3)

Ensures that the total number of students scheduled to be in the same room at the same time does not exceed the room's maximum capacity.

  • Room (R): the capacity is a property of the room.
  • Time slot (T): the simultaneous usage.
  • Classes (Ci, Cj, …): the classes assigned to that room and time.

Professor / student availability and load (order ≥ 3)

Constraints related to the workload or availability of a single resource (like a professor or a pool of shared equipment) across multiple classes.

  • Professor (P): a shared resource.
  • Classes (Ci, Cj, Ck, …): the classes taught by that professor.
  • Time slots (Ti, Tj, Tk, …): the scheduled times.

E.g., a professor P cannot teach more than 3 classes on any given day, or they must have a 1-hour break between consecutive classes.

Real-world CSPs

  • Assignment problems
  • Timetabling problems
  • Transportation scheduling
Backtracking

Solving Constraint Satisfaction Problems

Constraint satisfaction problems are traditionally solved using backtracking. Backtracking is an optimization on depth-first search used specifically for the problem of constraint satisfaction, with improvements coming from two main principles:

  1. Fix an ordering for variables, and select values for variables in this order — because assignments are commutative (e.g. assigning WA = Red, NT = Green is identical to NT = Green, WA = Red).
  2. When selecting values for a variable, only select values that don't conflict with any previously assigned values. If no such values exist, backtrack and return to the previous variable, changing its value.

The most used techniques are variants of:

📐 Minimum Remaining Values (MRV) — which variable next?

When selecting which variable to assign next, an MRV policy chooses whichever unassigned variable has the fewest valid remaining values (the most constrained variable). This is intuitive in the sense that the most constrained variable is most likely to run out of possible values and result in backtracking if left unassigned, and so it's best to assign a value to it sooner rather than later.

📐 Least Constraining Value (LCV) — which value next?

Similarly, when selecting which value to assign next, a good policy is to select the value that prunes the fewest values from the domains of the remaining unassigned variables. Notably, this requires additional computation (e.g. rerunning arc consistency / forward checking or other filtering methods for each value to find the LCV), but can still yield speed gains depending on usage.

Step through backtracking

Map colouring with the deliberately bad variable order WA, NSW, NT, Q, SA, V, T and value order red, green, blue. Plain backtracking only notices a problem when it tries to colour SA. Turn on forward checking to see the dead end earlier (an empty domain), and MRV to avoid it altogether. Try LCV on its own too: here it still picks red for NSW (the value that rules out the fewest options) and runs into the same dead end — MRV and LCV are heuristics, not guarantees.

0
assignments
0
backtracks
Domains
Search log
Min-conflicts

Min-conflicts

Start with some random assignment to values, then iteratively select a random conflicted variable and reassign its value to the one that violates the fewest constraints until no more constraint violations exist (a policy known as the min-conflicts heuristic). Under such a policy, constraint satisfaction problems like N-queens become both very time-efficient and space-efficient to solve.

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal. It is an example of the more general n-queens problem of placing n non-attacking queens on an n×n chessboard, for which solutions exist for all natural numbers n with the exception of n = 2 and n = 3.

For example, with 4 queens we arrive at a solution after only 2 iterations:

♛♛♛♛h = 5♛♛♛♛h = 2♛♛♛♛h = 0

h(n) = number of attacks (each line is one pair of queens attacking each other).

N-Queens

Solving the N-queens problem

n = the size of the board. Each queen should be in a different column, so we represent the queens by the column they are in: Queen0 in column0, Queen1 in column1, …, Queenn−1 in columnn−1.

To track the conflicts and in which row Queeni is positioned we use the following arrays:

  • queenPosition — keeps track in which row Queeni is
  • conflictRows — number of queens in each row
  • conflictPositiveDiagonals — number of queens in each positive diagonal
  • conflictNegativeDiagonals — number of queens in each negative diagonal

The number of positive / negative diagonals in an n×n matrix is 2n − 1:

  • Accessing the i-th positive diagonal: (row + col)
  • Accessing the i-th negative diagonal: (n − 1 − row + col)

h(n) = total number of conflicts on the board

Algorithm

  1. Initialize the starting positions of the queens randomly.
  2. Until the number of conflicts is zero:
    • take a random conflicted queen and remove her from the current row
    • calculate the number of conflicts by positioning the queen at rowi for all i = 0, …, n − 1
    • for all rows where the count of the conflicts is minimal, choose a random one to place the queen

Run min-conflicts yourself

Each step has two halves: pick a random conflicted queen (the numbers in her column are the conflicts she would have in each row), then move her to a row with the fewest conflicts. The arrays below are exactly the ones the algorithm keeps.

8
–
h = conflicts
0
moves
Arrays
Log
Test yourselfLab 03 quiz

18 auto-graded tasks, 100 points: CSP formulation, constraint graphs, backtracking, MRV and LCV, forward checking, min-conflicts and N-Queens.

Start the quiz →