Constraint Satisfaction Problem.md

title	date	lastmod
Constraint Satisfaction Problem	2022-11-08	2022-11-21

Constraint Satisfaction Problem

There are a set of constraints which specify the allowable combinations of values

Forward checking: Pre-emptively removes inconsistent values from the domains of neighbouring variables. Prevents unnecessary expansion if constraints have already been violated. This is uninformed and can be improve with heuristics:

Constraint Propagation

Propagate the implications of constraints from assigning 1 variable to the other variables.

Useful to optimize the order of variable assignments. This has the effect of making inconsistent assignments to fail earlier in the search, which enables more efficient pruning. This means that it may lead to more dead ends than:

Useful to optimize the order of value assignments. This prevents deadlocks and reduces backtracking by choosing the values which are most likely to work.

Example Problems

Cryptarithmetic Puzzle