Avoid findall overflow with n-fractions problem

Question

I am trying to print all solutions of the n-fractions problem for n=4:

:- lib(ic).

fractions(Digits) :-
   Digits = [A,B,C,D,E,F,G,H,I,J,K,L],

   Digits #:: 1..9,

   ic:alldifferent(Digits),

   X #= 10*B+C,
   Y #= 10*E+F,
   Z #= 10*H+I,
   V #= 10*K+L,

   A*Y*Z*V + D*X*Z*V + G*X*Y*V + J*X*Y*Z #= X*Y*Z*V,

   A*Y #=< D*X,
   D*Z #=< G*Y,
   G*V #=< J*Z,

   search(Digits,0,input_order,indomain,complete,[]).

When I run the query:

?- findall(Digits,fractions(Digits),List).

I get the following exception:

*** Overflow of the local/control stack!
You can use the "-l kBytes" (LOCALSIZE) option to have a larger stack.
Peak sizes were: local stack 105728 kbytes, control stack 25344 kbytes

I am thinking if there is a way to loop inside the program and print one solution each time, or I can't do that because the problem has too many solutions?

Answer 1

As has been pointed out, your code fails because the alldifferent(Digits) constraint is too restrictive. The digits must be allowed to occur between 1 and 2 times. In eclipse-clp, you can use constraints such as atleast/3, atmost/3, occurrences/3 or gcc/2 to express this.

Slightly off-topic: as you are using ECLiPSe's ic-solver (which can handle continuous domains), you can actually use a model much closer to the original specification, without introducing lots of multiplications:

:- lib(ic).
:- lib(ic_global).

fractions4(Digits) :-

    Digits = [A,B,C,D,E,F,G,H,I,J,K,L],
    Digits #:: 1..9,

    A/(10*B+C) + D/(10*E+F) + G/(10*H+I) + J/(10*K+L) $= 1,

    ( for(I,1,9), param(Digits) do
        occurrences(I, Digits, NOcc), NOcc #:: 1..2
    ),

    lex_le([A,B,C], [D,E,F]),       % lex-ordering to eliminate symmetry
    lex_le([D,E,F], [G,H,I]),
    lex_le([G,H,I], [J,K,L]),

    labeling(Digits).

Apart from the main equality constraint (using $= instead of #= because we don't want to require integrality here), I've used occurrences/3 for the occurrence restrictions, and lexicographic ordering constraints as a more standard way of eliminating symmetry. Result:

?- findall(Ds, fractions4(Ds), Dss), length(Dss, NSol).
Dss = [[1, 2, 4, 3, 5, 6, 8, 1, 4, 9, 2, 7], [1, 2, 6, 5, 3, 9, 7, 1, 4, 8, 2, 4], [1, 2, 6, 5, 3, 9, 7, 8, 4, 9, 1, 2], [1, 2, 6, 7, 3, 9, 8, 1, 3, 9, 5, 4], [1, 2, 6, 8, 7, 8, 9, 1, 3, 9, 5, 4], [1, 3, 4, 5, 4, 6, 8, 1, 7, 9, 2, 3], [1, 3, 4, 7, 5, 6, 8, 1, 7, 9, 2, 4], [1, 3, 4, 8, 1, 7, 8, 5, 2, 9, 2, ...], [1, 3, 5, 6, 2, 8, 7, 1, 4, 9, ...], [1, 3, 6, 5, 2, 4, 7, 1, 8, ...], [1, 3, 6, 5, 3, 6, 7, 8, ...], [1, 3, 6, 5, 4, 5, 8, ...], [1, 3, 6, 5, 6, 3, ...], [1, 3, 6, 6, 5, ...], [1, 3, 6, 7, ...], [1, 3, 9, ...], [1, 3, ...], [1, ...], [...], ...]
NSol = 1384
Yes (82.66s cpu)

An added advantage of this model is that it can be quite easily turned into a generic model for arbitrary N.

Answer 2

Simply your predicate fails. If you remove all the constraints except alldifferent/1 and search/6 (just to understand the problem) and call ?- fractions(Digits). you get false because it's impossible to have a list with 12 elements (Digits = [A,B,C,D,E,F,G,H,I,J,K,L]) with domain for each element Digits #:: 1..9 and constraint those elements to be all different (ic:alldifferent(Digits)). 9 options for 12 elements: unsolvable. If you expand the domain up to 12 (Digits #:: 1..12), you get a solution:

?- fractions(Digits).
Digits = [2, 3, 4, 9, 7, 10, 12, 8, 5, 11, 1, 6]
Yes (94.00s cpu, solution 1, maybe more)

Then you can apply findall/3 and see other solutions...

Answer 3

Many clpfd implementations offer global_cardinality constraints which I use in this example. In the following I use SICStus Prolog 4.5.0:

:- use_module(library(clpfd)).

fractions(Digits) :-
   Digits = [A,B,C,D,E,F,G,H,I,J,K,L],
   domain(Digits, 1, 9),
   global_cardinality(Digits, [1-N1,2-N2,3-N3,4-N4,5-N5,6-N6,7-N7,8-N8,9-N9]),
   domain([N1,N2,N3,N4,N5,N6,N7,N8,N9], 1, 2),
   X #= 10*B+C,
   Y #= 10*E+F,
   Z #= 10*H+I,
   V #= 10*K+L,
   Z*V #= ZV,
   X*Y #= XY,
   A*Y*ZV + D*X*ZV + G*XY*V + J*XY*Z #= XY*ZV,
   X #=< Y, X #= Y #=> A #=< D,                   % break some symmetries
   Y #=< Z, Y #= Z #=> D #=< G,
   Z #=< V, Z #= V #=> G #=< J.

Sample use:

| ?- n_fractions(4,Zs), labeling([enum],Zs).
Zs = [2,1,2,9,1,8,7,3,5,6,4,5] ? ;
Zs = [2,1,3,7,1,8,9,2,6,5,4,5] ? ;
Zs = [2,1,3,7,1,8,9,2,6,6,5,4] ? ;
...
no

Using prolog-findall for collecting all solutions works out all right, too:

?- findall(Zs,(n _fractions(4,Zs), labeling([enum],Zs)), Zss),
   length(Zss, N_sols).
Zss = [[2,1,2,9,1,8,7,3,5|...],
       [2,1,3,7,1,8,9,2,6|...],
       [2,1,3,7,1,8,9,2|...],
       [2,1,3,8,1,5,7|...],
       [2,1,3,8,1,6|...],
       [2,1,3,9,1|...],
       [2,1,3,9|...],
       [2,1,4|...],
       [2,1|...],
       [...|...]|...],
N_sols = 1384 ? ;
no