如何在Prolog中为“8/ 10猫做倒计时”数字游戏求解器生成不同的解决方案？

Question

我编写了一个Prolog程序来查找任何“https://en.wikipedia.org/wiki/8_Out_of_10_Cats_Does_Countdown”数字序列的所有解决方案。我对结果很满意。然而，解决办法并不是独一无二的。我试过distincts()和reduced()从“解序列”库。他们没有提出独特的解决办法。

问题很简单。您有一个给定的列表，其中包括n1、n2、n3、n4、n5、n6和一个目标数(R)。使用n1、-、*、/从任意任意的only +到n6组合计算R。您不必使用所有数字，但只能使用每个数字一次。如果两个解决方案是相同的，则只能生成一个，而另一个必须丢弃。

有时，在不同的分配方式下，也会有相同的结果。例如：

(100+3)*6*75/50+25
(100+3)*75*6/50+25  

有没有人有任何建议来消除这种冗余？

每个解决方案都是一个嵌套运算符和整数。例如，+(2,*(4,-(10,5)))。该解决方案是一种不平衡二叉树，具有算术运算算子的根和兄弟节点，数字为叶节点。为了有唯一的解，没有两棵树是等价的。

代码：

:- use_module(library(lists)).
:- use_module(library(solution_sequences)).

solve(L,R,OP) :-
    findnsols(10,OP,solve_(L,R,OP),S),
    print_solutions(S).

solve_(L,R,OP) :-
    distinct(find_op(L,OP)),
    R =:= OP.

find_op(L,OP) :-
    select(N1,L,Ln),
    select(N2,Ln,[]),
    N1 > N2,
    member(OP,[+(N1,N2), -(N1,N2), *(N1,N2), /(N1,N2), N1, N2]).
find_op(L,OP) :-
    select(N,L,Ln),
    find_op(Ln,OP_),
    OP_ > N,
    member(OP,[+(OP_,N), -(OP_,N), *(OP_,N), /(OP_,N), OP_]).

print_solutions([]).
print_solutions([A|B]) :-
  format('~w~n',A),
  print_solutions(B).

测试：

solve([25,50,75,100,6,3],952,X)

结果

(100+3)*6*75/50+25 <- s1
((100+6)*3*75-50)/25 <- s2
(100+3)*75*6/50+25 <- s1
((100+6)*75*3-50)/25 <- s2
(100+3)*75/50*6+25 <- s1
true.

• 此代码使用来自选择/3的“名单”图书馆。

更新:使用DCG生成解决方案

下面是使用DCG生成解决方案的尝试。我能够生成一个比之前发布的代码更详尽的解决方案集。在某种程度上，使用DCG会产生更正确和优雅的代码。然而，要‘猜’出代码正在做什么要困难得多。

多余的解决办法问题仍然存在。

:- use_module(library(lists)).
:- use_module(library(solution_sequences)).

s(L) --> [L].

s(+(L,Ls)) --> [L],s(Ls).
s(*(L,Ls)) --> [L],s(Ls), {L =\= 1, Ls =\= 1, Ls =\= 0}.

s(-(L,Ls)) --> [L],s(Ls), {L =\= Ls, Ls =\= 0}.
s(/(L,Ls)) --> [L],s(Ls), {Ls =\= 1, Ls =\= 0}.

s(-(Ls,L)) --> [L],s(Ls), {L =\= Ls}.
s(/(Ls,L)) --> [L],s(Ls), {L =\= 1, Ls =\=0}.

solution_list([N,H|[]],S) :-
    phrase(s(S),[N,H]).

solution_list([N,H|T],S) :-
    phrase(s(S),[N,H|T]);
    solution_list([H|T],S).

solve(L,R,S) :-
    permutation(L,X),
    solution_list(X,S),
    R =:= S.

Answer 1

有没有人有任何建议来消除这种冗余？

我建议在每个节点(内部或叶)上定义排序权重。可以使用因减少子节点而产生的数字，但会出现领带。可以通过另外查看最顶层的操作来打破这些问题，例如，在*之前对+进行排序。实际上，人们希望有一个排序操作，对于这个排序操作，"tie“的意思是”完全相同的算术运算子树“。