Plans on (classical) backtracking techniques for constraint solving.
More...
Go to the source code of this file.
Detailed Description
Plans on (classical) backtracking techniques for constraint solving.
 Todo:
 constraint_backtracking

Likely the constraintrelated backtracking should go into its own module?

Also output the corresponding splitting trees; perhaps they contain the enforced assignments.

Given such splitting trees, again one can represent all solutions, and/or count all solutions.

The simple code for "constraint_backtracking_counting" shows the big problem of the notion of "propagators": Only total solutions are recognised! The generalised SAT approach should overcome this.
 Todo:
 Heuristics

For the purpose of comparisons implement also the 3 other heuristics from [Beek, 2006, Backtracking Search Algorithms] (which use only the the domain sizes from the lookahead).

Brown and Purdom: Minimise the remaining domain size + the minimum over all other variables of the sum of their domain sizes in the branches.

Geelen: Minimise for a variable the sum over its values of the product of the remaining domain sizes over all other variables. (This is closest to our, but it replaces the taurule by the sum, which should be a bad approximation.)

Freeman: As Geelen, but instead of taking the product again the sum is chosen.
To me (OK) this all looks like guessing around, where the true rule is the taurule of variable_heuristics_tau.

The heuristics should be optimal, given that only the domain sizes for the potential branches are available ?!
 Todo:
 Further propagators
Definition in file ConstraintSatisfaction.hpp.