Constraint Satisfaction Problems (e.g. sudoku)

• Single player, Deterministic, Fully observable, Discrete (finite) state space
• Path is not important! Actions doesn’t have cost
• All paths have the same depth

CSP Attributes

• State is defined by vars $X_i \in$ domain $D$
• Goal set: Constraints specifying passing value combinations for some vars
  • Implicit Constraint: A rule verifying if the constraint is satisfied
  • Explicit Constraint: A set of all possible values for $X_1, X_2, \dots$ satisfying the constraint
• (e.g. sudoku: var $X_{i,j}$ is a block, domain $D=\{1,\dots,9\}$)

Constraint Graph: Each var is a node, each constraint is an edge

• Unary Constraint: Constraint on a single variable (Dumb, you can just reduce the domain)
• Binary Constraint: Each constraint relate 2 vars

Backtracking Search

Naive Search ❌

• State: Partial assignment of vars
• Successor function: Assign and unassign vars
• Goal test: All vars are assigned, no constraints violated
• BFS: Very bad, the solution is always at the bottom of the tree where all vars are assigned
• DFS: Better but still bad, it fills everything first without checking the constraints are satisfied

Backtracking Search: Check constraints as you go, prune if constraint violated

• It cannot detect indirect logical failures in the future (where an assignment cause no value can be assigned to one or more empty vars)