4.11 Constraint satisfaction problems

Work through these

• State a problem as variables, domains and constraints

  Writing the problem as a set of variables, the values each may take, and the rules relating them. This is the whole trick: once a state has visible parts, the solver can reason about it instead of treating it as a lump.

• Draw the constraint graph, and read unary, binary and higher-order constraints off it

  The picture where every variable is a node and every rule an edge between the variables it relates. Reading the graph tells you which choices interact, and that is what every ordering heuristic later depends on.

• Run backtracking search, and see why it beats generic depth-first search here

  Assigning one variable at a time and undoing the last assignment when a rule is violated. It succeeds because assignments commute, so the search never explores the same set of choices in a different order.

• Apply forward checking and arc consistency to prune before you search

  Removing values from other variables the moment an assignment rules them out, and repeating until nothing more can be removed. Most of the speed of a constraint solver comes from this, not from the search itself.

• Order variables and values: most constrained variable, most constraining variable, least constraining value

  Three ordering rules that decide which variable to fill next and which value to try first. Together they turn a solver that stalls on a hard problem into one that finishes, without changing the answer.

• Solve map colouring, n-queens and a timetable as constraint problems

  Three problems that look unrelated and turn out to be the same shape once written as variables and rules. Working all three is what makes the formulation stick.