我试图在序言中创建紧凑的代码以解决方程组。
例如,在这种情况下,假设必须是
A+B-C-D=4, A+B+C+D=14, A-B+C-D=2.
我正在尝试将其解决A,B,C和D的所有可能组合,但要满足所有3个方程。尽管它们只能是#的0-9,但是以某种方式显示了所有可能的解决方案/组合。
因此,在运行查询后,它将输出类似的内容
加密(A,B,C,D)
A = 8, B = 1, C = 0, D = 5.
^那将是一种解决方案。但我需要显示所有可能。
我对如何满足Prolog中的所有3种方法感到困惑。谢谢。
您可以通过从变量的域中取出一个元素并将其分配给它们,以便为每个变量分配不同的数字来解决它。这是一种蛮力方法。
takeout(X, [X|R], R).
takeout(X, [Y|Xs], [Y|Ys]):- takeout(X, Xs, Ys).
aas(X,L,L1):- takeout(X,L,L1).
crypto(A,B,C,D):-
L=[0,1,2,3,4,5,6,7,8,9],
aas(A,L,L1),aas(B,L1,L2),aas(C,L2,L3),aas(D,L3,_),
A+B-C-D=:=4,
A+B+C+D=:=14,
A-B+C-D=:=2,
nl.
aas(X,L,L1).
用于为变量分配值。takeout
函数用于取出一个元素并返回不包括取出的元素的列表。
输出
?- crypto(A,B,C,D).
A = 3,
B = 6,
C = 5,
D = 0
A = 5,
B = 4,
C = 3,
D = 2
A = 7,
B = 2,
C = 1,
D = 4
A = 8,
B = 1,
C = 0,
D = 5
此程序将打印出该方程A+B-C-D=4, A+B+C+D=14, A-B+C-D=2.
的所有可能解,希望它能回答您的问题。
作为注释中的joel76注释,请使用库clpfd(tutorial)
在这里,我将提供的不仅仅是答案,因为这个问题很简单,很多人都可以理解,而且很复杂,可以用来说明一些必要的概念,以便在Prolog中使用约束。我也打算将来再参考此答案。
与SWI-Prolog一起使用约束时,要做的第一件事就是引入存储在库中的谓词,这是通过以下指令完成的:
:- use_module(library(clpfd)).
现在是最简单的约束示例,一个常数。
constant(C) :-
C#= 4.
以及一个显示如何使用它的测试
:- begin_tests(simple_constraints).
test(1) :-
constant(C),
assertion( C == 4 ).
:- end_tests(simple_constraints).
从顶层使用make/0将编译代码并运行测试
?- make.
% c:/xyz compiled 0.00 sec, -8 clauses
% PL-Unit: simple_constraints . done
% test passed
true.
因此第一个测试成功运行。
下一条是无界线
% Unbounded line
unbounded_line(X,Y) :-
X #= Y.
但是如果按原样使用
?- unbounded_line(X,Y).
X = '$VAR'('Y'),
'$VAR'('Y')in inf..sup.
告诉我们,可能的答案是无限的。目前,我不知道如何将其放入测试中并检查无限可能的答案(link),但是如果测试要限制值,它将起作用。
test(2) :-
findall((X,Y),(between(-5,5,X),unbounded_line(X,Y)),Line),
assertion( Line == [(-5,-5),(-4,-4),(-3,-3),(-2,-2),(-1,-1),(0,0),(1,1),(2,2),(3,3),(4,4),(5,5)] ).
?- make.
% c:/xyz 0.00 sec, 2 clauses
% PL-Unit: simple_constraints .. done
% All 2 tests passed
true.
消除带有约束的无限可能答案的更好方法是添加更多约束。
% bounded line
bounded_line(X,Y) :-
X #>= -5, X #=< 5,
X #= Y.
和测试
test(3) :-
Goal = (bounded_square(X,Y),label([X,Y])),
findall((X,Y),Goal,Values),
assertion( Values == [(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)] ).
?- make.
% c:/xyz compiled 0.00 sec, 0 clauses
% PL-Unit: simple_constraints ... done
% All 3 tests passed
true.
[注意,测试使用了label/1。参见Understanding CLP(FD) Prolog code of N-queens problem
因此,如果您遇到的问题可能具有无限数量的解决方案,并将其交给约束求解器,则求解器将无法成功寻找确切答案,而只会返回关系,例如
three_variables_unbounded(A,B,C) :-
A + B + C #= 5.
?- three_variables_unbounded(A,B,C).
'$VAR'('A')+'$VAR'('B')+'$VAR'('C')#=5.
?- three_variables_unbounded(A,B,C),label([A,B,C]).
ERROR: Arguments are not sufficiently instantiated
ERROR: In:
ERROR: [16] throw(error(instantiation_error,_10256))
ERROR: [13] clpfd:'__aux_maplist/2_must_be_finite_fdvar+0'([_10290,_10296|...]) at c:/program files/swipl/library/clp/clpfd.pl:1745
ERROR: [12] clpfd:labeling([],[_10334,_10340|...]) at c:/program files/swipl/library/clp/clpfd.pl:1748
ERROR: [9] <user>
ERROR:
ERROR: Note: some frames are missing due to last-call optimization.
ERROR: Re-run your program in debug mode (:- debug.) to get more detail.
但是,如果添加了其他约束,例如
three_variables_bounded(A,B,C) :-
A + B + C #= 5,
A #>= -5, A #=< 5,
B #>= -5, B #=< 5,
C #>= -5, C #=< 5.
?- three_variables_bounded(A,B,C).
'$VAR'('A')in-5..5,
'$VAR'('A')+'$VAR'('B')+'$VAR'('C')#=5,
'$VAR'('B')in-5..5,
'$VAR'('C')in-5..5.
?- three_variables_bounded(A,B,C),label([A,B,C]).
A = -5,
B = C, C = 5 ;
A = -4,
B = 4,
C = 5 ;
A = -4,
B = 5,
C = 4 ;
A = -3,
B = 3,
C = 5
...
现在解决问题。
problem(A,B,C,D) :-
A + B - C - D #= 4,
A + B + C + D #= 14,
A - B + C - D #= 2,
A #>= -10, A #=< 10,
B #>= -10, B #=< 10,
C #>= -10, C #=< 10,
D #>= -10, D #=< 10.
和测试用例
test(3) :-
Goal = (problem(A,B,C,D),label([A,B,C,D])),
findall((A,B,C,D),Goal,Values),
assertion( Values ==
[
(-1,10,9,-4),
(0,9,8,-3),
(1,8,7,-2),
(2,7,6,-1),
(3,6,5,0),
(4,5,4,1),
(5,4,3,2),
(6,3,2,3),
(7,2,1,4),
(8,1,0,5),
(9,0,-1,6),
(10,-1,-2,7)
]
).
?- make.
% c:/xyz compiled 0.02 sec, 0 clauses
% PL-Unit: simple_constraints ... done
% All 3 tests passed
true.