Prolog -动物拼图，需要强制每个原子只使用一次

Question

我看过一些关于SO讨论这个难题的帖子，但他们似乎旨在快速执行，我真的不明白发生了什么。我试图保持它非常简单，并希望写一些声明性和人类可读的东西。

我已经走了大部分的路，但我需要帮助添加一个条件，说每个原子只能在每个冒险中使用。

1. 教授突然抓起一块大石头把动物扔了出去。
医生没有在东非打猎，也没有被一只河马。上校的犀牛之旅不在中环在非洲，一个猎人用他的裸奔赶走了一只动物手。北美野牛袭击了一名猎人。
2. 消防队长在南非打猎。
3. 美洲狮被船长用空枪击中头部。
西非的猎人没有有枪，而且他也不是那个用枪与袭击者搏斗的人服装。
4. 大象不是被棍子赶走的。

我是这样做的:

hunter(professor).
hunter(doctor).
hunter(colonel).
hunter(fire_chief).
hunter(captain).
animal(rhino).
animal(bison).
animal(puma).
animal(hippo).
animal(elephant).
tool(stick).
tool(empty_gun).
tool(garment).
tool(hands).
tool(stone).
location(north_africa).
location(central_africa).
location(south_africa).
location(west_africa).
location(east_africa).
adventure([H, A, T, L]) :-
hunter(H),
animal(A),
tool(T),
location(L),
not( invalid([H, A, T, L]) ),
iff( H = professor, T = stone),
iff( H = colonel, A = rhino),
iff( H = fire_chief, L = south_africa),
iff( A = bison, L = north_africa),
iff( T = hands, L = central_africa),
iff( H = captain, A = puma),
iff( H = captain, T = empty_gun).
invalid_list([
[doctor, _, _, east_africa],
[doctor, hippo, _, _],
[colonel, _, _, central_africa],
[_, rhino, _, central_africa],
[_, _, empty_gun, west_africa],
[_, _, garment, west_africa],
[_, elephant, stick, _]
]).
invalid(A) :- invalid_list(LL), member(A, LL).
iff(A, B) :- A , B ; not(A) , not(B).

得到以下输出。当然，我可以手动将其带入解决方案，但我想实现最后一步，其中每个原子只能使用一次。

?- adventure(X).
X = [professor, bison, stone, north_africa] ;
X = [professor, hippo, stone, west_africa] ;
X = [professor, hippo, stone, east_africa] ;
X = [professor, elephant, stone, west_africa] ;
X = [professor, elephant, stone, east_africa] ;
X = [doctor, bison, stick, north_africa] ;
X = [doctor, bison, garment, north_africa] ;
X = [doctor, elephant, hands, central_africa] ;
X = [colonel, rhino, stick, west_africa] ;
X = [colonel, rhino, stick, east_africa] ;
X = [colonel, rhino, garment, east_africa] ;
X = [fire_chief, hippo, stick, south_africa] ;
X = [fire_chief, hippo, garment, south_africa] ;
X = [fire_chief, elephant, garment, south_africa] ;
X = [captain, puma, empty_gun, east_africa] ;
false.

更新:

1. 我创建了all_unique/5来做所有的横向不平等比较。
2. 我意识到我需要同时询问所有的冒险。

更新后的程序陷入递归循环。我不知道为什么。

all_adventures([
[H1, A1, T1, L1],
[H2, A2, T2, L2],
[H3, A3, T3, L3],
[H4, A4, T4, L4],
[H5, A5, T5, L5]
]) :-
H1  = professor,
H2  = doctor,
H3  = colonel,
H4  = fire_chief,
H5  = captain,
animal(A1),
animal(A2),
animal(A3),
animal(A4),
animal(A5),
tool(T1),
tool(T2),
tool(T3),
tool(T4),
tool(T5),
location(L1),
location(L2),
location(L3),
location(L4),
location(L5),  
all_unique(A1, A2, A3, A4, A5),
all_unique(T1, T2, T3, T4, T5),
all_unique(L1, L2, L3, L4, L5),
adventure([H1, A1, T1, L1]),
adventure([H2, A2, T2, L2]),
adventure([H3, A3, T3, L3]),
adventure([H4, A4, T4, L4]),
adventure([H5, A5, T5, L5]).
1 ?- all_adventures(X).

