AI CSP

Constraint Satisfaction Problem (CSP)

A search problem where states are assignments to variables that must satisfy constraints.

What search is for

Planning focuses on paths; identification focuses on assignments.

CSP problem type

CSPs are identification problems, not path-finding problems.

CSP world assumptions

Single agent, deterministic actions, fully observed, discrete state space.

Standard search state

An arbitrary data structure with no internal structure.

CSP state representation

A set of variables with values from domains.

CSP goal test

A set of constraints that must all be satisfied.

Why CSPs are special

They allow powerful general-purpose algorithms.

CSP variables

X₁, X₂, … each representing a decision.

CSP domain

The set of allowed values for a variable.

CSP constraints

Rules restricting combinations of variable assignments.

CSP solution

A complete assignment satisfying all constraints.

Map coloring CSP variables

Regions on the map.

Map coloring CSP domains

Colors.

Map coloring CSP constraints

Adjacent regions must have different colors.

N-Queens CSP goal

Place queens so none attack each other.

N-Queens formulation 1

Variables = columns, domain = rows.

N-Queens formulation 2

Variables = queens, domain = board positions.

Binary CSP

A CSP where each constraint involves at most two variables.

Constraint graph

Graph where nodes are variables and edges are constraints.

Purpose of constraint graph

Exploit structure to speed up search.

Independent subproblems

Disconnected components in the constraint graph.

Cryptarithmetic CSP

Letters are variables, digits are domains, arithmetic rules are constraints.

Sudoku CSP variables

Each square on the board.

Sudoku CSP domains

{1,2,…,9}

Sudoku CSP constraints

AllDiff constraints on rows, columns, and regions.

Unary constraint

A constraint on a single variable.

Binary constraint

A constraint involving two variables.

Higher-order constraint

A constraint involving three or more variables.

Soft constraints

Preferences rather than strict requirements.

Real-world CSP examples

Scheduling, timetabling, assignments, circuit layout, medicine.

Standard CSP search state

Partial assignment of variables.

CSP initial state

Empty assignment {}.

CSP successor function

Assign a value to an unassigned variable.

CSP goal test

Assignment is complete and consistent.

Why BFS is bad for CSPs

All solutions are at the deepest level.

Why DFS is better for CSPs

Finds complete assignments earlier.

Backtracking search

DFS with constraint checking and variable ordering.

Backtracking idea 1

Assign one variable at a time.

Backtracking idea 2

Check constraints incrementally.

Incremental goal test

Check constraints after each assignment.

Backtracking effectiveness

Can solve N-Queens up to about n ≈ 25.

Choice points in backtracking

Order of variables and order of values.

Improving CSP search

Ordering, filtering, and exploiting structure.

Filtering idea

Remove illegal values early from domains.

Forward checking

Remove values that conflict with a new assignment.

Forward checking limitation

Does not detect all future conflicts.

Constraint propagation

Reason from constraint to constraint.

Arc consistency definition

For every value of X, there exists a legal value of Y.

Arc consistency direction

Delete values from the tail of the arc.

Arc consistency benefit

Detects failure earlier than forward checking.

Arc consistency drawback

High runtime cost.

Arc consistency runtime

O(n²d³), can be improved to O(n²d²).

Closed-world limitation

Arc consistency cannot detect all failures.

MRV heuristic

Choose variable with minimum remaining values.

MRV intuition

Fail fast by choosing most constrained variable.

Least constraining value heuristic

Choose value that rules out the fewest options.

Why least constraining value

Keeps future choices flexible.

Combining heuristics

MRV + LCV + propagation gives huge speedups.

Problem structure

Exploit independence and graph structure.

Independent subproblems

Solve separately for massive speedups.

Tree-structured CSP

A CSP whose constraint graph has no cycles.

Tree-structured CSP complexity

O(nd²)

General CSP complexity

O(dⁿ)

Tree-structured CSP algorithm

Backward pass + forward assignment.

Backward pass purpose

Make arcs consistent from leaves to root.

Forward assignment purpose

Assign values without backtracking.

Why tree CSPs don’t backtrack

Consistency guarantees legal assignments.

Why cycles break tree CSPs

Multiple parents may conflict.

Cutset conditioning

Instantiate variables to make the graph a tree.

Cutset size c

Runtime O(dᶜ (n−c)d²)

Tree decomposition

Create mega-variables forming a tree.

Mega-variable purpose

Encode overlapping subproblems.

Agreement constraint

Mega-variables must agree on shared variables.

CSP summary

CSPs use backtracking + ordering + filtering + structure.