1

Is there any way to prevent cycle in this code.

move(a,b).
move(b,a).
move(a,c).
move(b,d).
move(b,e).
move(d,h).
move(d,i).
move(e,j).
move(e,k).
move(c,f).
move(c,g).
move(f,l).
move(f,m).
move(g,n).
move(g,o).
goal(n).


goSolveTheMaze(Start,Way) :-
    dfs(Start, Way),!.

dfs(Goal, [Goal]) :-
   goal(Goal),!.

dfs(Start, [Start|Way])  :-
    move(Start, N),
    dfs(N, Way).

so when move(a,b) move to (b,c) dont go back to (b,a), when run goSolveTheMaze(a,path). The output should be path=[a,c,g,n].

desertnaut
  • 57,590
  • 26
  • 140
  • 166
zead seam
  • 31
  • 5

1 Answers1

1

What if you add a third argument to dfs which is a list of where you've already visited? You could then use \+/1 and member/2 to avoid returning to places you've already been.

For example, if you use the following:

move(a,b).
move(b,a).
move(a,c).
move(b,d).
move(b,e).
move(d,h).
move(d,i).
move(e,j).
move(e,k).
move(c,f).
move(c,g).
move(f,l).
move(f,m).
move(g,n).
move(g,o).
goal(n).


goSolveTheMaze(Start,Way) :-
    dfs(Start, Way, [Start]),!.

dfs(Goal, [Goal], _) :-
   goal(Goal),!.

dfs(Start, [Start|Way], Visited)  :-
    move(Start, N),
    \+ member(N, Visited),
    dfs(N, Way, [N|Visited]).

Then the query:

?- goSolveTheMaze(a, X).

Will produce the result:

X = [a, c, g, n]

Update in response to comment "can you tell me what \+ do?":

The \+ predicate is true when its argument cannot be proven. Therefore in the above example the line \+ member(N, Visited) means "when N is not a member of the list Visited".

See: https://www.swi-prolog.org/pldoc/man?predicate=%5C%2B/1

14241354
  • 156
  • 4