Solving a logic riddle in Prolog

Question

I'm in the "early phase" of learning prolog and came across a logic riddle that seams easy to implement:

Link to the riddle | Link to solution

---

We are looking for the 10-digit number which satisfies the following conditions:

• All digits from 0-9 occur exactly once.
• The first 2 digits are divisible by 2.
• The first 3 digits are divisible by 3.

...

• The first 10 digits are divisible by 10.

---

I think I would first need to implement the rules to the .pl file right? The rules from the solution are:

• An integer can be divided by 1 without remainder.
• An integer is divisible by 2 without remainder, if the last digit is straight.
• An integer can be divided by 3 without a remainder if its transverse sum is divisible by 3.
• An integer can be divided by 4 without a remainder if the last two digits are divisible by 4.
• An integer is divisible by 5 if the last digit is divisible by 5.
• An integer is divisible by 6 without a remainder if its transverse sum is divisible by 3 and the last digit by 2.
• An integer is divisible by 8 without a remainder if the last three digits are divisible by 8.
• An integer is divisible by 9 without a remainder if its transverse sum is divisible by 9.
• An integer is divisible by 10 without a remainder if the last digit is a 0.

---

I read multiple introductions to rules in prolog but still dont get how do it. Can anyone help? Would be great :)

Answer 1

Since you have tagged this with clpfd, I would like to augment the existing answer with additional information about constraints.

Importantly, constraints let you often avoid the generation of all combinations by pruning the search space for you.

We can start by relating a list of digits to the integer described by these digits:

digits_integer(Ds0, I) :-
        reverse(Ds0, Ds),
        Ds0 ins 0..9,
        foldl(pow, Ds, 0-0, I-_).

pow(D, I0-P0, I-P) :-
        I #= I0 + D*10^P0,
        P #= P0 + 1.

Here are two example queries:

?- digits_integer([1,2,3], I).
I = 123.

?- digits_integer(Ds, 302).
Ds = [3, 0, 2] .

Next, let us describe that a prefix of length N of the list Ls is divisible by N:

n_divisible(Ls, N) :-
        length(Prefix, N),
        append(Prefix, _, Ls),
        digits_integer(Prefix, I),
        I mod N #= 0.

The whole solution can thus be described as:

solution(Ds) :-
        length(Ds, 10),
        Ds ins 0..9,
        all_distinct(Ds),
        E in 2..10,
        findall(E, indomain(E), Es),
        maplist(n_divisible(Ds), Es).

Sample query:

?- solution(Ds), label(Ds).
Ds = [3, 8, 1, 6, 5, 4, 7, 2, 9, 0] ;
false.

Let us briefly compare the performance of the two solutions:

?- time((puzzle(Vs),false)).
% 142,709,119 inferences, 14.865 CPU in 14.867 seconds

vs.:

?- time((solution(Ds),label(Ds),false)).
% 19,384,173 inferences, 2.166 CPU in 2.166 seconds

Thus, the constraint-based approach is several times faster in this concrete case. This is mostly due to the power of constraint propagation, which the solver performs automatically.

Answer 2

Here's a slightly different approach with CLP(FD). First let's consider a predicate, that describes a relation between a list, its first n elements and the number those n elements yield. This version is somewhat similar but less general than @mat's digits_integer/2.

:- use_module(library(clpfd)).

digits_firstn_number_(_D,0,Num,Num).
digits_firstn_number_([D|Ds],X1,Num,Acc0) :-
   X1 #> 0,
   X0 #= X1-1,
   Acc1 #= Acc0*10+D,
   digits_firstn_number_(Ds,X0,Num,Acc1).

The calling predicate num/1 consists of a goal num_/2, that describes the actual relation and a second goal label/1 that is labeling the list of digits which is the second argument of num_/2. As a minor difference to @mat's version num/1 has the actual number rather than the list of digits as an argument:

num(Num) :-
   num_(Num,Digits),     % <- actual relation
   label(Digits).        % <- labeling the digits

The actual relation, num_/2 differs insofar, as the divisibility rules are, wherever possible, expressed as constraints on the respective digits (as suggested in the solution you linked) rather than on the corresponding numbers:

