鉴于您对 addUnique/2
谓词的描述,可以使用约束逻辑编程来实现解决方案。这远非初学者的东西,但无论如何我都会发布一个解释。
首先,查找什么是约束逻辑编程以及如何使用实现(例如,SWI-PL clpfd)可能是值得的。基本上,约束逻辑编程(特别是有限域求解器)将允许您对输入列表中的变量指定以下约束addUnique/2
:
- 输入列表中的变量如何绑定到某些数值(即从 0 到并包括指定值的整数)
- 输入列表上的不同变量如何不能同时绑定到相同的值(即!= 不同的地方)
- 输入列表中的变量之和加上任何数字必须加起来为指定值(即,变量可以在上面的 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
该整数上,总计时,totaled 4
,而:
?- addUnique([A,A,A,A],4).
A = 1.
...正如预期的那样。另外,您想尝试:
?- addUnique([A,B,C,D],4).
false.
同样,这里的结果是失败,因为所有变量、A
和都被断言为不同的,并且不能都绑定到。B
C
D
1
编辑附言。ony 也想试试:
?- addUnique([A,A,A,1],4).
A = 1.
对上面代码的简单修改可确保在调用断言域时仅使用变量ins
(而不是输入列表中的任何数字)。