Prolog - Solve labyrinth

Question

I need help with prolog problem.

The text of problem is: Write a predicate Prolog called Labyrinth(Lab, From, To) that receive in input a labyrinth, initial position and end position and print the list of possible moves (up,right, bottom, left). The labyrinth is a 7x7 matrix with list of rows and list of columns. Each cell contains 'w' if is a wall, otherwise 'e' if empty. the start and end position are describe with a function in/2 that have for arguments a row and column.

This is an example of matrix (index start at 0)

Labyrinth([
    [e,e,w,w,w,w,w],           
    [w,e,w,e,w,e,w],
    [w,e,w,e,w,e,w],
    [w,e,e,e,w,e,w],
    [w,e,w,e,w,e,w],
    [w,e,e,e,e,e,w],
    [e,w,w,w,w,e,e]
    ], in(0,0), in(6,6)

I understood that need:

four predicate, one for each move (up, down, left, right);
one test if the current cell is == 'w' or is == 'e';
A goal test to check if current position is the final position

I'm stucked to write the correct sequence and predicate to solve the problem. Someone has some hint?

/******* UPDATE ******************/ @CapelliC here my code. I looked for write the necessary predicate, but I'm stuck into backtracking

get_cell([R,C], Data,L):-
    nth1(R,Data,L1),
    nth1(C,L1,L).

labyrinth(Map, Start, Finish, Move) :-

   move(Start, Move),
   update(Start, Move, NewState),
   legal(NewState, Map),
   \+ member(NewState, Finish),
   labyrinth(Map, NewState, [NewState|Finish], Move).

legal( p(X,Y), Map) :-
   X > 0,
   Y > 0,
   get_cell([X,Y], Map, Z),
   %write(Z),
   Z \= w .

% UP
update(  p(X, Y), up, p(X_new, Y)  ) :-
    write('up '),
    X_new is X - 1.

% DOWN
update(  p(X,Y), down, p(X_new, Y) ) :-
    write('down '),
    X_new is X + 1.

% LEFT
update(  p(X,Y), left, p(X, Y_new)  ) :-
   write('left '),
   Y_new is Y - 1.

% RIGHT
update(  p(X,Y), right, p(X, Y_new)  ) :-
   write('right '),
   Y_new is Y + 1.

move(  p( _, _ ), up    ).
move(  p( _, _ ), down  ).
move(  p( _, _ ), left  ).
move(  p( _, _ ), right ).

And I call the program like:

labyrinth([
   [e,e,w,w,w,w,w],           
   [w,e,w,e,w,e,w],
   [w,e,w,e,w,e,w],
   [w,e,e,e,w,e,w],
   [w,e,w,e,w,e,w],
   [w,e,e,e,e,e,w],
   [e,w,w,w,w,e,e]
], p(1,2), p(6,6), _)

This questions seems not to be related to backtracking, there are problems like ,using nth1 on a zero based arrays. A position is illegal if it's equal to 0, but it's a zero based array. Printing directions before you found a path. The recursive call on labyrinth(Map, Start, Finish, Move) from labyrinth(Map, NewState, [NewState|Finish], Move) also don't makes a lot of sense. What you need to do is debug your program. If you reply, I can consider starting over and giving you the solution, since it looks like a fun homework project. — call-me
@call-me That is a first try to solve problem. I'm stuck in finding the correct predicates. After predicate, I would find a way to improve algorithm — Camel2Camel

call-me call-me · Accepted Answer · 2020-06-19T01:21:59

Some overall changes, this could be a way to implement backtracking in the maze. There is an extra list of positions to keep track if a position is already visited before, if the maze would not have cycles this would not have been necessary.

get_cell([R,C], Data,L):-
    nth0(R,Data,L1),
    nth0(C,L1,L).

labyrinth(Map, Start, Finish):-
    labyrinth(Map, Start, Finish,[], [],Solution),!,
    reverse(Solution,S),
    print(S).

labyrinth(_, Finish, Finish,_, Out,Out). %Unification of solution
labyrinth(Map, Start, Finish, Positions,Moves,Out) :-
move(Move),
update(Start, Move, NewState),
\+ member(NewState, Positions),
legal(NewState, Map),
labyrinth(Map, NewState, Finish,[NewState|Positions],[Move|Moves],Out).

legal( p(X,Y), Map) :-
X >= 0, 7>X,
Y >= 0, 7>Y,
get_cell([X,Y], Map, Z),
%write(Z),
Z \= w .

% UP
update(  p(X, Y), up, p(X_new, Y)  ) :-
    X_new is X - 1.

% DOWN
update(  p(X,Y), down, p(X_new, Y) ) :-
    X_new is X + 1.

% LEFT
update(  p(X,Y), left, p(X, Y_new)  ) :-
Y_new is Y - 1.

% RIGHT
update(  p(X,Y), right, p(X, Y_new)  ) :-
Y_new is Y + 1.

move(  up    ).
move(  down  ).
move(  left  ).
move(  right ).

Prolog - Solve labyrinth

1 Answers