我编写了一个 Prolog 程序来查找任何“十分之八的猫会倒计时”数字序列的所有解决方案。我对结果很满意。然而，解决方案并不是唯一的。我尝试从“解决方案序列”库distincts()中获取。他们没有提出独特的解决方案。reduced()
问题\xc2\xa0很简单。您有一个给定的六个数字列表 [n1,n2,n3,n4,n5,n6] 和一个目标数字 (R)。仅使用 \xc2\xa0+,-,*,/ 从 n1 到 n6 的任意 \xc2\xa0 组合计算 R。您不必使用所有号码，但每个号码只能使用一次。如果两个解相同，则只能生成一个，而丢弃另一个。\xc2\xa0
\n\n有时，不同的\xc2\xa0排列会产生等效的\xc2\xa0结果。例如：
\n\n(100+3)*6*75/50+25\n(100+3)*75*6/50+25\xc2\xa0\xc2\xa0\n有没有人有任何建议来消除这种冗余？
\n\n每个解决方案都是嵌套的运算符和整数。例如+(2,*(4,-(10,5)))。该解决方案是一个不平衡二叉树，根节点和同级节点使用算术运算符，叶节点使用数字。为了获得唯一的解决方案，任何两棵树都不应该是等价的。
代码：
\n\n:- use_module(library(lists)).\n:- use_module(library(solution_sequences)).\n\nsolve(L,R,OP) :-\n findnsols(10,OP,solve_(L,R,OP),S),\n print_solutions(S).\n\nsolve_(L,R,OP) :-\n distinct(find_op(L,OP)),\n R =:= OP.\n\nfind_op(L,OP) :-\n select(N1,L,Ln),\n select(N2,Ln,[]),\n N1 > N2,\n member(OP,[+(N1,N2), -(N1,N2), *(N1,N2), /(N1,N2), N1, N2]).\nfind_op(L,OP) :-\n select(N,L,Ln),\n find_op(Ln,OP_),\n OP_ > N,\n member(OP,[+(OP_,N), -(OP_,N), *(OP_,N), /(OP_,N), OP_]).\n\nprint_solutions([]).\nprint_solutions([A|B]) :-\n format(\'~w~n\',A),\n print_solutions(B).\n测试：
\n\nsolve([25,50,75,100,6,3],952,X)\n结果
\n\n(100+3)*6*75/50+25 <- s1\n((100+6)*3*75-50)/25 <- s2\n(100+3)*75*6/50+25 <- s1\n((100+6)*75*3-50)/25 <- s2\n(100+3)*75/50*6+25 <- s1\ntrue.\n更新：使用 DCG 生成解决方案
\n\n以下是使用 DCG 生成解决方案的尝试。\xc2\xa0 我能够生成比之前发布的代码更详尽的解决方案集。在某种程度上，使用 DCG 可以生成更正确、更优雅的代码。然而，\xc2\xa0 要“猜测”代码在做什么要困难得多。
\n\n冗余解决方案的问题仍然存在。
\n\n:- use_module(library(lists)).\n:- use_module(library(solution_sequences)).\n\ns(L) --> [L].\n\ns(+(L,Ls)) --> [L],s(Ls).\ns(*(L,Ls)) --> [L],s(Ls), {L =\\= 1, Ls =\\= 1, Ls =\\= 0}.\n\ns(-(L,Ls)) --> [L],s(Ls), {L =\\= Ls, Ls =\\= 0}.\ns(/(L,Ls)) --> [L],s(Ls), {Ls =\\= 1, Ls =\\= 0}.\n\ns(-(Ls,L)) --> [L],s(Ls), {L =\\= Ls}.\ns(/(Ls,L)) --> [L],s(Ls), {L =\\= 1, Ls =\\=0}.\n\nsolution_list([N,H|[]],S) :-\n phrase(s(S),[N,H]).\n\nsolution_list([N,H|T],S) :-\n phrase(s(S),[N,H|T]);\n solution_list([H|T],S).\n\nsolve(L,R,S) :-\n permutation(L,X),\n solution_list(X,S),\n R =:= S.\n有没有人有任何建议来消除这种冗余？
我建议在每个节点（内部或叶子）上定义排序权重。可以使用减少子节点得到的数字，尽管会出现平局。这些可以通过另外查看最顶层的操作来打破，例如*在之前进行排序。+实际上，人们希望有一种排序操作，其中“tie”意味着“算术运算的完全相同的子树”。