Constraint satisfaction

Question 1

What is backtracking search?

Answer 1

• Algorithm for solving constraint satisfaction problems

-

Question 2

Improving backtracking search efficency

Answer 2

• Least constraining value: choose the variable (value) that rules out the fewest values in the remaining variables.
• Minimum remaining values: choose variable with the fewest legal moves
• Degree heuristic: choose the variable most constraints on remaining values
• ## Forward checking: For each unassigned variable keep track of its legal values. If we make a decision that leaves a variable no legal values stop search and backup

Question 3

Structured CSPS

Answer 3

• Divide problems into smaller problems