Prolog project/puzzle 的错误结果
Incorrect results for Prolog project/puzzle
我正在使用困难的 Prolog project/puzzle 但我找不到解决方案。
我会感谢任何帮助。
实践是通过迷宫对逻辑编程进行建模和求解。
它由房间、门和钥匙组成。当两个房间相连时，它们通过一扇门连接，该门由一把或多把锁关闭，需要打开才能从一个房间移动到另一个房间。钥匙和锁是分不清的，IE任意钥匙开任意锁。打开一扇门后，它一直是开着的，但钥匙卡在锁里，无法取回（永远丢失），因此打开每扇门，他们将带走许多钥匙和锁。每个房间都可以有未使用的钥匙，可以收集这些钥匙以进一步打开新门。最初我们没有钥匙。
解决方案必须定义一个谓词 camino / 3（camino 在西班牙语中是道路），使得 (A, F, X) 在 X 是根据入住情况通往房间F的道路，方便随时携带相应钥匙开门。道路应按照房间名称的顺序计算为房间名称列表（因此从 A 开始并在 F 结束）。
该程序将为每个房间 E 定义一个形式为 e (E , L ) 的谓词 e / 2，其中 L 是该房间中包含的钥匙数。您还为每扇门定义了一个形式为 p (E1, E2 , C) 的谓词 p / 3，其中 C 是具有连接 E1 和 E2 房间的门的锁的数量.该程序应该保持房间的状态（如果他们有钥匙或没有）和门（如果已经打开或仍然
锁定）在任何时候。
一个例子是 (Source):
%rooms+ number of keys
e(a,1).
e(b,2).
e(c,1).
e(d,0).
e(e,0).
e(f,0).
%Doors
p(a,b,1).
p(a,c,1).
p(b,d,1).
p(c,e,1).
p(d,f,1).
p(e,f,2).
结果应该是：
?‐ camino(a,f,X).
X = [a,b,a,c,d,f] ?
yes
?‐ camino(a,f,X).
X = [a,c,d,f] ?
yes
这是我当前的代码。它找到了通往命运的道路，但它是不正确的。而且我还没有应用削减，所以它只给了我一个答案：
%CODE
% these are the rooms and the number of keys they contain
e(a,1).
e(b,2).
e(c,1).
e(d,0).
e(e,0).
e(f,0).
%these are the doors and the number of keys needed to open them
p(a,b,1).
p(a,c,1).
p(b,d,1).
p(c,e,1).
p(d,f,1).
p(e,f,2).
concatenate([],L,L).
concatenate([X|M],L,[X|Y]) :-
concatenate(M,L,Y).
%%%%%%%%%%%%%
camino(A,F,X):-
A==F, %check if we start at the destiny
concatenate([],[F],X).
%%%%%%%%%%%%%%%%%%%%%%%%%%
camino(A,F,X):-
A\==F, %check if we dont start at the destiny
concatenate([],[A],R),
findRoad(A,F,0,R,X).
%%%%%%%%%%%%%%%%%%
%TRUE if x is a road (list) that leads to room F starting from A
%
findRoad(A,F,K,R,X):- %k is key --- initial keys
addkey(A,K,L), %L new key--- number of keys after we add the keys of the room
pickkey(A), %we put the number of keys of the room to 0
passDoor(A,L,P,_), %P is position-- position of the new room
opendoor(A,P), %we put the number of keys needed to pass the door to 0
P == F, %we check if we have finished
concatenate(R,[P],X). %we concatenate the destiny and end
findRoad(A,F,K,R,X):- %k is key --- initial keys
addkey(A,K,L), %L new key--- number of keys after we add the keys of the room
pickkey(A), %we put the number of keys of the room to 0
passDoor(A,L,P,L2), %P is position-- position of the new room
opendoor(A,P), %we put the number of keys needed to pass the door to 0
P \== F, %we check we haven't finished
concatenate(R,[P],R2),%we concatenate the path we have for the moment
findRoad(P,F,L2,R2,X).
addkey(A,K,L):-
e(A,N),
L is K+N.
passDoor(A,L,P,L2):-
p(A,P,W),
L2 is L-W,
L2 >= 0.
passDoor(A,L,P,L2):-
p(P,A,W),
L2 is L-W,
L2 >= 0.
pickkey(A):-
e(A,_) = e(A,0).
opendoor(A,P):-
p(A,P,_) = p(A,P,0).
opendoor(A,P):-
p(P,A,_) = p(P,A,0).
这是解决它的另一种尝试，但是它陷入了无限循环
%房间 + 钥匙数
e(a,1).
e(b,2).
e(c,1).
e(d,0).
e(e,0)。
e(f,0).
%门
p(a,b,1).
p(a,c,1).
p(b,d,2).
p(c,e,1).
p(d,f,1).
p(e,f,2).
%PRÁCTICA
连接([],L,L).
连接([X|M],L,[X|Y]) :-
concatenate(M,L,Y).
路径(A,F,X):-
A==F,
连接([],[F],X).
路径(A,F,X):-
A\==F,
连接([],[A],R),
探路者(A,F,0,R,[],[],,,X).
%TRUE 如果 x 是从 A 开始通向 F 房间的道路（列表）
探路者(A,F,K,R,ROOM,DOOR,ROOM2,DOOR3,X):- %k 是钥匙 --- 初始钥匙
addkey(A,K,L,ROOM,ROOM2), %L new key--- number of keys after we add the keys of the room
passDoor(A,L,P,_,DOOR,DOOR3), %P is position-- position of the new room
P == F, %we check if we have finished
concatenate([P],[R],X). %we concatenate the destiny and end
探路者(A,F,K,R,ROOM,DOOR,ROOM2,DOOR3,X):- %k 是钥匙 --- 初始钥匙
addkey(A,K,L,ROOM,ROOM2), %L new key--- number of keys after we add the keys of the room
passDoor(A,L,P,L2,DOOR,DOOR3),%P=new room L2 = new Nº of keys
P \== F, %we check we havent finished
concatenate([R],[P],R2), %we add the room we are to the path
pathfinder(P,F,L2,R2,ROOM2,DOOR3,_,_,X). %
addkey(A,K,L,ROOM,ROOM):-
member(A,ROOM), %checks if we hace visited the room
L is K. % If so [ROOM] and Nº of keys wont change
添加键(A,K,L,ROOM,ROOM2):-
not(member(A,ROOM)), %checks we havnt visited the room
e(A,N), %we save the number of keys of the room in N
L is K+N, %L is (Nº of previous keys)+ keys of the room
concatenate([ROOM],[A],ROOM2). %we add A to the list of visited rooms
passDoor(A,L,P,L2,DOOR,DOOR):-
member(p(A,P,_),DOOR), %checks if you have passed that door
L2 is L. %If you have allready passed it, the Nº of keys dont change
passDoor(A,L,P,L2,DOOR,DOOR3):-
not(member(p(A,P,_),DOOR)), %checks that you havent passed that door
p(A,P,W), %checks the door exists
L2 is L-W, %we substract to our keys the Nº of keys needed
L2 >= 0, %checks the result is > 0
concatenate([DOOR],[p(A,P,_)], DOOR2), %we add the door to the list of used doors
concatenate([DOOR2],[p(P,A,_)], DOOR3). % we add both ways in case we need to go back
一种不提供最佳路径（在房间之间的最小步数意义上）但满足请求的方法如下。主要规则是：
path( Orig, Dest, Res ) :-
e( Orig, Keys ),
nextDoor( Dest, [(Orig,Orig)], Keys, [_|OpenDoors] ), !,
joinDoors( Orig, OpenDoors, [Orig], Res ), !.
这意味着，在用初始房间的钥匙初始化钥匙数量后，算法将决定门必须按什么顺序打开（nextDoor），然后将找到一扇门到下一扇门之间的路径上一个列表。
基本原理是：在给定时刻，我们有一组打开的门，以及一组由这些打开的门连接的房间。在打开的门和访问过的房间区域中移动是免费的，门已经打开并且访问过的房间还没有钥匙。因此，我们只对决定我们必须打开的下一扇门感兴趣。决定这扇门开门顺序的规则是：
nextDoor( Dest, OpenDoors, _, Res ) :-
visitedRoom( Dest, OpenDoors ),
!,
reverse( OpenDoors, Res ).
nextDoor( Dest, OpenDoors, Keys, Res ) :-
/* choice a visited room */
visitedRoom( Room, OpenDoors ),
/* next door not yet open */
door( Room, NextRoom, DoorCost ),
\+ member( (Room,NextRoom), OpenDoors ),
\+ member( (NextRoom,Room), OpenDoors ),
/* we can open door ? */
DoorCost =< Keys,
/* do not open doors to rooms already visited */
\+ visitedRoom( NextRoom, OpenDoors ),
/* ok, cross door and next one */
e( NextRoom, RoomAward ),
Keys2 is Keys-DoorCost+RoomAward,
nextDoor( Dest, [(Room,NextRoom)|OpenDoors], Keys2, Res ).
其中使用了两个实用程序，一个用于提供双向路径：
door(From,To,Cost) :-
( p(From,To,Cost); p(To,From,Cost) ).
还有一个是在已经访问过的区域中查找房间（通过开门连接的房间）：
visitedRoom( Room, OpenDoors ) :-
( member( (_,Room), OpenDoors ); member( (Room,_), OpenDoors ) ).
第二步是按照之前的顺序从一扇门走到另一扇门。
joinDoors( _, [], Path, Res ) :-
reverse( Path, Res ).
joinDoors( CurrentRoom, [ (RoomBeforeDoor, RoomAfterRoom ) | Q ], Path, Res ) :-
roomToRoom( CurrentRoom, RoomBeforeDoor, [], Path2 ),
append( Path2, Path, Path3 ),
joinDoors( RoomAfterRoom, Q, [RoomAfterRoom|Path3], Res ).
其中 roomToRoom 是寻找路径的经典算法（TODO：优化以找到最短路径）：
roomToRoom( DestRoom, DestRoom, Path, Path ) :- !.
roomToRoom( CurrentRoom, DestRoom, Path, Res ) :-
door( CurrentRoom, NextRoom, _ ),
\+ member( NextRoom, Path ),
roomToRoom( DestRoom, NextRoom, [NextRoom|Path], Res ).
如果我们尝试使用示例中提供的数据：
e(a,1).
e(b,2).
e(c,1).
e(d,0).
e(e,0).
e(f,0).
p(a,b,1).
p(a,c,1).
p(b,d,2). /* corrected */
p(c,d,1). /* add */
p(c,e,1).
p(d,f,1).
p(e,f,2).
结果是：
?- path(a,f,Path).
Path = [a, b, a, c, d, f].
为了确保得到最短路径，可以使用BFS搜索：
:- use_module(library(lambda)).
%rooms + number of keys
e(a,1).
e(b,2).
e(c,1).
e(d,0).
e(e,0).
e(f,0).
%Doors
p(a,b,1).
p(a,c,1).
p(b,d,2).
p(c,d,1).
p(c,e,1).
p(d,f,1).
p(e,f,2).
% Doors are closed at the beginning of the puzzle
% state(CurrentRoom, NumberKeys, StateRooms, StateDoors)
init(state(a, 0, LstRooms, LstDoors)) :-
setof(e(X,Y), X^Y^e(X,Y), LstRooms),
setof(p(X,Y,Z, closed), X^Y^Z^p(X,Y,Z), LstDoors).
% final state
final(state(f, _, _, _)).
% skeleton of BFS search
:- dynamic(states/1).
puzzle :-
retractall(states(_)),
% set the initial state
init(State),
assert(states([[State]])),
repeat,
nextstates,
% if we get to the final state,
% eneded/1 succeeds with a path
ended(Path),
maplist(writeln, Path).
% test if we have finished the puzzle
% succeeds with a Path to the solution
% This BFS gives a reverse path to the solution
ended(Path) :-
final(State),
states(LstStates),
% may be there is no solution ?
( LstStates = []
-> Path = []
; include(=([State|_]), LstStates, Paths),
Paths = [RPath|_],
reverse(RPath, Path)).
nextstates :-
retract(states(LstStates)),
foldl(\States^Y^Z^(nextstates_one(States, NewStates),
append(Y, NewStates, Z)),
LstStates, [], LstNewStates),
assert(states(LstNewStates)).
% First we search the rooms near the current room
% Next we build the new paths
nextstates_one([Head | Tail], NewStates) :-
nextrooms(Head, LState),
foldl([Head, Tail] +\X^Y^Z^(member(X, Tail)
-> Z = Y
; append([[X, Head | Tail]], Y, Z)),
LState, [], NewStates),
% we must put a cut here,
% if **ended(Path)** fails, we must continue at **repeat**
!.
% fetch all the rooms near the current room
nextrooms(state(R, K, SR, SD), States) :-
% we fetch keys (even when there is no more keys left !)
select(e(R, Key), SR, TSR),
NK is K + Key,
sort([e(R, 0) | TSR], NSR),
% we test all the doors
foldl([R,NK,NSR,SD]+\X^Y^Z^(X = p(R1, R2, Keys, Open),
% can we go to the next door ?
( select(R, [R1,R2], [NR])
-> ( Open = opened
% the door is opened, we came in without changint anything
-> Z = [state(NR, NK, NSR, SD) | Y]
% the door is closed, have we enough keys ?
; ( Keys =< NK
-> NK1 is NK - Keys,
select(p(R1, R2, Keys, Open), SD, TSD),
sort([p(R1, R2, 0, opened) | TSD], NSD),
Z = [state(NR, NK1, NSR, NSD) | Y]
; Z = Y))
; Z = Y)),
SD, [], States).
我正在使用困难的 Prolog project/puzzle 但我找不到解决方案。 我会感谢任何帮助。
实践是通过迷宫对逻辑编程进行建模和求解。 它由房间、门和钥匙组成。当两个房间相连时，它们通过一扇门连接，该门由一把或多把锁关闭，需要打开才能从一个房间移动到另一个房间。钥匙和锁是分不清的，IE任意钥匙开任意锁。打开一扇门后，它一直是开着的，但钥匙卡在锁里，无法取回（永远丢失），因此打开每扇门，他们将带走许多钥匙和锁。每个房间都可以有未使用的钥匙，可以收集这些钥匙以进一步打开新门。最初我们没有钥匙。
解决方案必须定义一个谓词 camino / 3（camino 在西班牙语中是道路），使得 (A, F, X) 在 X 是根据入住情况通往房间F的道路，方便随时携带相应钥匙开门。道路应按照房间名称的顺序计算为房间名称列表（因此从 A 开始并在 F 结束）。
该程序将为每个房间 E 定义一个形式为 e (E , L ) 的谓词 e / 2，其中 L 是该房间中包含的钥匙数。您还为每扇门定义了一个形式为 p (E1, E2 , C) 的谓词 p / 3，其中 C 是具有连接 E1 和 E2 房间的门的锁的数量.该程序应该保持房间的状态（如果他们有钥匙或没有）和门（如果已经打开或仍然
锁定）在任何时候。
一个例子是 (Source):
%rooms+ number of keys
e(a,1).
e(b,2).
e(c,1).
e(d,0).
e(e,0).
e(f,0).
%Doors
p(a,b,1).
p(a,c,1).
p(b,d,1).
p(c,e,1).
p(d,f,1).
p(e,f,2).
结果应该是：
?‐ camino(a,f,X).
X = [a,b,a,c,d,f] ?
yes
?‐ camino(a,f,X).
X = [a,c,d,f] ?
yes
这是我当前的代码。它找到了通往命运的道路，但它是不正确的。而且我还没有应用削减，所以它只给了我一个答案：
%CODE
% these are the rooms and the number of keys they contain
e(a,1).
e(b,2).
e(c,1).
e(d,0).
e(e,0).
e(f,0).
%these are the doors and the number of keys needed to open them
p(a,b,1).
p(a,c,1).
p(b,d,1).
p(c,e,1).
p(d,f,1).
p(e,f,2).
concatenate([],L,L).
concatenate([X|M],L,[X|Y]) :-
concatenate(M,L,Y).
%%%%%%%%%%%%%
camino(A,F,X):-
A==F, %check if we start at the destiny
concatenate([],[F],X).
%%%%%%%%%%%%%%%%%%%%%%%%%%
camino(A,F,X):-
A\==F, %check if we dont start at the destiny
concatenate([],[A],R),
findRoad(A,F,0,R,X).
%%%%%%%%%%%%%%%%%%
%TRUE if x is a road (list) that leads to room F starting from A
%
findRoad(A,F,K,R,X):- %k is key --- initial keys
addkey(A,K,L), %L new key--- number of keys after we add the keys of the room
pickkey(A), %we put the number of keys of the room to 0
passDoor(A,L,P,_), %P is position-- position of the new room
opendoor(A,P), %we put the number of keys needed to pass the door to 0
P == F, %we check if we have finished
concatenate(R,[P],X). %we concatenate the destiny and end
findRoad(A,F,K,R,X):- %k is key --- initial keys
addkey(A,K,L), %L new key--- number of keys after we add the keys of the room
pickkey(A), %we put the number of keys of the room to 0
passDoor(A,L,P,L2), %P is position-- position of the new room
opendoor(A,P), %we put the number of keys needed to pass the door to 0
P \== F, %we check we haven't finished
concatenate(R,[P],R2),%we concatenate the path we have for the moment
findRoad(P,F,L2,R2,X).
addkey(A,K,L):-
e(A,N),
L is K+N.
passDoor(A,L,P,L2):-
p(A,P,W),
L2 is L-W,
L2 >= 0.
passDoor(A,L,P,L2):-
p(P,A,W),
L2 is L-W,
L2 >= 0.
pickkey(A):-
e(A,_) = e(A,0).
opendoor(A,P):-
p(A,P,_) = p(A,P,0).
opendoor(A,P):-
p(P,A,_) = p(P,A,0).
这是解决它的另一种尝试，但是它陷入了无限循环
%房间 + 钥匙数 e(a,1).
e(b,2).
e(c,1).
e(d,0).
e(e,0)。
e(f,0).
%门
p(a,b,1).
p(a,c,1).
p(b,d,2).
p(c,e,1).
p(d,f,1).
p(e,f,2).
%PRÁCTICA
连接([],L,L).
连接([X|M],L,[X|Y]) :-
concatenate(M,L,Y).
路径(A,F,X):-
A==F,
连接([],[F],X).
路径(A,F,X):-
A\==F,
连接([],[A],R),
探路者(A,F,0,R,[],[],,,X).
%TRUE 如果 x 是从 A 开始通向 F 房间的道路（列表）
探路者(A,F,K,R,ROOM,DOOR,ROOM2,DOOR3,X):- %k 是钥匙 --- 初始钥匙
addkey(A,K,L,ROOM,ROOM2), %L new key--- number of keys after we add the keys of the room
passDoor(A,L,P,_,DOOR,DOOR3), %P is position-- position of the new room
P == F, %we check if we have finished
concatenate([P],[R],X). %we concatenate the destiny and end
探路者(A,F,K,R,ROOM,DOOR,ROOM2,DOOR3,X):- %k 是钥匙 --- 初始钥匙
addkey(A,K,L,ROOM,ROOM2), %L new key--- number of keys after we add the keys of the room
passDoor(A,L,P,L2,DOOR,DOOR3),%P=new room L2 = new Nº of keys
P \== F, %we check we havent finished
concatenate([R],[P],R2), %we add the room we are to the path
pathfinder(P,F,L2,R2,ROOM2,DOOR3,_,_,X). %
addkey(A,K,L,ROOM,ROOM):-
member(A,ROOM), %checks if we hace visited the room
L is K. % If so [ROOM] and Nº of keys wont change
添加键(A,K,L,ROOM,ROOM2):-
not(member(A,ROOM)), %checks we havnt visited the room
e(A,N), %we save the number of keys of the room in N
L is K+N, %L is (Nº of previous keys)+ keys of the room
concatenate([ROOM],[A],ROOM2). %we add A to the list of visited rooms
passDoor(A,L,P,L2,DOOR,DOOR):-
member(p(A,P,_),DOOR), %checks if you have passed that door
L2 is L. %If you have allready passed it, the Nº of keys dont change
passDoor(A,L,P,L2,DOOR,DOOR3):-
not(member(p(A,P,_),DOOR)), %checks that you havent passed that door
p(A,P,W), %checks the door exists
L2 is L-W, %we substract to our keys the Nº of keys needed
L2 >= 0, %checks the result is > 0
concatenate([DOOR],[p(A,P,_)], DOOR2), %we add the door to the list of used doors
concatenate([DOOR2],[p(P,A,_)], DOOR3). % we add both ways in case we need to go back
一种不提供最佳路径（在房间之间的最小步数意义上）但满足请求的方法如下。主要规则是：
path( Orig, Dest, Res ) :-
e( Orig, Keys ),
nextDoor( Dest, [(Orig,Orig)], Keys, [_|OpenDoors] ), !,
joinDoors( Orig, OpenDoors, [Orig], Res ), !.
这意味着，在用初始房间的钥匙初始化钥匙数量后，算法将决定门必须按什么顺序打开（nextDoor），然后将找到一扇门到下一扇门之间的路径上一个列表。
基本原理是：在给定时刻，我们有一组打开的门，以及一组由这些打开的门连接的房间。在打开的门和访问过的房间区域中移动是免费的，门已经打开并且访问过的房间还没有钥匙。因此，我们只对决定我们必须打开的下一扇门感兴趣。决定这扇门开门顺序的规则是：
nextDoor( Dest, OpenDoors, _, Res ) :-
visitedRoom( Dest, OpenDoors ),
!,
reverse( OpenDoors, Res ).
nextDoor( Dest, OpenDoors, Keys, Res ) :-
/* choice a visited room */
visitedRoom( Room, OpenDoors ),
/* next door not yet open */
door( Room, NextRoom, DoorCost ),
\+ member( (Room,NextRoom), OpenDoors ),
\+ member( (NextRoom,Room), OpenDoors ),
/* we can open door ? */
DoorCost =< Keys,
/* do not open doors to rooms already visited */
\+ visitedRoom( NextRoom, OpenDoors ),
/* ok, cross door and next one */
e( NextRoom, RoomAward ),
Keys2 is Keys-DoorCost+RoomAward,
nextDoor( Dest, [(Room,NextRoom)|OpenDoors], Keys2, Res ).
其中使用了两个实用程序，一个用于提供双向路径：
door(From,To,Cost) :-
( p(From,To,Cost); p(To,From,Cost) ).
还有一个是在已经访问过的区域中查找房间（通过开门连接的房间）：
visitedRoom( Room, OpenDoors ) :-
( member( (_,Room), OpenDoors ); member( (Room,_), OpenDoors ) ).
第二步是按照之前的顺序从一扇门走到另一扇门。
joinDoors( _, [], Path, Res ) :-
reverse( Path, Res ).
joinDoors( CurrentRoom, [ (RoomBeforeDoor, RoomAfterRoom ) | Q ], Path, Res ) :-
roomToRoom( CurrentRoom, RoomBeforeDoor, [], Path2 ),
append( Path2, Path, Path3 ),
joinDoors( RoomAfterRoom, Q, [RoomAfterRoom|Path3], Res ).
其中 roomToRoom 是寻找路径的经典算法（TODO：优化以找到最短路径）：
roomToRoom( DestRoom, DestRoom, Path, Path ) :- !.
roomToRoom( CurrentRoom, DestRoom, Path, Res ) :-
door( CurrentRoom, NextRoom, _ ),
\+ member( NextRoom, Path ),
roomToRoom( DestRoom, NextRoom, [NextRoom|Path], Res ).
如果我们尝试使用示例中提供的数据：
e(a,1).
e(b,2).
e(c,1).
e(d,0).
e(e,0).
e(f,0).
p(a,b,1).
p(a,c,1).
p(b,d,2). /* corrected */
p(c,d,1). /* add */
p(c,e,1).
p(d,f,1).
p(e,f,2).
结果是：
?- path(a,f,Path).
Path = [a, b, a, c, d, f].
为了确保得到最短路径，可以使用BFS搜索：
:- use_module(library(lambda)).
%rooms + number of keys
e(a,1).
e(b,2).
e(c,1).
e(d,0).
e(e,0).
e(f,0).
%Doors
p(a,b,1).
p(a,c,1).
p(b,d,2).
p(c,d,1).
p(c,e,1).
p(d,f,1).
p(e,f,2).
% Doors are closed at the beginning of the puzzle
% state(CurrentRoom, NumberKeys, StateRooms, StateDoors)
init(state(a, 0, LstRooms, LstDoors)) :-
setof(e(X,Y), X^Y^e(X,Y), LstRooms),
setof(p(X,Y,Z, closed), X^Y^Z^p(X,Y,Z), LstDoors).
% final state
final(state(f, _, _, _)).
% skeleton of BFS search
:- dynamic(states/1).
puzzle :-
retractall(states(_)),
% set the initial state
init(State),
assert(states([[State]])),
repeat,
nextstates,
% if we get to the final state,
% eneded/1 succeeds with a path
ended(Path),
maplist(writeln, Path).
% test if we have finished the puzzle
% succeeds with a Path to the solution
% This BFS gives a reverse path to the solution
ended(Path) :-
final(State),
states(LstStates),
% may be there is no solution ?
( LstStates = []
-> Path = []
; include(=([State|_]), LstStates, Paths),
Paths = [RPath|_],
reverse(RPath, Path)).
nextstates :-
retract(states(LstStates)),
foldl(\States^Y^Z^(nextstates_one(States, NewStates),
append(Y, NewStates, Z)),
LstStates, [], LstNewStates),
assert(states(LstNewStates)).
% First we search the rooms near the current room
% Next we build the new paths
nextstates_one([Head | Tail], NewStates) :-
nextrooms(Head, LState),
foldl([Head, Tail] +\X^Y^Z^(member(X, Tail)
-> Z = Y
; append([[X, Head | Tail]], Y, Z)),
LState, [], NewStates),
% we must put a cut here,
% if **ended(Path)** fails, we must continue at **repeat**
!.
% fetch all the rooms near the current room
nextrooms(state(R, K, SR, SD), States) :-
% we fetch keys (even when there is no more keys left !)
select(e(R, Key), SR, TSR),
NK is K + Key,
sort([e(R, 0) | TSR], NSR),
% we test all the doors
foldl([R,NK,NSR,SD]+\X^Y^Z^(X = p(R1, R2, Keys, Open),
% can we go to the next door ?
( select(R, [R1,R2], [NR])
-> ( Open = opened
% the door is opened, we came in without changint anything
-> Z = [state(NR, NK, NSR, SD) | Y]
% the door is closed, have we enough keys ?
; ( Keys =< NK
-> NK1 is NK - Keys,
select(p(R1, R2, Keys, Open), SD, TSD),
sort([p(R1, R2, 0, opened) | TSD], NSD),
Z = [state(NR, NK1, NSR, NSD) | Y]
; Z = Y))
; Z = Y)),
SD, [], States).