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
?- 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
Better edit your question and add that sample call there properly formatted. — Paulo Moura
Your second clause of path/5 is still wrong, as I pointed out in my answer. — Paulo Moura

Paulo Moura Paulo Moura · Accepted Answer · 2019-01-07T19:00:18

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.

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

2 Answers