Answer 1

我认为解决这类谜题的标准方法是从一个缩小的域中做出唯一的选择。

所做的每个选择都将所选元素从给定域中移除，因此它不在to的选择之列

这样通过构造保证选择是唯一的。这是由下面的select/2谓词完成的。

第二种机制是使用member逐步实例化表示解决方案Sol的共享表的部分:

hunters(   [professor, doctor, colonel, fire_chief, captain] ).
animals(   [rhino,      bison,    puma,   hippo,   elephant] ).
tools(     [stick,        gun, garment,   hands,    stone  ] ).
locations( [north,    central,   south,   west,     east   ] ).
select( [A|B], C) :- select( A,C,D), select( B,D).
select( [], _).
p(A,B,C,D,[A,B,C,D]).
sol(Sol) :- 
hunters(Hs),    animals(As), 
tools(Ts),
locations(Ls),
maplist( p, Hs,      A,     T,     L,        Sol),
member( [professor,  _   , stone,  _     ] , Sol),
member( [colonel,   rhino,  _   ,  _     ] , Sol),
member( [_,          _   , hands, central] , Sol),
member( [_,         bison,   _  , north  ] , Sol),
member( [fire_chief, _   ,   _  , south  ] , Sol),
member( [captain,   puma ,  gun ,  _     ] , Sol),
member( [_,          _   ,   TW , west   ] , Sol),
select( T, Ts),  TW = gun, TW = garment,
select( A, As),
select( L, Ls),
+ member( [doctor,  _,    _,    east] , Sol),
+ member( [doctor, hippo, _,    _   ] , Sol),
+ member( [colonel, _,    _, central] , Sol),
+ member( [_, elephant,  stick,    _] , Sol).

首先，用member语句说明了正规则。

然后通过select调用完成实例化。member和select都逐步增量地实例化了公共共享的知识存储，即解决方案Sol。不兼容的实例被拒绝，控件返回，并因此做出不同的选择。

否定规则是在相关实例化之后声明的，越快越好——但不是越快越好。这会产生

26 ?- time(sol(_X)), maplist(writeln,_X).
% 190 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
[professor,  bison,    stone,   north  ]
[doctor,     elephant, hands,   central]
[colonel,    rhino,    stick,   west   ]
[fire_chief, hippo,    garment, south  ]
[captain,    puma,     gun,     east   ]
true ;
% 1,029 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
false.

你的方法做了600倍的推断来得到相同的结果，并做了700倍的推断来完成搜索:

30 ?- time( all_adventures(_X)), maplist(writeln,_X).
% 122,782 inferences, 0.031 CPU in 0.030 seconds (104% CPU, 3935295 Lips)
[bison,   stone,    north_africa  ]
[elephant,hands,    central_africa]
[rhino,   stick,    west_africa   ]
[hippo,   garment,  south_africa  ]
[puma,    empty_gun,east_africa   ]
true ;
% 719,071 inferences, 0.078 CPU in 0.080 seconds (97% CPU, 9218800 Lips)
false.

也相当长，所以可能更难理解。

---

更"紧";可以使用具有互斥正规则的select/2而不是单独的member调用来进行公式制定。select/2的使用使得它有点"多成员":

sol(Sol) :- 
hunters(Hs),    animals(As), 
tools(Ts),
locations(Ls),
maplist( p, Hs,      A,     T,     L,        Sol),
select( [ [professor,  _   , stone,  _     ] 
, [colonel,   rhino,  _   ,  _     ] 
, [fire_chief, _   ,   _  , south  ]
, [captain,   puma ,  gun ,  _     ] ], Sol),
select( [ [_,          _   , hands, central] 
, [_,         bison,   _  , north  ] 
, [_,          _   ,   TW , west   ] ], Sol),
select( T, Ts),  TW = gun, TW = garment,
select( A, As),
select( L, Ls),
+ member( [doctor,  _,    _,    east] , Sol),
+ member( [doctor, hippo, _,    _   ] , Sol),
+ member( [colonel, _,    _, central] , Sol),
+ member( [_, elephant,  stick,    _] , Sol).

效率的提高非常小，现在需要183个推理来找到解决方案，916个来完成搜索。

