Tree-Search and Constraint Propagation

After the problem has been expressed using domain variables and constraints, we have to find values (or sometimes only sets of possible values) for these variables. This is achieved by the Tree-Search process associated to Constraint Propagation.

This process is performed as follows:

Level n:

  1. Choose a domain variable var which has not been instantiated yet. If there is no uninstantiated variable, then the problem is solved;
  2. Set a Choice Point, i.e. remember the state of all the domain variables at this step;
  3. Try to instantiate the domain variable var to a selected value val (which belong to its domain);
  4. Check the result of instantiation of variable:
    • If instantiation has failed (i.e. if Constraint Propagation has found an inconsistency), then return to the most recent Choice Point, and restore the state of all the domain variables at the step the Choice Point was set (this “return-and-restore” process is called Backtrack).
    • If instantiation has failed and all possible values for var have already been tried, then Backtrack to the Choice point of the level (n - 1). (If n = 1, then it means that the problem itself has no solution).
    • Otherwise perform the next level (n + 1).

In fact this basic Tree-Search algorithm itself is implemented in C using iZ-C in 15 lines of code (cf. Reference Manual, “Context” section).

In the Tree-Search process, Constraint Propagation occurs at step (3), when a value for a domain variable is tried. This Constraint Propagation mechanism is triggered by a domain variable var when its domain changes. Then a domain variable \(V_{i}\) linked to var through a constraint \(C_{i,j}\) will have its domain modified according to the new domain of var and the constraint \(C_{i,j}\)

As \(V_{i}\) itself may trigger Constraint Propagation again, this mechanism is recursive.

For example, let us consider two domain variables A and B, having their initial domain set to 1..8, and consider the constraint:

  • A: {1..8}
  • B: {1..8}
  • A = B + 2

After this constraint is posted:

  • A: {3..8}
  • B: {1..6}

Let us modify the domain of A:

  • A \(\neq\) 5

Then Constraint Propagation will give: B \(\neq\) 3

If we modify the domain of B:

  • B \(\le\) 3

Then Constraint Propagation will give: A \(\le\) 5

Using iZ-C, the code and output would be:

Code:

#include "iz.h"

int main(int argc, char **argv)
{
  CSint *A, *B;

  cs_init();

  A = cs_createNamedCSint(1, 8, "A");
  B = cs_createNamedCSint(1, 8, "B");

  cs_printf("%T\n%T\n", A, B);

  cs_Eq(A, cs_Add(B, CSINT(2)));
  cs_printf("\nAfter 'A = B + 2':\n%T\n%T\n", A, B);

  cs_NEQ(A, 5);
  cs_printf("\nAfter 'A != 5':\n%T\n%T\n", A, B);

  cs_LE(B, 3);
  cs_printf("\nAfter 'B <= 3':\n%T\n%T\n", A, B);

  cs_end();

  return 0;
}

output:

A: {1..8}
B: {1..8}

After 'A = B + 2':
A: {3..8}
B: {1..6}

After 'A != 5':
A: {3, 4, 6..8}
B: {1, 2, 4..6}

After 'B <= 3':
A: {3, 4}
B: {1, 2}

Actually, Constraint propagation is performed automatically with iZ-C, when we set constraints (cs_Add constraint in the example) or when some changes occurs in the domain of CSint variables.

In iZ-C, a pre-defined functions integrates the Tree-Search mechanism explained before. cs_search() is one of these functions takes a findFreeVar() function as an argument, which enable to have control on the order in which CSint variables are chosen (cf step (1) of the Tree-Search process).

To illustrate the cs_search() function, let us go back to the “Alphametic”.

Code:

void printSolution(CSint **allvars, int nbVars)
{
  cs_printf("  %D\n", L1);
  cs_printf("* %D\n", L2);
  cs_printf("-----\n");
  cs_printf("  %D\n", L3);
  cs_printf(" %D \n", L4);
  cs_printf("%D  \n", L5);
  cs_printf("-----\n");
  cs_printf("%D  \n", L6);
  cs_printStats();
}

int main(int argc, char **argv)
{
  cs_init();

  constraints();
  cs_search(Digit, NB_DIGITS, cs_findFreeVarNbElements);
  printSolution(Digit, NB_DIGITS);

  cs_end();

  return 0;
}

Output:

  179
* 224
-----
  716
 358
358
-----
40096

Nb Fails = 134
Nb Choice Points = 217
Heap Size = 1024

The printed solution is found within 134 Backtracks (number of fails) and 217 Choice Points.

The cs_findFreeVarNbElements() function, passed as an argument of cs_search() is a pre-defined iZ-C function that returns the non instantiated CSint variable which has the smallest domain, i.e. the lowest number of elements. This strategy is often a good one, but other strategies can be implemented by rewriting your own findFreeVar() function.

One may want to know if this solution is the only one. This new problem can be solved using the cs_findAll() function instead of cs_search().

Code:

int main(int argc, char **argv)
{
  cs_init();

  constraints();
  cs_findAll(Digit, NB_DIGITS, cs_findFreeVarNbElements, printSolution);
  cs_printStats();

  cs_end();

  return 0;
}

Output:

  179
* 224
-----
  716
 358
358
-----
40096

Nb Fails = 134
Nb Choice Points = 217
Heap Size = 1024

Nb Fails = 1669
Nb Choice Points = 2600
Heap Size = 2048

1669 backtracks are necessary to find that the “Alphametic” has only one solution. The fourth argument of cs_findAll() is a function that will be called each time a solution is found.

As we have seen with this small example, Constraint Solving is consists from three steps:

  1. Declare the domain variables
  2. Express the constraints on these variables;
  3. Find values for these variables compatible with the constraints.

iZ-C provides:

  • CSint variable for step 1.
  • Many pre-defined constraints for step 2. And also provides ways of defining new customized constraints (cf. Define a New Constraint using Demons)
  • Pre-defined Tree-Search functions for step 3. And also provides ways of defining new customized heuristics (cf. Reference Manual, “Heuristics and Generation Mechanisms”, “Context”).