Prolog maze problem : code gives infinite paths from start to end and doesn't backtrack

Question

I am trying to solve a maze in Prolog using backtracking.

My problem is that when I run the program, it runs correctly for the first time, but after that it takes the end position as the starting position and keeps finding paths from there, hence goes into endless loop. It works correctly when path doesn't exist between 2 positions. I have tried lots of things but nothing seems to be working. Here's my code:

path(Dest, Dest, _, [], _) :- !.

path([Row0,Col0],[Row1,Col1],M,Path,1) :-
    next_move([Row0,Col0],[Rnew,Cnew]),
    is_available(Rnew, Cnew,Ret),

    write(Rnew),
    write(Cnew),

    not(member([Rnew, Cnew], M)),
    path([Rnew, Cnew], [Row1, Col1], [[Rnew,Cnew]|M], Path, Ret).

path([X0,Y0], [X1,Y1], [[X0,Y0]|M], [[X,Y]|Path], 0) :-
    path([X,Y],[X1,Y1],M,Path,1).

Sample output:

?- solves([1,1],[1,7],P).
P = [[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7]] ;
P = [[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 6], [2, 7], [2|...], 
    [...|...]|...] ;
P = [[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 6], [2, 7], [2|...], 
    [...|...]|...] ;
P = [[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 6], [2, 7], [2|...], 
    [...|...]|...] .

When executing the program, it should display all the paths if a path exists between 2 positions. It should return false otherwise. As you can see above, my code goes into infinite loop and keep generating paths.

Please help as I am not very experienced in Prolog. Thanks.

How are you calling `path/5`? I am not sure what your failing query looks like. — Daniel Lyons, Jan 07 '19 at 18:17
?- solves([1,1],[3,3],P). P = [[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [3|...]] ; P = [[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 7], [2|...], [...|...]|...] ; P = [[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 7], [2|...], [...|...]|...] ; P = [[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 7], [2|...], [...|...]|...] ; As you can see, it keeps giving paths till you press ;. Also it only displays upto 7 nodes properly. After that it displays incomplete values like [2|...] or [...|...] . — Hash, Jan 07 '19 at 23:24
Better edit your question and add that sample call there properly formatted. — Paulo Moura, Jan 07 '19 at 23:36
Your second clause of `path/5` is still wrong, as I pointed out in my answer. — Paulo Moura, Jan 12 '19 at 10:30

Paulo Moura · Answer 1 · 2019-01-12T10:31:01.247

1

The first clause of the path/5 predicate and the recursive call in its second clause are wrong. It should be:

path(Dest, Dest, _, [], _) :- !.

path([Row0,Col0],[Row1,Col1],M,[[Rnew,Cnew]|Path],1) :-
    next_move([Row0,Col0],[Rnew,Cnew]),
    is_available(Rnew, Cnew,Ret),

    write(Rnew),
    write(Cnew),

    \+ member([Rnew, Cnew], M),
    path([Rnew, Cnew], [Row1, Col1], [[Rnew,Cnew]|M], Path, Ret).

Also, use the ISO Prolog standard \+/1 predicate instead of the not/1 legacy predicate.

edited Jan 12 '19 at 10:31

answered Jan 07 '19 at 19:00

Paulo Moura

18,373
3
23
33

1

I also find the `Ret =:= 1` thing weird, why not just specify 1 or 0 in the head? – Daniel Lyons Jan 07 '19 at 23:02
Thanks for replying Paulo. You were right about Ret =:= 1. I made the changes but the code still doesn't work. I have realized that my program isn't backtracking properly .Any thoughts on that? If it helps, here is the code for my is_available function :- is_available(Row,Col,Ret) :- mazeSize(Rows, Cols), \+barrier(Row,Col), Row >= 1, Row =< Rows, Col >= 1, Col =< Cols, Ret is 1. is_available(X,Y,Ret) :- barrier(X,Y), Ret is 0. – Hash Jan 07 '19 at 23:20
1

Better edit your question and add that code there properly formatted. – Paulo Moura Jan 07 '19 at 23:35

score 0 · Answer 2 · answered Jan 12 '19 at 00:17

Ha there's a fair amount of irony here that I even saw this post - you are on the PPL course? :)

Generally returning a value of 0 or 1 to say whether a statement is true or false is not necessary in prolog - it is implicit in whether the predicate has passed.

For example is_available(Rnew, Cnew,Ret) would be better written as is_available(Rnew, Cnew) - if is_available resolves as false then it would already STOP and begin to backtrack to look for other solutions along its alternate lines if there was no alternative.

Furthermore this will mean that if there is no solution, a value of 'false' would be printed when you try to evaluate the maze.

On your output issues - actually that is not 'broken'; it is just suppressed output! Try running this in your swi terminal before you run the maze solving expression:

set_prolog_flag(answer_write_options,[max_depth(0)]).

as per SWI-Prolog how to show entire answer (list)?

Thanks Alex! I have been stuck on this thing for like forever. The first version of the program I wrote, was without return , but because of the same issues with output, I thought threre's some problem with my code and have been trying different approaches ever since. Now that the output issue has been solved, I will see if I can find my first version of the program. — Hash, Jan 12 '19 at 15:19
No worries, let me know if you are having difficulties still and we can have a chat through your solution one evening at BBK. — Alex, Jan 12 '19 at 22:55

Prolog maze problem : code gives infinite paths from start to end and doesn't backtrack

2 Answers2