PrologEZ
Advanced · Lesson 36 of 43

Constraints: CLP(FD)

Arithmetic that runs backwards, and puzzles that solve themselves.

Plain Prolog arithmetic has a limitation you met earlier: is/2 only works left-to-right with everything known. Constraint Logic Programming over Finite Domains, library(clpfd), gives you arithmetic relations.

Load the library and the operators with # become available:

:- use_module(library(clpfd)).
?- X #= 3 + 4
?- 7 #= X + 4
?- 7 #= 3 + Y

The same equation, three directions. Constraints can also be partial: the solver narrows each variable's domain and reports what's left:

?- X #> 3, X #< 8
?- X in 1..10, X mod 3 #= 0

To actually enumerate values, ask for labelling:

?- X #> 3, X #< 8, label([X])
?- [X, Y] ins 1..3, X #< Y, label([X, Y])

The pattern for every CLP(FD) program is:

  1. declare domains (ins, in);
  2. post constraints (#=, #\=, #<, all_different/1, …);
  3. label the variables to search.

SEND + MORE = MONEY

The classic cryptarithm: each letter is a distinct digit, and the sum must work out.

    S E N D
  + M O R E
  ---------
  M O N E Y
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,
    label(Vars).
?- puzzle(P)

Declarative, short, and instant, generate-and-test would try 10⁸ combinations.

N-queens, constrained

Compare with the previous lesson. Declare the board, post "no two attack each other", and label with the first-fail strategy ff:

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).
?- once((n_queens(8, Qs), labeling([ff], Qs)))
?- once((n_queens(20, Qs), labeling([ff], Qs)))

Twenty queens, solved in a blink. The constraints prune impossible rows before any guessing.

Exercise: Two numbers

Two whole numbers between 0 and 10 add up to 10, and their difference is 4. Write solve(X, Y) with CLP(FD) (the library is already imported) to find them.