CODEWITHSUNDEEP
recursionprologmazetransitive-closure
chnging
chnging

Reputation: 775

Prolog: Finding path in a maze

Let's say we have a robot that is on a Chess Board and can move like a King can.

The board is with coords from [1,1] to [8,8].

The starting position is [1,1] the final is [8,8]. There is a list X that contains lists of obstacle's coords for example [[1,4],[2,5],[5,6]]. The problem is: is there a possible way for the robot to move from the starting to the final position.

I made this predicates:

path([A,B],_):- A is 8, B is 8.
path([A,B],X):- 
        possibleMoves(A,B,L), % possibleMoves returns a list of all the possible coords that
        the robot can go to. (Example for [1,1] are [[0,1],[0,0],[2,1]...])

        member([Ex,Ey],L), % member generates all the possible members from the list L
        not(member([Ex,Ey],X)), % if this member is not member of the "forbidden ones"
        Ex<9,Ex>0,Ey<9,Ey>0, % and its coords are on the board
        path([Ex,Ey],X).


isTherePath(X):- possibleMoves(1,1,L),
                 member(E,L),
                 path(E,X).

But there is a mistake and it does not return any value. The recursion never stops I can't find why.

Upvotes: 1

Views: 2026

Answers (1)

false
false

Reputation: 10102

Define in one predicate, what a valid step is - including all restrictions you have. Stick to this naming convention: X0 the "first" value, X the "last" value

step(Forbidden,[X0,Y0],[X,Y]) :-
   possibleMoves(X0,Y0,L), % rather: possibleMove([X0,Y0],L),
   member([X,Y],L),
   between(1,8,X),
   between(1,8,Y),
   non_member([X,Y],Forbidden).

Now you have a path with:

 ..., closure0(step(Forbidden), S0,S), ...

closure0/3 takes care of cycles.

Upvotes: 2

Related Questions