How to create arithmetic and disequality constraints in Prolog

Question

I'm brand new to Prolog, and I'm interested in converting the following word problem into (SWI) Prolog:

There are 4 children: Abe, Dan, Mary, and Sue. Their ages, in no particular order, are 3, 5, 6, and 8. Abe is older than Dan. Sue is younger than Mary. Sue's age is Dan's age plus 3 years. Mary is older than Abe.

So far I've come up with

child(X) :-
    member(X, [3,5,6,8]).

solution(Abe, Dan, Mary, Sue) :-
    child(Abe),
    child(Dan),
    child(Mary),
    child(Sue),
    Abe > Dan,
    Sue < Mary,
    Sue == Dan+3,
    Mary > Abe,
    Abe \== Dan,
    Abe \== Mary,
    Abe \== Sue,
    Dan \== Mary,
    Dan \== Sue,
    Mary \== Sue.

But running the query

?- solution(Abe, Dan, Mary, Sue)

I just get false. As a side question, will Prolog perform brute force search for solutions, or is there some machinery which can solve this (sort of) problem in better than O(n!) ?

The result I want is Abe = 5, Dan = 3, Mary = 9, Sue = 6.

Wearable

You must write Sue =:= Dan+3 instead of Sue == Dan+3 – Obey

Sue == Dan+3 will not perform the arithmetic operation. You need Sue =:= Dan+3 for that. – Dobla

OK, so where are the big problem instances? I'd love to see them! – Hortensehortensia

Answer 1

Arithmetic constraints over integers, such as the constraints in this puzzle, are best expressed with your Prolog system's CLP(FD) constraints.

For example, in SICStus Prolog, YAP or SWI:

:- use_module(library(clpfd)).

ages(As) :-
        As = [Abe,Dan,Mary,Sue],    % There are 4 children: Abe, Dan, Mary, Sue
        As ins 3\/5\/6\/8,          % Their ages are 3, 5, 6 and 8
        all_different(As),
        Abe #> Dan,                 % Abe is older than Dan
        Sue #< Mary,                % Sue is younger than Mary
        Sue #= Dan + 3,             % Sue's age is Dan's age plus 3 years
        Mary #> Abe.                % Mary is older than Abe

Sample query and its result:

?- ages([Abe,Dan,Mary,Sue]).
Abe = 5,
Dan = 3,
Mary = 8,
Sue = 6.

We see from this answer that the puzzle has a unique solution.

Note that no search whatsoever was necessary to obtain this answer! The constraint solver has deduced the unique solution by a powerful implicit mechanism called constraint propagation, which is the key advantage of CLP systems over brute force search. Constraint propagation is successfully used in this example to prune all but one remaining branch of the search tree.

Denaedenarius

Way to go. s(X)! Some small issues with your answer: (1) For SICStus clpfd (ins)/2 needs to be defined. (2) The domain 3\/5\/6\/8 should better be written as {3}\/{5}\/{6}\/{8} which works with both SWI and SICStus. (3) Both issues are gone when using library(clpz) with SICStus --- available at github.com/triska/clpz. How about introducing a module named clpz to SWI, too? – Hortensehortensia

After looking up clpfd and subsequently discovering swi-prolog.org/man/clpqr.html I have a couple small questions maybe you can answer. 1) Is CLP(Q,R) a superset of CLP(FD) - can CLP(Q,R) solve this problem efficiently as well, or is working strictly with integers a useful constraint? 2) I found that CLP(FD) is for working with integers, but what do the letters FD actually stand for? – Wearable

Would using CLP(Q,R) for this (more accurately, similar but much larger) problem introduce a performance penalty though? – Wearable

@Brent. fd = "finite domain". Yes and no, clpqr can work with both integers and non-integers (rational and floating-point numbers) but is heavily geared towards systems of linear equations and linear inequations solvable with Gaussian elimination and the Simplex "linear programming" method. MIP (mixed integer linear programming) is offered, too, but the weapon of choice for all-integer combinatorial problems is clpfd, not clpqr. – Hortensehortensia

@Brent. Good question! Supply some problem instances and we can try it out. I assume that clpfd generally wins (by a large margin) with problems like this. – Hortensehortensia

