Modeling with iZ-C
Domain Variable (CSint type)
The Constraint Solving approach to solve a problem is based on two principles:
Modeling the problem as a set of variables, and a set of constraints over these variables. A solution for the problem will be found when the values (or possible values) for the variables will respect all the constraints.
Solving the problem is based on what is called the Constraint Propagation mechanism. It means that during the Tree-Search, constraints are used actively as soon as possible to detect inconsistencies, and to eliminate variable values which cannot occur in the solution of the problem.
At the step of modeling the problem, we don’t need to care about how it will be solved. Our purpose at this level is just to express declaratively the problem, in terms of variables (the unknowns of the problem) and constraints over these variables (i.e. the restrictions over the possible values of the variables that must be satisfied).
With iZ-C, variables are called CSint variables, or integer domain variables. The set of possible values of a CSint variable is called its domain.
Examples of CSint and its domain: (cs_init and cs_end are omitted in these examples)
Code:
{
CSint *vint = cs_createNamedCSint(0, 10, "vint"); // Create a CSint variable having domain
cs_printf("%T\n", vint); // between 0 and 10 and print it.
}
Output:
vint: {0..10}
Code:
{
int domain[9] = {-2, 0, 1, 2, 3, 5, 6, 7, 10}; // Create a CSint variable having
CSint *vint = cs_createCSintFromDomain(domain, 9); // domain defined by array domain[9]
cs_printf("%T\n", vint); // and print it.
}
Output:
{-2, 0..3, 5..7, 10}
Alphametic
Let us take the “Alphametic” as an example, where the problem consists in the following cryptogram where each letterhas to be replaced by a number between 0 and 9 such as the multiplication is correct, and where each integer between 0 and 9 is used exactly twice.
A B C (L1)
* D E F (L2)
----------
G H I (L3)
J K L (L4)
M N O (L5)
-----------
P Q R S T (L6)
The solution of our problem will be the values of the CSint variables A, B, …, T.
The constraints between these variables are:
a). L6 = L1 * L2
b). L3 = F * L1
c). L4 = E * L1
d). L5 = D * L1
e). L6 = 100 * L5 + 10 * L4 + L3
f). A \(\neq\) 0, D \(\neq\) 0, G \(\neq\) 0, J \(\neq\) 0, M \(\neq\) 0, P \(\neq\) 0
g). Each integer between 0 and 9 must appear exactly twice in {A, B, …, T}.
Where L1, L2, …, L6 are defined as:
d1). L1 = 100 * A + 10 * B + C;
d2). L2 = 100 * D + 10 * E + F;
d3). L3 = 100 * G + 10 * H + I;
d4). L4 = 100 * J + 10 * K + L;
d5). L5 = 100 * M + 10 * N + O;
d6). L6 = 10000 * P + 1000 * Q + 100 * R + 10 * S + T.
Let us express this problem using iZ-C:
#include "iz.h"
#define NB_DIGITS 20
CSint **Digit; // Digit is an array of 20 CSint variables
CSint *L1, *L2, *L3, *L4, *L5, *L6;
// Digit[a] = A, Digit[b] = B, ..., Digit[t] = T
enum {a = 0, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t};
void constraints()
{
int val;
Digit = cs_createCSintArray(NB_DIGITS, 0, 9);
L1 = cs_VScalProd(3, Digit[a], Digit[b], Digit[c], 100, 10, 1); // (d1)
L2 = cs_VScalProd(3, Digit[d], Digit[e], Digit[f], 100, 10, 1); // (d2)
L3 = cs_VScalProd(3, Digit[g], Digit[h], Digit[i], 100, 10, 1); // (d2)
L4 = cs_VScalProd(3, Digit[j], Digit[k], Digit[l], 100, 10, 1); // (d3)
L5 = cs_VScalProd(3, Digit[m], Digit[n], Digit[o], 100, 10, 1); // (d4)
L6 = cs_VScalProd(5, Digit[p], Digit[q], Digit[r], Digit[s], Digit[t], // (d5)
10000, 1000, 100, 10, 1);
cs_Eq(L6, cs_Mul(L1, L2)); // (a)
cs_Eq(L3, cs_Mul(Digit[f], L1)); // (b)
cs_Eq(L4, cs_Mul(Digit[e], L1)); // (c)
cs_Eq(L5, cs_Mul(Digit[d], L1)); // (d)
cs_Eq(L6, cs_VScalProd(3, L5, L4, L3, 100, 10, 1)); //(e)
// (f)
cs_NEQ(Digit[a], 0);
cs_NEQ(Digit[d], 0);
cs_NEQ(Digit[g], 0);
cs_NEQ(Digit[j], 0);
cs_NEQ(Digit[m], 0);
cs_NEQ(Digit[p], 0);
// (g)
for (val = 0; val <= 9 ; val++) {
cs_OccurConstraints(CSINT(2), val, Digit, NB_DIGITS);
}
}