Constraints in practice

This lesson collects five programs on constraints in Prolog, all using library(clpfd). Every one of them starts with

:- use_module(library(clpfd)).

and that line is the whole installation.

Arithmetic twice: is/2 and #=/2

File arithmetic.pl. The same relation, written the two ways: is evaluates (its right side must be known), #= relates (neither side needs to be known).

• double_is(3, Y) works, and double_is(X, 6) is an error: X is not instantiated.
• double_fd(X, 6) finds X = 3: the same definition runs backwards.
• double_fd(X, Y) has no solution yet: the answer is a residual constraint, X*2 #= Y, the relation itself, waiting for more information.

A factorial that runs in any direction

The factorial the CLP(FD) way: one definition, any direction. The example is the one in the library(clpfd) manual and in The Power of Prolog.

• n_factorial(5, F) computes 120;
• n_factorial(N, 120) finds N = 5, and asking for more solutions then answers false: the constraint bounds N, so the search terminates (F #= N * F1 bounds N backwards from 120);
• n_factorial(N, F) enumerates, on backtracking, one pair after another: 0-1, 1-1, 2-2, 3-6, 4-24, ...

SEND + MORE = MONEY

File send-more-money.pl. The cryptarithmetic puzzle: eight letters, eight distinct digits, one equation over them. The model is the one in the library(clpfd) manual. Note that this program does not label: the solving is left to the caller.

The first answer is not a solution but the residual constraints: propagation alone has already fixed S = 9, M = 1 and O = 0 (the second query checks exactly that), and cut the other five domains down to four values or fewer. Only with label(As) do we get 9567 + 1085 = 10652, and it is the only solution: collecting all of them with findall gives a single one.

N queens

File queens.pl. Qs is a list of N variables, Qs[i] being the row of the queen in column i. The model is the one in the library(clpfd) manual.

There are 4 solutions for the 6 × 6 board.

The labeling strategy is not a detail

Compare the two strategies on 20 queens, asking each for a first solution and looking at the inferences reported by time/1. The default label/1 takes the variables in order and tries values in order; labeling([ff], Qs) (first-fail) always picks the variable with the smallest remaining domain:

With ff a few hundred thousand inferences at most are needed; with plain label the search is so much longer that this notebook stops it after its step budget (12 million inferences) without an answer. In measurements on SWI-Prolog 10.0.2, 24 queens took 5.2 s with label/1 and 0.003 s with labeling([ff]), and ff still answers n = 100 in 0.07 s.

Sudoku with all_distinct/1

File sudoku.pl. 27 all_distinct/1 constraints (nine rows, nine columns, nine blocks) and nothing else. The model is the one in the library(clpfd) manual. Two puzzles are given: the first is solved by propagation alone, the second is not, and needs labeling.

• problem(1, Rows), sudoku(Rows): no labeling at all, and the grid comes back solved. all_distinct/1 propagates strongly enough that there is no search to do. (The label and portray_clause version just prints it.)
• problem(2, Rows), sudoku(Rows): this one propagation does not finish. The answer is residual constraints, and the grid is not ground, as the query negating ground(Rows) confirms. It needs labeling([ff]) on every row.

A stronger propagator is not always faster

all_different/1 is the weaker, cheaper cousin of all_distinct/1. Try both on the harder grid:

On the hard puzzle the cheaper all_different/1 can be the faster one (0.065 s against 0.018 s in one measurement on SWI-Prolog 10.0.2), while on the easy one all_distinct/1 costs nothing at all and all_different/1 leaves a search to do that costs seconds. The honest summary: a stronger propagator is not always faster. Re-measure rather than copy numbers forward: they depend on the system and its version.

Knapsack: optimisation, not just satisfaction

File knapsack.pl. A 0/1 knapsack. item(Name, Weight, Value) facts, one 0/1 variable per item (in the order item/3 gives them), scalar_product/4 for the totals, and labeling([max(V)], Take) for the optimisation.

• knapsack(200, T, W, V) alone is a residual constraint again: the model, not yet a solution.
• With labeling([max(V)], T) the solutions come out from best to worst value, so the first one is the optimum. Here it takes the map, the compass, the sandwich, the glucose, the banana and the note (weight 136, value 545). (once/1 keeps just that first one.)
• With capacity 100 the best choice changes: map, sandwich, glucose and note, for a value of 450.