Tree-CSP-Solver.md

TREE-CSP-SOLVER

AIMA3e

function TREE-CSP-SOLVER(csp) returns a solution, or failure
 inputs: csp, a CSP with components X, D, C

 n ← number of variables in X
 assignment ← an empty assignment
 root ← any variable in X
 X ← TOPOLOGICALSORT(X, root)
 for j = n down to 2 do
  MAKE-ARC-CONSISTENT(PARENT(X_j), X_j)
  if it cannot be made consistent then return failure
 for i 1 to n do
  assignment[X_i] ← any consistent value from D_i
  if there is no consistent value then return failure
 return assignment

---

Figure ?? The TREE-CSP-SOLVER algorithm for solving tree-structured CSPs. If the CSP has a solution, we will find it in linear time; if not, we will detect a contradiction.