An introduction to CSPs (Constraint Satisfaction Problems) in Prolog

01_Prolog_Intro.pl

/* Created by Guilhem Piat, 2022
View the interactive notebook version of this guide here:
https://swish.swi-prolog.org/p/intro_to_pl.swinb

        ##### INTRODUCTION TO PROLOG FOR CSPs #####

Prolog is a logic programming language that is typically meant to
solve logic problems, but can also easily be used as a CSP solver.

To use Prolog, you may use the online editor/console SWISH:
https://swish.swi-prolog.org/ or you may install a prolog interpreter like
SWIPL, available in the swi-prolog package on most Linux package managers.
For Windows and MacOS, see the downloads page:
https://www.swi-prolog.org/download/stable

Many code editors will default to Pascal highlighting with the .pl
extension, so make sure you're in Prolog mode if you're editing locally.
With SWIPL, start the interpreter with `swipl filename.pl` where
`filename.pl` is the program you want to load. You can reload after
having made changes with:
?- make.

For the puroses of this example, we will consider a CSP for which we have
to fill two length-3 lists with values in [1,3], and the i-th element of
both lists must differ for all index i.
L1 = [1,1,1] ; L2 = [2,2,3] is a correct answer for instance.

In Prolog, you do not write instructions or functions.
You write clauses, of which there are two types: Facts and Rules.
These clauses define predicates, which look like functions in other
languages but are a distinct concept (i.e. `predicate(Arg1, Arg2, ...).`).
Clauses end with a period (".").
Because you do not write instructions in Prolog, you do not write
algorithms. You write constraints -- what MUST be true -- and Prolog will
find solutions that satisfy your constraints.

The interpreter has a helpful `help` predicate. `?- help(==).` for intance
will bring up the help page of the `==` operator.
*/

%           # Facts & Variable Domain Definitions #

% Facts tell the program what is true.
% We typically define the domains of our variables with facts.
% Here, we define the is_valid_value predicate. It is true when given
% 1, 2, or 3 as argument.
is_valid_value(1).
is_valid_value(2).
is_valid_value(3).

% Here, we define a predicate which checks that two lists do not contain
% any values in common at any index. It is trivially true when given
% two empty lists as arguments.
no_common_index_value_pairs([], []).


%           # Rules & Constraint Definitions #

% Rules tell the program that a predicate is true, IF some conditions
% are verified.

/* Rules have the form:
    X :- Y, Z.
where `:-` means "is true if", and is followed by a list of goals.
`,` is the "conjunction" goal separator (there are other less used
goal separators, see `help(;).` for "disjunction").
In the previous example, X is true if goals Y and Z are both true.
See `help(,).` for more information.

Prolog cannot natively use indexed collections or loops. Looping can
only be done recursively. Therefore, we define a recursive rule such
that no_common_index_value_pairs is true if:
    - The first values of the lists are different, AND
    - the rest of the lists have no common index/value pairs

[H|T] is a pattern-matching formula. H (for "Head") is a variable
containing the first value of the list. T (for "Tail") is a list
containing the rest. Variables always start with a capital.*/

no_common_index_value_pairs([H1|T1], [H2|T2]):-
    H1 =\= H2, % The numeric inequality operator is not !=, but =\=
    no_common_index_value_pairs(T1, T2).

% Eventually, T1 and T2 will match to the empty list, and
% no_common_index_value_pairs(T1, T2) will match to
% no_common_index_value_pairs([], []) which we have defined to be true.

% This predicate checks if a list contains only values in [1, 3]. This
% is trivially true when it contains nothing.
contains_only_valid_values([]).
% Recursively check that every value is valid.
contains_only_valid_values([H|T]):-
    is_valid_value(H),
    contains_only_valid_values(T).

