- Up - | Next >> |

Propagation is saturation under deterministic inference. The basic inference rules as well the inference rules corresponding to the non-basic constraints are applied repeatedly until a fix point is reached, i.e. until the partial information about the assignment can no longer be improved. At this point, there are 3 possibilities:

was derived, i.e. we have arrived at a contradiction and this branch of the search must be abandoned since it cannot lead to a solution.

All variables are determined: the assignment is fully known and satisfies the constraints. This is a solution.

At least one variable is not yet determined. At this point we need search and non-deterministically apply a distribution rule.

- Up - | Next >> |

Denys Duchier

Version 1.2.0 (20010221)