Featured16

Visual Computing7

Computer Vision4

Natural Language Processing6

Design / Web16

Data Mining2

Deep Learning5

Systems8

Machine Learning2

Functional Programming1

Artificial Intelligence7

Data Structures and Algorithms5

Information Theory1

Writing2

Data Insights1

Artificial Intelligence/Constraint Satisfaction
54 / 67

10/2021Artificial Intelligence

Constraint Satisfaction

Backtracking search with forward checking and the MRV, degree, and least-constraining-value heuristics, applied to map coloring and circuit layout.

╌╌╌╌

A constraint satisfaction problem (CSP) is a triple: variables, a domain of values for each, and constraints that forbid certain combinations. Map coloring and circuit-board layout both take this form — assign a color to each region, or a position to each component, so that no constraint is violated. This project solves them with backtracking search, sharpened by forward checking and variable- and value-ordering heuristics.

A map-coloring CSP as a constraint graph. Each node is a region; an edge joins two regions that share a border and so may not take the same color. Tasmania (T) borders nothing, so its color is unconstrained.

Backtracking assigns variables one at a time, checks the constraints touching each new assignment, and on a dead end undoes the last assignment to try the next value. It walks the same tree as naive generate-and-test but prunes a branch the moment it turns inconsistent, rather than only at a complete assignment.

Algorithm:Backtrack(A,csp)\textsc{Backtrack}(A, csp) — depth-first search over partial assignments
  1. 1
    input: a partial assignment AA, a CSP
  2. 2
    if AA is complete then return AA
  3. 3
    X←X \gets unassigned variable chosen by MRV, then degree
  4. 4
    for each value vv of XX, ordered by LCV, do
  5. 5
    if vv is consistent with AA then
  6. 6
    add X=vX = v to AA; propagate by forward checking
  7. 7
    if no neighbor's domain is empty then
  8. 8
    r←Backtrack(A,csp)r \gets \textsc{Backtrack}(A, csp)
  9. 9
    if r≠failurer \ne \textsf{failure} then return rr
  10. 10
    remove X=vX = v from AA; restore pruned domains
  11. 11
    return failure

Three ordering heuristics decide which branch to try first:

  • Minimum remaining values (MRV) picks the variable with the fewest legal values left, failing fast on the tightest variable.
  • Degree breaks MRV ties by choosing the variable tied to the most constraints with still-unassigned neighbors.
  • Least-constraining value (LCV) orders the chosen variable's values by how few options they remove from neighbors, keeping the rest of the search open.

Forward checking propagates each assignment into neighbors' domains, deleting values it has just made illegal; when a domain empties, the current path is abandoned before it is extended further. This catches conflicts one step earlier than testing constraints only at assignment time.

A slice of the backtracking tree with the heuristics at work. MRV expands the tightest variable next; LCV tries the value that keeps the most options open first, and that branch runs on toward a solution. The other value assigns Q=b, and forward checking empties SA's domain on the spot — the whole subtree is pruned without ever being searched.

References

  1. Project repository
  2. Reference notes: Constraint Satisfaction Problems
  3. Reference notes: CSP Search and Structure
  4. Reference notes: Constraint Search: N-Queens & Sudoku

╌╌ END ╌╌