Answer 2

在@gusbro的帮助下，我以一种我很满意的方式解决了这个问题。这段代码感觉很自然，很容易阅读，就像我想要的那样。

剧情简介:

1. 冒险是一个满足线索中的条件的4元组。

1 a)。排除条件很容易在带有通配符(_)的列表中进行模式匹配。

1b)需求条件需要用iff子句表示。

2. 我们需要询问哪些变量同时满足所有五个冒险，同时要求没有原子被重用。

% The professor tossed the animal with a suddenly grabbed large stone.
% The doctor did not hunt in East Africa and was not attacked by a hippopotamus.
% The colonel’s rhino adventure was not in Central Africa, where one of the hunters chased away an animal with his bare hands.
% The bison attacked one of the hunters in North Africa.
% The fire chief hunted in South Africa.
% The puma was hit in the head by the captain with an empty gun.
% The hunter in West Africa did not have any guns, and he was not the one who fight his attacker with a garment.
% The elephant was not chased away with a stick.
hunter(professor).
hunter(doctor).
hunter(colonel).
hunter(fire_chief).
hunter(captain).
animal(rhino).
animal(bison).
animal(puma).
animal(hippo).
animal(elephant).
tool(stick).
tool(empty_gun).
tool(garment).
tool(hands).
tool(stone).
location(north_africa).
location(central_africa).
location(south_africa).
location(west_africa).
location(east_africa).
adventure([H, A, T, L]) :-
hunter(H),
animal(A),
tool(T),
location(L),
not( invalid([H, A, T, L]) ),
iff( H = professor, T = stone),
iff( H = colonel, A = rhino),
iff( H = fire_chief, L = south_africa),
iff( A = bison, L = north_africa),
iff( T = hands, L = central_africa),
iff( H = captain, A = puma),
iff( H = captain, T = empty_gun).

all_adventures([
[A1, T1, L1],
[A2, T2, L2],
[A3, T3, L3],
[A4, T4, L4],
[A5, T5, L5]
]) :-
adventure([professor, A1, T1, L1]),
adventure([doctor, A2, T2, L2]),
adventure([colonel, A3, T3, L3]),
adventure([fire_chief, A4, T4, L4]),
adventure([captain, A5, T5, L5]),

all_different_atoms([A1, A2, A3, A4, A5]),
all_different_atoms([T1, T2, T3, T4, T5]),
all_different_atoms([L1, L2, L3, L4, L5]).

invalid_list([
[doctor, _, _, east_africa],
[doctor, hippo, _, _],
[colonel, _, _, central_africa],
[_, rhino, _, central_africa],
[_, _, empty_gun, west_africa],
[_, _, garment, west_africa],
[_, elephant, stick, _]
]).
invalid(A) :- invalid_list(LL), member(A, LL).
iff(A, B) :- A , B ; not(A) , not(B).
all_different_atoms(X):- +((select(M,X,Y), member(M,Y))).
1 ?- all_adventures(X).

Answer 3

https://www.swi-prolog.org/pldoc/man?predicate=all_distinct/1

(all_distinct/1是有限域约束求解模块的一部分)

EDIT:正如所指出的，这只适用于整数。当然，你可以把所有的原子都映射成整数，但这有点麻烦。

这里有一个谓词，它不是非常快，但会验证列表中的所有项都是不同的，并适用于任何Prolog项(数字，原子，字符串等):

all_unique(List) :- all_unique(List, []).
all_unique([], _).
all_unique([X|Xs], Seen) :-
+ member(X, Seen),
all_unique(Xs, [X|Seen]).

但是，正如所指出的，它只能与一个完全有效的参数List一起使用，这将导致一个暴力解决方案，并进行许多不必要的测试。

相反，您可以创建一个all_unique/1的版本，它延迟到事物被充分实例化为止。为此，将+ member(X, Seen)行更改为freeze(X, + member(X, Seen))。您可以看到它与以下查询一起工作:

?- List=[A,B,C], forall((all_unique(List), between(1,3,A), between(1,3,B), between(1,3,C), writeln(List))).

也:

?- List=[A,B,C], all_unique(List), forall((between(1,3,A), between(1,3,B), between(1,3,C), writeln(List))).