Prolog 初学者：如何为谓词中的每个变量设置唯一值

Question

我有一个序言谓词：

Add( [A|B] , Answer ) :-
    ...
    ~ Add everything in the list to come up with answer
    ...

我现在想实现 AddUnique ，当我给它两次变量时，它将为列表中的所有内容返回唯一值除了。

---

以下是逻辑上等效的内容：

?- AddUnique([A, B, C], 10). 等效于： ?- Add([A, B, C], 10 ), A != B, B != C, A != C.

并且：

?- AddUnique([A, B, B], 10). 相当于： <代码>?- Add([A, B, B], 10), A != B.

另外：

?- AddUnique([A, B, B], 10). 不相当于： ?- Add([A, B, B], 10), A != B, B!=B.

---

如果 ?- AddUnique([A,B,C,D], 4). 被赋予它应该返回 false，因为它不能带有加到四的唯一正整数。

如果给出 ?- AddUnique([A,A,A,A], 4). ，则应返回 A=1。

---

问题：如何在谓词内移动 A != B, B != C, A != C. 逻辑，而不执行类似 A ! = A ？

Answer 1

Khm...你应该明白 doStuff(A,B,C,D) 和 doStuff(A,A,B,B) 的意思。首先是将 A .. D 值与适当的值统一起来，从而使 doStuff/4 可以达到目标。第二个等于 A=B, C=D, doStuff(A,B,C,D) 和 doStuff(A,B,C,D), A=B, C =D （但最后一个变体可能会导致回溯）。所以我希望您明白 unique/1 不应该在 doStuff/4 内部完成，因为它是外部限制。所以你应该使用 doStuff(A,B,C,D), unique([A,B,C,D]) 和 doStuff(A,A,B,B), unique ([A,B])。

我想知道你怎么读A is not B...
无论如何，您可以将 unique/1 定义为

not_unique([H|T]):- member(H, T) ; not_unique(T).
unique(L):- not(not_unique(L)).

Answer 2

根据您对 addUnique/2 谓词的描述，可以使用约束逻辑编程来实现解决方案。这与初学者的东西相去甚远，但无论如何我都会发布一个解释。

首先，可能值得查找约束逻辑编程是什么，以及如何使用实现（例如，SWI-PL clpfd)。基本上，约束逻辑编程（特别是有限域求解器）将允许您对输入列表上的变量指定以下约束：addUnique/2：

1. 输入列表上的变量如何绑定到某些数值（即从 0 到指定值的整数）
2. 输入列表中的不同变量如何不能同时绑定到同一值（即，不同时为 !=）
3. 输入列表中的变量之和如何加上任何数字相加必须达到指定值（即上述 1 中变量可以取的最大值）。

总之，这些规范将允许底层约束求解器自动确定在给定上述约束的情况下变量可以同时采用哪些允许值，从而为您提供解决方案（可能有多个、一个或没有）。

下面是在 SWI-PROLOG（clpfd 求解器）中使用上述约束求解器的解决方案：

:- use_module(library(clpfd)).  % import and use the constraint solver library

addUnique([A|As], Val) :-
    unique_vars([A|As], UVs),  % determine all unique variables
    UVs ins 0..Val,            % (1) domain of all unique variables is 0 to Val
    pairwise_inequ(UVs),       % (2) all unique variables are pairwise !=
    construct_sum_constr(As, Val, A, Program),  % (3) construct the sum constraint
    Program,              % assert the sum constraint
    label(UVs).           % label domains to enumerate a solution (backtracks)

% predicate to return a list of unique vars, if present
unique_vars([], []).
unique_vars([V|Vs], [V|Uniq]) :-
    var(V),
    \+ var_memberchk(V, Vs), !,
    unique_vars(Vs, Uniq).
unique_vars([_|Vs], Uniq) :-
    unique_vars(Vs, Uniq).

% predicate to test if a variable appears in a list (possibly including variables)
var_memberchk(V0, [V1|_]) :- 
    V0 == V1, !.
var_memberchk(V0, [_|V1s]) :- 
    var_memberchk(V0, V1s).

% create constraints that assert each in the input list != to each other
pairwise_inequ([]).
pairwise_inequ([V|Vs]) :-
    map_inequ(Vs, V),
    pairwise_inequ(Vs).

% predicate to pairwise assert inequality between all list members
map_inequ([], _).
map_inequ([V1|V1s], V0) :-
    V0 #\= V1,   % the inequality constraint
    map_inequ(V1s, V0).

% predicate to construct a summation constraint, whereby all variables in the 
% input list are constructed into a sum with +/2 and finally equated to a value
construct_sum_constr([], Val, Sum, (Sum #= Val)).
construct_sum_constr([V|Vs], Val, Sum, Program) :-
    construct_sum_constr(Vs, Val, (V + Sum), Program).

例如，运行此代码会给出：

?- addUnique([A,B,B], 6).
A = 0,
B = 3 ;
A = 4,
B = 1 ;
A = 6,
B = 0.

; 枚举变量之间允许的绑定的下一个解决方案。请注意，A 和 B 永远不会根据需要采用相同的值，但输入列表中的所有出现的总和将始终为 6。另一个查询：

 ?- addUnique([A,A,A],4).
false.

这里的结果是失败的，因为找不到单个整数可以绑定到 A，当求和时，总计为 4，而：

 ?- addUnique([A,A,A,A],4).
A = 1.

...如预期的那样。另外，您想尝试：

?- addUnique([A,B,C,D],4).
false.

同样，这里的结果是失败，因为所有变量 A、B、C 和 D< /code> 均被断言为不同，并且不能全部绑定到 1。

编辑 ps。 ony 也想尝试：

?- addUnique([A,A,A,1],4).
A = 1.

对上面的代码进行简单修改，确保在调用 ins 断言域时仅使用变量（而不是输入列表中的任何数字）。

Answer 3

这是我想出的解决方案。它只会将输入分配为小于 10 的数字，但效果很好！

addUnique( A, Answer ) :- 
    used(A,[0,1,2,3,4,5,6,7,8,9],_),
    add(A,Answer).

add( [A|B] , Answer ) :-
    ~ Add everything in the list to come up with answer ~.


% ================================
% Ensures that all variables are unique.  
% ================================

% Base case: Assigned variables unique values
used([], Nin, Nin).

% Have already assigned a value to this variable
used([A|B], Nin, Nout) :-
        integer(A),
        helper(B,Nin,Nout).

% Have not assigned a value to this variable yet
% Assign it and remove it from the list.  
used( [A|B] , Nin, Nout) :-
        member(A,Nin),
        delete(Nin,A,Temp),
        helper(B,Temp,Nout).