1. Having a finite set of variables with a finite set of possible values
2. Having a finite set of propagators which are monotonic on variables (that is, it either reduces the amount of possible values for a variable or does not (it never adds).
3. A space describing a full set of variables and propagators
4. A way of reducing the amount of values when all propagators have hit a fixpoint for some space.
5. A way of rewinding state when some variable runs out of possible values
And then it basically (BASICALLY) runs this loop:
while(!solved(space)) {
if(failed(space)) {
rewind(space);
}
while(!fixpoint(space)) {
for(p in propagators(space))
{ p(space);
}
}
make_choice(space);
}It's mainly used for solving NP-hard problems by being smart when attacking the full search tree.