% Users do not assign values to variables in Prolog. We define
% constraints on the possible values a variable can have and let
% the solver figure it out.
% Here, we constrain the second argument to have a length equal to
% the first. `len(const, Var)` will assign to `Var` the length of
% `const`, and `len(Var, const)` will assign a list of length
%`const` to `Var`.
len([], 0).
% The underscore ("_") is used when we don't need to name a variable.
len([_|T], Length):-
    len(T, Length2),
    % `is` is the equality operator for numeric values on the left and
    % expressions on the right (which is different from `=:=`, the
    % equality operator for Numbers on left and right).
    Length is Length2 + 1.
% (Actually the `length` predicate already does this, but we're
% reimplementing it for the example).


%     # Defining Variables, Specifying the Domains & Constraints. #

% We define a predicate which solves the problem. It takes our
% variables as arguments and will search for values for these
% variables which satisfy all of the goals.
% As our goals, we specify the domain of all variables
% and the constraints, separated by conjunctions
% (*i.e.* AND, represented with a `,`).
solve(X1, X2):-
    % Domain definition
    len(X1, 3),
    len(X2, 3),
    contains_only_valid_values(X1),
    contains_only_valid_values(X2),
    % Constraints
    no_common_index_value_pairs(X1, X2).

/*
Typically, you'll want to optimize your `solve()` predicate by introducing
constraints as soon as the domain of the relevant variables is specified
as this prunes branches of the search tree early.

                        # Running the program #

To call the `solve()` predicate locally with a `.pl` file, load the
file in your Prolog Interpreter and enter:
?- solve(X, Y).
This is called a Query. (You can use different variable names than X and Y
if you want, it doesn't matter).
Prolog will give you a value for X and a value for Y such that `solve(X, Y)`
is true. In SWIPL, ENTER will end the program, and N will generate another
solution. SWISH has clickable buttons for the same thing.
*/

02_Prolog_CSP_template.pl

/*  Created by Guilhem Piat, 2022
    CSP definition template 
*/

% Defining the facts for our various domains.
    % value1 -- value5 are `atoms`. You can
    % think of them as an enum if it helps.
domain1(value1).
domain1(value2).
domain1(value3).

domain2(value3).
domain2(value4).
domain2(value5).

% Defining facts and rules for our constraints
%   Classic constraints
% It is trivially true that no matter what the
% first arg is, it cannot be in the empty list
not_in(_, []).
not_in(X, [Y|T]):-
    % remember to use the proper operators for
    % your domain.
    X \== Y,   % non-numeric inequality
    % X =\= Y, % numeric inequality
    not_in(X, T).

alldiff([_]).
alldiff([H|T]):-
    not_in(H, T),
    alldiff(T).

% Defining a predicate which solves the problem.
% 582 steps to find all solutions
solve(X1, X2, X3, X4):-
    % Define the domain of all variables
    domain1(X1),
    domain1(X2),
    domain2(X3),
    domain2(X4),

    % Enforce constraints
    alldiff([X1, X2, X3]),
    X1 == X4.    % non-numeric equality
    % X1 =:= X4. % numeric equality

% Optimizing the predicate, checking constraints ASAP
% 74 steps to find all solutions
better_solve(X1, X2, X3, X4):-
    domain1(X1),
    domain2(X4),
    X1 == X4,
    domain1(X2),
    domain2(X3),
    alldiff([X1, X2, X3]).

03_Crossword.pl