num_(Num,Digits) :-
   Digits=[A,B,C,D,E,F,G,H,I,J],
   Digits ins 0..9,
   all_distinct(Digits),                     % divisibility for:
   0 #= B mod 2,                             % <- first 2 digits
   0 #= (A+B+C) mod 3,                       % <- first 3 digits
   digits_firstn_number_([C,D],2,Num4,0),    % <- first 4 digits
   0 #= Num4 mod 4,                          % <- first 4 digits
   0 #= (E) mod 5,                           % <- first 5 digits
   0 #= (A+B+C+D+E+F) mod 3,                 % <- first 6 digits
   0 #= F mod 2,                             % <- first 6 digits
   digits_firstn_number_(Digits,7,Num7,0),   % <- first 7 digits
   0 #= Num7 mod 7,                          % <- first 7 digits
   digits_firstn_number_([F,G,H],3,Num8,0),  % <- first 8 digits
   0 #= Num8 mod 8,                          % <- first 8 digits
   0 #= (A+B+C+D+E+F+G+H+I) mod 9,           % <- first 9 digits
   J #= 0,                                   % <- all 10 digits
   digits_firstn_number_(Digits,10,Num,0).   % <- the actual number

The downside of this approach (besides more code) is, that it is exceedingly tailored towards this specific puzzle while @mat's version can be more easily extended to search for numbers with a different amount of digits with similar constraints (first n digits divisible by n). On the upside this approach is faster (compared with SWI-Prolog (Multi-threaded, 64 bits, Version 6.6.4)):

?- time((num(Num),false)).
% 2,544,064 inferences, 0.486 CPU in 0.486 seconds (100% CPU, 5235403 Lips)
false.

?- time((solution(Ds),label(Ds),false)).
% 19,289,281 inferences, 3.323 CPU in 3.324 seconds (100% CPU, 5805472 Lips)
false.

And of course, num/1 yields the same solution:

?- num(Num).
Num = 3816547290 ;
false.

Answer 3

The basic approach to solving this kind of problem in Prolog is to generate all possibilities, and then filter them. In this case we need a list of the ten digits with no repetitions, and each prefix of length N should be evenly divisible by N.

puzzle([A,B,C,D,E,F,G,H,I,J]) :-
  select(A,[0,1,2,3,4,5,6,7,8,9],List1),
  select(B,List1,List2), select(C,List2,List3), select(D,List3,List4),
  select(E,List4,List5), select(F,List5,List6), select(G,List6,List7),
  select(H,List7,List8), select(I,List8,List9), List9 = [J],
  divisible([A,B],2),
  divisible([A,B,C],3),
  divisible([A,B,C,D],4),
  divisible([A,B,C,D,E],5),
  divisible([A,B,C,D,E,F],6),
  divisible([A,B,C,D,E,F,G],7),
  divisible([A,B,C,D,E,F,G,H],8),
  divisible([A,B,C,D,E,F,G,H,I],9),
  divisible([A,B,C,D,E,F,G,H,I,J],10).

Even divisibility can be easily implemented:

divisible(Is,D) :-
  combine(Is,N),
  R is N rem D, R == 0.

But then we also need a bunch of technicalities to convert between integers, characters, and atoms.

:- use_module(library(lists)).

combine(Is,N) :-
  maplist(conv,Is,As), concat_list(As,A),
  atom_chars(A,Cs), number_chars(N,Cs).

conv(I,A) :-
  number_chars(I,[C]), atom_chars(A,[C]).

concat_list([A1,A2|As],Atom) :-
  atom_concat(A1,A2,A3),
  concat_list([A3|As],Atom).
concat_list([A],A).

This produces the result indicated in your link:

| ?- puzzle(X).
X = [3,8,1,6,5,4,7,2,9,0] ? ;
no
| ?- 

Addition: if you want to make it faster, rather than just buying a bigger computer like everybody else, you can interleave the generation & test parts of the code:

puzzle2([A,B,C,D,E,F,G,H,I,J]) :-
  select(A,[0,1,2,3,4,5,6,7,8,9],List1),
  select(B,List1,List2), divisible([A,B],2),
  select(C,List2,List3), divisible([A,B,C],3),
  select(D,List3,List4), divisible([A,B,C,D],4),
  select(E,List4,List5), divisible([A,B,C,D,E],5),
  select(F,List5,List6), divisible([A,B,C,D,E,F],6),
  select(G,List6,List7), divisible([A,B,C,D,E,F,G],7),
  select(H,List7,List8), divisible([A,B,C,D,E,F,G,H],8),
  select(I,List8,List9), divisible([A,B,C,D,E,F,G,H,I],9),
  List9 = [J], divisible([A,B,C,D,E,F,G,H,I,J],10).

Using SWI Prolog, I get the following timings:

?- time((puzzle(_),false)).
32m% 142,709,118 inferences, 76.333 CPU in 76.650 seconds (100% CPU, 1869553 Lips)

?- time((puzzle2(_),false)).
32m% 157,172 inferences, 0.142 CPU in 0.144 seconds (98% CPU, 1108945 Lips)

?- time((num(_),false)).
32m% 2,802,204 inferences, 1.008 CPU in 1.028 seconds (98% CPU, 2779208 Lips)

which would seem to suggest that the puzzle2 version is several times faster than the num version given below.