@Brent. Also, clpfd gives a wide array of methods / solvers / internal representations etc... so even if it doesn't win right from the start, we could find a very suitable method/parameters with moderate to low effort. – Hortensehortensia

@Brent: I agree with everything repeat has said. Moreover, I think that each of your questions deserves to be asked on its own. You will get several good answers for them. – Denaedenarius

Answer 2

The answer by @WillemVanOnsem—generate and test with low-level arithmetics—is old-school:

• Legacy Prolog code puts the burden of getting all low-level procedural details right on you.

• Debugging / optimizing legacy code often boils down to some variant of program tracing.

In comparison, @mat's code wins on generality / versatility / robustness, declarativity, conciseness, efficiency, and more! How come? Luck? Genius? Divine intervention? Likely a bit of each, but the main reason is this: @mat uses superior tools. @mat uses clpfd.

Good news! clpfd is generally available. Use it & reap the benefits:

• Note how close @mat's Prolog code and the original specs are!

• The code preserves logical-purity. This has important consequences:

  • High-level debugging methods (which harness useful algebraic properties of pure Prolog code) can be used!

  • Low-level debugging is also possible, but explore high-level methods first!

Hortensehortensia

I really like the use of the permutation function, because it closely resembles my internal model of the problem. Would you give a brief explanation of what's going on in that maplist call? Is #< the first parameter to maplist/3? What is it? – Wearable

@Brent. I'll edit my answer in a little while, but let me start here in this comment: maplist/3 is a widely available meta-predicate, that is a predicate that takes another predicate as an argument. (#<)/2 misses exactly 2 arguments. maplist/3 with #< as the first argument, [A1,A2,A3] as the second argument, and [B1,B2,B3] as the third argument has same meaning as A1#<B1, A2#<B2, A3#<B3. (It works like that with two lists having the same length. In the query in my SO-answer we use it with two lists of 5 items each.) – Hortensehortensia

That makes sense. Thanks for the clarification. – Wearable

As I see it, constraint propagation is the key advantage to entirely avoid the O(n!) call of permutation/2. This was even explicitly asked for in the original question. Now it seems to be of less concern, and maybe it has some educational value to contrast the brute-force approach (using permutation/2) with constraint propagation, but I would overall put much more emphasis on the latter than on the former. – Denaedenarius

@mat. Thank you for helping me backtrack to roads I'd actually take myself! – Hortensehortensia

To posterity: all comments preceding this one refer to details of a hack-ish code sketch that I later retracted. – Hortensehortensia

Answer 3

Since the values are grounded after the child calls, you can use the is operator:

child(X) :-
    member(X, [3,5,6,8]).
solution(Abe, Dan, Mary, Sue) :-
    child(Abe),
    child(Dan),
    child(Mary),
    child(Sue),
    Abe > Dan,
    Sue < Mary,
    Sue is Dan+3,
    Mary > Abe,
    Abe =\= Dan,
    Abe =\= Mary,
    Abe =\= Sue,
    Dan =\= Mary,
    Dan =\= Sue,
    Mary =\= Sue.

You can further improve performance by interleaving generate and test, instead of first generating and then test:

child(X) :-
    member(X, [3,5,6,8]).
solution(Abe, Dan, Mary, Sue) :-
    child(Abe),
    child(Dan),
    Abe > Dan,
    Abe =\= Dan,
    child(Mary),
    Mary > Abe,
    Abe =\= Mary,
    Dan =\= Mary,
    Sue is Dan+3,
    Sue < Mary,
    child(Sue),
    Abe =\= Sue,
    Dan =\= Sue,
    Mary =\= Sue.

Then you can also eliminate some not equal predicates (=\=) because these are implied by the less than (<) or greater than (>) predicates; or by the is predicate:

child(X) :-
    member(X, [3,5,6,8]).
solution(Abe, Dan, Mary, Sue) :-
    child(Abe),
    child(Dan),
    Abe > Dan,
    child(Mary),
    Mary > Abe,
    Dan =\= Mary,
    Sue is Dan+3,
    Sue < Mary,
    child(Sue),
    Abe =\= Sue.

Nevertheless using a constraint logic programming (CLP) tool is probably the best way to solve this problem.

Bebel

Why not place Sue is Dan+3 before child(Sue)? And then, maybe, move both more to the top; I know... it never ends:) – Hortensehortensia