% Created by Guilhem Piat, 2022
% Load this program in a prolog interpreter like swipl or SWISH
% ( https://swish.swi-prolog.org/ ) and run the following query:
% ?- better_solve(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10)

% This program solves the following crossword problem:
%
%   %%1D%%%%7D%%%%%%%%    Where %% are black squares, __ are
%   %%__%%6R________0D    squares to be filled, and number/
%   %%__%%5D__%%8D%%__    letter combinations number a word
%   %%__3R________%%__    spot and indicate whether it goes
%   2R______%%9R______    down or to the right. The 0 is 10.
%   %%4R________%%%%%%
%
%  The words to place are: boa, lot, ont, paf, pot, pou,
%                          club, fuit, puis, pull.
%  (It's a French example problem)

% For our domains, we can give all variables the same domain
% and put a constraint on the length of the variables, or we
% can have the 3-letter-word domain and the 4-letter domain.
% We do the latter as it is more efficient in Prolog.

% Defining the facts for the domains of our length-3 words 
word3('BOA').
word3('LOT').
word3('ONT').
word3('PAF').
word3('POT').
word3('POU').

% Defining the facts for the domains of our length-4 words 
word4('CLUB').
word4('FUIT').
word4('PUIS').
word4('PULL').


% Makes sure arg1 (any type) is not in arg2 (list).
% This is trivially true for the empty list.
not_in(_, []).
% \== is the non-numeric inequality operator
not_in(X, [Y|T]):-
    X \== Y,
    not_in(X, T).

% Defining the rule to verify that all elements
% of a list are different.
alldiff([_]).
alldiff([H|T]):-
    not_in(H, T),
    alldiff(T).


% Defining the rule which solves the problem.
% Intuitive, non-optimized version. This version finds
% the solution in 4.7 million steps (0.7s), and proves
% it is unique in 141.7M additional steps (21s).
solve(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10) :-
    % Define the domain of all variables
    word4(X1),
    word3(X2),
    word4(X3),
    word4(X4),
    word3(X5),
    word4(X6),
    word3(X7),
    word3(X8),
    word3(X9),
    word3(X10),
    % Enforce all different
    alldiff([X1, X2, X3, X4, X5, X6, X7, X8, X9, X10]),
    
    % You can get a substring with
    % sub_string(Str, Start_index, Length,
    %            Length_remaining, SubStr).
    % see `help(sub_string).`
    % Get all shared characters
    sub_string(X1,  3, 1, _, X1_4), 
    sub_string(X2,  0, 1, _, X2_1), 
    sub_string(X2,  2, 1, _, X2_3), 
    sub_string(X3,  0, 1, _, X3_1), 
    sub_string(X3,  1, 1, _, X3_2),
    sub_string(X3,  3, 1, _, X3_4),
    sub_string(X4,  0, 1, _, X4_1),
    sub_string(X4,  3, 1, _, X4_4),
    sub_string(X5,  0, 1, _, X5_1),
    sub_string(X5,  1, 1, _, X5_2),
    sub_string(X5,  2, 1, _, X5_3),
    sub_string(X6,  0, 1, _, X6_1),
    sub_string(X7,  0, 1, _, X7_1),
    sub_string(X7,  2, 1, _, X7_3),
    sub_string(X8,  0, 1, _, X8_1),
    sub_string(X8,  1, 1, _, X8_2),
    sub_string(X8,  2, 1, _, X8_3),
    sub_string(X9,  0, 1, _, X9_1),
    sub_string(X9,  2, 1, _, X9_3),
    sub_string(X10, 2, 1, _, X10_3),

    % Check for equality of shared characters
    % == is the non-numeric equality operator
    X2_1 == X1_4,
    X5_1 == X3_1,
    X5_2 == X2_3,
    X5_3 == X4_1,
    X7_1 == X6_1,
    X7_3 == X3_2,
    X8_1 == X3_4,
    X8_3 == X4_4,
    X9_1 == X8_2,
    X9_3 == X10_3.


% Optimized version -- introduces equality constraints
% ASAP to cut off exploration of bad branches early.
% Finds the solution in 450 steps (< 1 ms), and proves
% it is unique in 370 additional steps.
better_solve(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10) :-
    word4(X1),
    sub_string(X1, 3, 1, _, X1_4),

    word3(X2),
    sub_string(X2, 0, 1, _, X2_1),
    X2_1 == X1_4,
    sub_string(X2, 2, 1, _, X2_3),

    word4(X3),
    sub_string(X3, 0, 1, _, X3_1),
    sub_string(X3, 1, 1, _, X3_2),
    sub_string(X3, 3, 1, _, X3_4),

    word4(X4),
    sub_string(X4, 0, 1, _, X4_1),
    sub_string(X4, 3, 1, _, X4_4),

    word3(X5),
    sub_string(X5, 0, 1, _, X5_1),
    X5_1 == X3_1,
    sub_string(X5, 1, 1, _, X5_2),
    X5_2 == X2_3,
    sub_string(X5, 2, 1, _, X5_3),
    X5_3 == X4_1,

    word4(X6),
    sub_string(X6, 0, 1, _, X6_1),

    word3(X7),
    sub_string(X7, 0, 1, _, X7_1),
    X7_1 == X6_1,
    sub_string(X7, 2, 1, _, X7_3),
    X7_3 == X3_2,

    word3(X8),
    sub_string(X8, 0, 1, _, X8_1),
    X8_1 == X3_4,
    sub_string(X8, 1, 1, _, X8_2),
    sub_string(X8, 2, 1, _, X8_3),
    X8_3 == X4_4,

    word3(X9),
    sub_string(X9, 0, 1, _, X9_1),
    X9_1 == X8_2,
    sub_string(X9, 2, 1, _, X9_3),

    word3(X10),
    sub_string(X10, 2, 1, _, X10_3),
    X9_3 == X10_3,

    alldiff([X1, X2, X3, X4, X5, X6, X7, X8, X9, X10]).

04_KenKen.pl

% Created by Guilhem Piat, 2022
% Load this program in a prolog interpreter like swipl or SWISH
% ( https://swish.swi-prolog.org/ ) and run the following query:
% ?- better_solve(A1, A2, A3, B1, B2, B3, C1, C2, C3)

% This program solves the following 3x3 KenKen problem:
%
%     1 2 3
%   A a a d    Where the a group must add up to 5,
%   B b a d    the b group must add up to 4, the c
%   C b c c    to 5, and the d to 4.
%
%  The words to place are: boa, lot, ont, paf, pot, pou,
%                          club, fuit, puis, pull.


% Defining the facts for the domains of our values.
% Only 1, 2, and 3 are possible values, and all our
% variables share the same domain.
domain(1).
domain(2).
domain(3).


% Makes sure arg1 (any) is not in arg2 (list).
% Trivially, "anything" is not in "nothing".
not_in(_, []).
% =\= is the numeric inequality operator
not_in(X, [H|T]):-
    X =\= H,
    not_in(X, T).

% Defining the rule to verify that all elements
% of a list are different.
% Trivially, there are no duplicates in a list
% of length 0 or 1.
alldiff([]).
alldiff([_]).
alldiff([H|T]):-
    not_in(H, T),
    alldiff(T).


% Defining the rule which solves the problem.
% Non-optimized version. 62k steps (13 ms) to solve.
solve(A1, A2, A3, B1, B2, B3, C1, C2, C3) :-
    % Define the domain of all variables
    domain(A1),
    domain(A2),
    domain(A3),
    domain(B1),
    domain(B2),
    domain(B3),
    domain(C1),
    domain(C2),
    domain(C3),
    % Enforce all different rows and columns
    alldiff([A1, A2, A3]), % Row A
    alldiff([B1, B2, B3]), % Row B
    alldiff([C1, C2, C3]), % Row C
    alldiff([A1, B1, C1]), % Col 1
    alldiff([A2, B2, C2]), % Col 2
    alldiff([A3, B3, C3]), % Col 3
    % Enforce additional constraints
    % =:= is the equality operator on numeric values
    A1 + A2 + B2 =:= 5,
    A3 + B3 =:= 4,
    C2 + C3 =:= 5,
    B1 + C1 =:= 4.

% Optimized version. 333 steps (<1ms) to solve.
better_solve(A1, A2, A3, B1, B2, B3, C1, C2, C3) :-
    define(A1),
    define(A2),
    define(A3),
    alldiff([A1, A2, A3]),
    define(B1),
    define(B2),
    A1 + A2 + B2 =:= 5,
    define(B3),
    alldiff([B1, B2, B3]),
    A3 + B3 =:= 4,
    define(C1),
    alldiff([A1, B1, C1]),
    B1 + C1 =:= 4,
    define(C2),
    alldiff([A2, B2, C2]),
    define(C3),
    alldiff([C1, C2, C3]),
    alldiff([A3, B3, C3]),
    C2 + C3 =:= 5.