Incorrect results for Prolog project/puzzle
I am working in a hard Prolog project/puzzle but I cant find the solution. I would thank any help.
The practice is to model and solve logic programming through a maze. It consists of rooms, doors and keys. When two rooms are connected they are connected through a door which is closed by one or more locks, which will require to be opened to move from one room to the other. Keys and locks are indistinct , IE any key opens any lock. After opening a door it is always open, but the key's stuck in the lock and can not be recovered (lost forever), so that for opening each door they will take many keys and locks. In each room there can be unused keys, which can be collected for further opening new doors. Initially we have no keys.
The solution program must define a predicate camino / 3 (camino is road in Spanish) such that (A, F, X) is true if X is a road leading to the room F based on the stay, so that you can go opening the door with the keys corresponding available at all times. The road shall be calculated as a list of the names of the rooms in the order in which they cross (and thus starting at A and ending at F).
The program will define a predicate e / 2 of the form e (E , L ) for each room E, where L is the number of keys contained in that room. You also define a predicate p / 3 of the form p (E1, E2 , C) for each door, where C is the number of locks having the door that connects E1 and E2 rooms. The program should maintain the state of the rooms (if they have keys or not) and doors (if already open or still
locked) at all times.
An example would be (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).
Results should be:
?‐ camino(a,f,X).
X = [a,b,a,c,d,f] ?
yes
?‐ camino(a,f,X).
X = [a,c,d,f] ?
yes
This is my current code. It finds its way to the destiny but it's not correct. Also I still haven't applied the cuts so that it only gives me one answer:
%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).
A method, that does not provides the optimal path (in the sense of minimal number of steps between rooms), but fulfills the request is as following. Main rule is:
path( Orig, Dest, Res ) :-
e( Orig, Keys ),
nextDoor( Dest, [(Orig,Orig)], Keys, [_|OpenDoors] ), !,
joinDoors( Orig, OpenDoors, [Orig], Res ), !.
that means, after init the number of keys with the keys of the initial room, algorithm will decide in which order the doors must be opened (nextDoor), and second will find the path between one door to next door in previous list.
The rationalle is: at a given moment, we have a set of open doors, and a set of rooms connected by these open doors. Movement across the area of open doors and visited rooms is free, doors are already open and visited rooms has not yet keys. Thus, we are only interested in decide which is the next door we must open. The rules to decide this order of doors to open is:
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 ).
where two utilities are used, one to provide bidirectional paths:
door(From,To,Cost) :-
( p(From,To,Cost); p(To,From,Cost) ).
and another one to find the rooms in the area of already visited ones (rooms connected by open doors):
visitedRoom( Room, OpenDoors ) :-
( member( (_,Room), OpenDoors ); member( (Room,_), OpenDoors ) ).
The second step is go from one door to the next door following the previous order.
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 ).
where roomToRoom is a clasical algorithm to find a path (TODO: optimize to find the shortest path):
roomToRoom( DestRoom, DestRoom, Path, Path ) :- !.
roomToRoom( CurrentRoom, DestRoom, Path, Res ) :-
door( CurrentRoom, NextRoom, _ ),
\+ member( NextRoom, Path ),
roomToRoom( DestRoom, NextRoom, [NextRoom|Path], Res ).
If we try with the data provided in the example:
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).
the result is:
?- path(a,f,Path).
Path = [a, b, a, c, d, f].