CODEWITHSUNDEEP
prolog
John Z
John Z

Reputation: 89

Prolog pathfinding stuck in a loop after found the answer

I have my code to find all the possible solutions in a given grid from point A to B, My problem is after finding all the solutions, it will start to trace back and forth forever. I guess it's legal because all the conditions are met. However, I have trouble giving out a condition that will prevent that. Any help?

move([X,Y], e, [X1,Y]) :- X1 is X+1.
move([X,Y], n, [X,Y1]) :- Y1 is Y+1.
move([X,Y], s, [X,Y1]) :- Y1 is Y-1.

safe([Xn,Yn],[Xg,Yg]) :-
  Xg >= Xn,
  Xn > 0,
  Yg >= Yn,
  Yn > 0. %next state must be whit-in grid otherwise false

%% solve([X,Y],[TargetX,TargetY],[Xg,Yg],[FirstMove|OtherMoves])

solve([X,Y],[X,Y],_,[]) :- !.
solve([X,Y],[Xt,Yt],[Xg,Yg],[Fm|Om]) :-
  move([X,Y],Fm,[Xn,Yn]),
  safe([Xn,Yn],[Xg,Yg]),
  solve([Xn,Yn],[Xt,Yt],[Xg,Yg],Om).

output:

?- solve([1,1],[2,2],[2,2],P).
P = [e, n] ;
P = [n, e] ;
P = [n, s, e, n] ;
P = [n, s, n, e] ;
P = [n, s, n, s, e, n] ;
P = [n, s, n, s, n, e] ;
P = [n, s, n, s, n, s, e, n] ;
P = [n, s, n, s, n, s, n, e] ;
P = [n, s, n, s, n, s, n, s, e|...] ;
P = [n, s, n, s, n, s, n, s, n|...] ;

Upvotes: 1

Views: 65

Answers (1)

Duda
Duda

Reputation: 3736

solve(A,B,C,D):-
  solve(A,B,C,D,[]).

solve([X,Y],[X,Y],_,[],_) :- !.
solve([X,Y],[Xt,Yt],[Xg,Yg],[Fm|Om],Chars) :-
  move([X,Y],Fm,[Xn,Yn]),
  \+ member(Fm,Chars),
  safe([Xn,Yn],[Xg,Yg]),
  solve([Xn,Yn],[Xt,Yt],[Xg,Yg],Om, [Fm|Chars]).

?- solve([1,1],[2,2],[2,2],P).
P = [e, n] ;
P = [n, e] ;
false.

All I did was to introduce another variable Chars which holds the visited nodes (?) and every time a move is tried it checks, if this move was already taken by asking if Fm is not a member of the list Chars (\+ member(Fm,Chars)). Fm is added to Chars in the recursive calls.

Upvotes: 1

Related Questions