backjumping and forward checking (slides5)

Question 1

Backjumping

Answer 1

used to remove thrashing

1. identify the source of the conflict (impossible to assign a value)
2. jump to past variables in conflict
   - irrelevant assignments are skipped and undone

Where to jump when at dead-end p:

• select the constraints containing just the currently assigned variable and pst variables
• select the closest variable participating in the selected constraints

Question 2

forward checking

Answer 2

• keep track of remaining legal values for unassigned variables
• terminate search when any variable has no legal values

Question 3

constraint propagation

Answer 3

forward checking with repeatedly enforced local constraints.

allows for early detection of failures with forward checking