Search code examples
prologeclipse-clpprolog-findall

Avoid findall overflow with n-fractions problem

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?

Solution

  • 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 , 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.