1

我正在尝试打印n=4的n 分数问题的所有解决方案：

:- 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,[]).

当我运行查询时：

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

我得到以下异常： 

*** 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

我在想是否有办法在程序内部循环并每次打印一个解决方案，或者我不能这样做，因为问题有太多解决方案？

4

3 回答 3

2

正如已经指出的那样，您的代码失败是因为alldifferent(Digits)约束过于严格。数字必须允许出现 1 到 2 次。在中，您可以使用atleast/3、atmost/3、occurrences/3或gcc/2等约束来表达这一点。

稍微偏离主题：当您使用 ECLiPSe 的ic-solver（可以处理连续域）时，您实际上可以使用更接近原始规范的模型，而无需引入大量乘法：

:- 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).

除了主要的等式约束（使用$=而不是#=因为我们不想在这里要求完整性）之外，我使用了occurrences/3作为出现限制，并使用字典顺序约束作为消除对称性的更标准的方法。结果：

?- 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)

这个模型的另一个优点是它可以很容易地变成任意 N 的通用模型。

于 2019-02-21T09:46:36.123 回答
1

只是你的谓词失败了。如果你删除除alldifferent/1and之外的所有约束search/6（只是为了理解问题）并调用你?- fractions(Digits).getfalse因为不可能有一个包含 12 个元素的Digits = [A,B,C,D,E,F,G,H,I,J,K,L]列表Digits #:: 1..9（ic:alldifferent(Digits)12 个元素的 9 个选项：无法解决。如果您将域扩展到 12 ( Digits #:: 1..12)，您将得到一个解决方案：

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

然后您可以申请findall/3并查看其他解决方案...

于 2019-02-17T10:48:02.757 回答
1

许多实现提供global_cardinality了我在本例中使用的约束。下面我使用 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.

样品用途：

| ?- 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

使用收集所有解决方案也可以：

?- 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
于 2019-02-17T18:30:34.380 回答