Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 40 ยท Constraint Logic Programming

CLP(FD) Puzzles and Labeling Strategies

Solve classic puzzles with Prolog constraints. Model SEND+MORE and N-queens with library(clpfd), choose labeling options such as ff and bisect, and learn modeling tips for faster search.

Puzzles are where constraint programming shines. A cryptarithm, a queens board or a Sudoku grid is a handful of integer variables plus a few rules; a CLP(FD) program states those rules almost verbatim and lets propagation and search do the rest. This lesson models two classics, then looks at the labeling options that decide how fast the search is.

Prolog is not available on this site. The Prolog code is shown read-only (it is standard library(clpfd) code), and each puzzle also runs on the small Python stand-in solver from the previous lesson so you can watch the same model produce the same answers.

SEND + MORE = MONEY

Each letter is a different digit, the leading letters are not zero, and the sum must hold:

Text
    S E N D
  + M O R E
  ---------
  M O N E Y

The model has three parts: the variables and their domain, the all_different constraint, and one arithmetic equation:

PROLOG
:- use_module(library(clpfd)).

puzzle([S,E,N,D] + [M,O,R,E] = [M,O,N,E,Y]) :-
    Vars = [S,E,N,D,M,O,R,Y],
    Vars ins 0..9,
    all_different(Vars),
              S*1000 + E*100 + N*10 + D
            + M*1000 + O*100 + R*10 + E #=
    M*10000 + O*1000 + N*100 + E*10 + Y,
    M #\= 0,
    S #\= 0.
PROLOG
?- puzzle(P), term_variables(P, Vs), label(Vs).
P = [9, 5, 6, 7]+[1, 0, 8, 5]=[1, 0, 6, 5, 2].

Even before labeling, propagation on the single equation shows that M must be 1 (the sum of two four-digit numbers is below 20000). That is the point of constraints: most of the work happens before any guess is made.

The stand-in splits the sum into columns with carry variables, which is how humans solve it and gives its simpler constraints something to propagate.

Python SEND + MORE = MONEY (Python stand-in solver)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The search visits a few thousand nodes (the exact number depends on the solver) instead of the 1.8 million ways to assign eight different digits.

N-queens

Place N queens on an N by N board so that no two attack each other. Use one variable per column: Qs = [Q1,...,QN], where Qi is the row of the queen in column i. Two queens in columns i and j clash if they share a row or a diagonal, which means Qi #\= Qj and abs(Qi - Qj) #\= j - i.

PROLOG
n_queens(N, Qs) :-
    length(Qs, N),
    Qs ins 1..N,
    safe_queens(Qs).

safe_queens([]).
safe_queens([Q|Qs]) :-
    safe_queens(Qs, Q, 1),
    safe_queens(Qs).

safe_queens([], _, _).
safe_queens([Q|Qs], Q0, D0) :-
    Q0 #\= Q,
    abs(Q0 - Q) #\= D0,
    D1 #= D0 + 1,
    safe_queens(Qs, Q0, D1).
PROLOG
?- n_queens(8, Qs), labeling([ff], Qs).
Qs = [1, 5, 8, 6, 3, 7, 2, 4] .

safe_queens/3 compares one queen with every queen to its right, adding 1 to the column distance each step. The program has no search in it at all: n_queens/2 only posts constraints, and labeling/2 chooses the strategy.

Python N-queens, counting solutions (Python stand-in solver)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The known counts are 2 solutions for 4 queens, 10 for 5, 4 for 6, 40 for 7 and 92 for 8, which the stand-in reproduces.

Labeling strategies

labeling(Options, Vars) lets you choose how the search proceeds. The options fall into three groups.

Variable selection (which variable next):

Option Meaning
leftmost the first unlabeled variable (default)
ff the variable with the smallest domain ("first fail")
ffc smallest domain, ties broken by most constraints
min / max the variable with the smallest lower / largest upper bound

Value order: up (default) or down.

Branching: step (default, tries X = V then X #\= V), enum (all values), bisect (splits the domain in half).

Optimization: min(Expr) and max(Expr) find a solution that minimizes or maximizes an expression (see Global Constraints and Optimization).

ff is the best general-purpose choice: the variable with the fewest options is the most likely to fail, so failing early prunes the tree faster. On hard problems the gap between leftmost and ff can be the gap between a second and a day. bisect helps with huge domains, because it never enumerates values one by one.

PROLOG
?- X in 1..100, X #> 90, labeling([down], [X]).
X = 100 ;
X = 99 ;
X = 98 .

Combine options in a list: labeling([ff, down], Vars).

Modeling tips

  • Choose the viewpoint. In N-queens, one variable per column with the row as its value is much better than one variable per square.
  • Add redundant constraints. A constraint that is logically implied can still help propagation, for example sum(Vars, #=, Total) next to the individual constraints.
  • Break symmetry. If solutions come in mirror images, add a rule such as Q1 #=< Q2, so only one of each pair is explored.
  • Use all_distinct/1 instead of all_different/1 when the problem is tight. It propagates more strongly (at higher cost per step).
  • Test small first. A model that is slow for 8 queens will never solve 30.
  • Read the residual goals before labeling: if everything is already solved by propagation, you are done; if nothing is pruned, the model needs stronger constraints.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does ff do in labeling([ff], Vars)?

    First-fail: the variable with the fewest remaining values is the most likely to fail, so trying it first prunes early.
  2. 2. In the N-queens model, why is the constraint abs(Q0 - Q) #\= D0 needed?

    Queens at column distance D0 are on a diagonal when their rows differ by exactly D0.
  3. 3. Which step should come last in a CLP(FD) program?

    Constrain first so propagation prunes the search; then label.
  4. 4. What does bisect branching do?

    Bisect narrows large domains efficiently without enumerating every value.

Summary

  • A puzzle model is: variables with domains, constraints for the rules, then label or labeling/2.
  • SEND+MORE and N-queens each need only all_different, #= or #\= constraints.
  • Propagation does most of the work; labeling strategies (ff, ffc, down, bisect) control the rest.
  • Good modeling means the right viewpoint, redundant constraints and symmetry breaking.

Next: Global Constraints and Optimization