maze - Incorrect results for Prolog project/puzzle -

i working in hard prolog project/puzzle cant find solution. thank help.

the practice model , solve logic programming through maze. consists of rooms, doors , keys. when 2 rooms connected connected through door closed 1 or more locks, require opened move 1 room other. keys , locks indistinct , ie key opens lock. after opening door open, key's stuck in lock , can not recovered (lost forever), opening each door take many keys , locks. in each room there can unused keys, can collected further opening new doors. have no keys.

the solution program must define predicate camino / 3 (camino road in spanish) such (a, f, x) true if x road leading room f based on stay, can go opening door keys corresponding available @ times. road shall calculated list of names of rooms in order in cross (and starting @ a , ending @ f).

the program define predicate e / 2 of form e (e , l ) each room e, l number of keys contained in room. define predicate p / 3 of form p (e1, e2 , c) each door, c number of locks having door connects e1 , e2 rooms. program should maintain state of rooms (if have keys or not) , doors (if open or still locked) @ times.

an example (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 current code. finds way destiny it's not correct. still haven't applied cuts gives me 1 answer:

%code  % these rooms , number of keys contain e(a,1). e(b,2). e(c,1). e(d,0). e(e,0).  e(f,0).  %these doors , number of keys needed 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 start @ destiny        concatenate([],[f],x).     %%%%%%%%%%%%%%%%%%%%%%%%%%     camino(a,f,x):-        a\==f,                     %check if dont start @ destiny        concatenate([],[a],r),        findroad(a,f,0,r,x).     %%%%%%%%%%%%%%%%%% %true if x road (list) leads room f starting % findroad(a,f,k,r,x):-     %k key ---  initial keys         addkey(a,k,l),        %l new key--- number of keys after add keys of room         pickkey(a),           %we put number of keys of room 0         passdoor(a,l,p,_),    %p position-- position of new room         opendoor(a,p),        %we put number of keys needed pass door 0         p == f,               %we check if have finished         concatenate(r,[p],x). %we concatenate destiny , end    findroad(a,f,k,r,x):-     %k key ---  initial keys        addkey(a,k,l),        %l new key--- number of keys after add keys of room         pickkey(a),           %we put number of keys of room 0         passdoor(a,l,p,l2),   %p position-- position of new room         opendoor(a,p),        %we put number of keys needed pass door 0         p \== f,              %we check haven't finished        concatenate(r,[p],r2),%we concatenate path have moment        findroad(p,f,l2,r2,x).  addkey(a,k,l):-         e(a,n),         l k+n.      passdoor(a,l,p,l2):-         p(a,p,w),         l2 l-w,         l2 >= 0.    passdoor(a,l,p,l2):-        p(p,a,w),        l2 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, not provides optimal path (in sense of minimal number of steps between rooms), fulfills request 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 number of keys keys of initial room, algorithm decide in order doors must opened (nextdoor), , second find path between 1 door next door in previous list.

the rationalle is: @ given moment, have set of open doors, , set of rooms connected these open doors. movement across area of open doors , visited rooms free, doors open , visited rooms has not yet keys. thus, interested in decide next door must open. rules decide order of doors open is:

nextdoor( dest, opendoors, _, res ) :-   visitedroom( dest, opendoors ),    !,   reverse( opendoors, res ).   nextdoor( dest, opendoors, keys, res ) :-   /* choice visited room */   visitedroom( room, opendoors ),     /* next door not yet open */   door( room, nextroom, doorcost ),   \+ member( (room,nextroom), opendoors ),   \+ member( (nextroom,room), opendoors ),    /* can open door ? */   doorcost =< keys,    /* not open doors rooms visited */   \+ visitedroom( nextroom, opendoors ),    /* ok, cross door , next 1 */   e( nextroom, roomaward ),   keys2 keys-doorcost+roomaward,   nextdoor( dest, [(room,nextroom)|opendoors], keys2, res ). 

where 2 utilities used, 1 provide bidirectional paths:

door(from,to,cost) :-   ( p(from,to,cost); p(to,from,cost) ). 

and 1 find rooms in area of visited ones (rooms connected open doors):

visitedroom( room, opendoors ) :-   ( member( (_,room), opendoors ); member( (room,_), opendoors ) ). 

the second step go 1 door next door following 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 clasical algorithm find path (todo: optimize find 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 try data provided in 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].