Maze Solver DFS Algorithm

Question

I'm studying prolog in a course. I have an exercise where I need to read a file, generate a maze from it, get a path from the source to destination and write it to a file.

I read the file and I assert square(CoordX, CoordY) for each cell I have, and connect(X, Y) for each two cells that are connected.

TargetX, TargetY, SourceX, SourceY are all integer coordinates so I know the start point and destination point.

The rationale I worked by is, If current node is connected to target, finish and return. else, find a node that current node is connected to and call recursion with the new node

solveFirst(TargetX, TargetY, SourceX, SourceY, T):-
    connects(square(SourceX, SourceY), NewSquare),
    solve(TargetX, TargetY, SourceX, SourceY, NewSquare, T2),
    T = T2.

solve(TargetX, TargetY, SourceX, SourceY, NewSquare ,[Tail]):-
    getFirst(Tail, HeadOfTail),
    (
    connects(NewSquare, square(TargetX, TargetY)), 
    addFirst(NewSquare, Tail, T2),
    Tail = T2 ;
    connects(NewSquare, E),
    solve(TargetX, TargetY, SourceX, SourceY, E, Tail)
    ).

Answer 1

I've modified your rules in this way

solve(TargetX, TargetY, _, _, NewSquare, [NewSquare]) :-
  connects(NewSquare, square(TargetX, TargetY)).

solve(TargetX, TargetY, SourceX, SourceY, NewSquare, [E | Tail]) :-
  connects(NewSquare, E),
  solve(TargetX, TargetY, SourceX, SourceY, E, Tail).

solveFirst(TargetX, TargetY, SourceX, SourceY, [NewSquare | T]):-
  connects(square(SourceX, SourceY), NewSquare),
  solve(TargetX, TargetY, SourceX, SourceY, NewSquare, T).

and, with the following facts

square(1, 1).  square(1, 2).  square(1, 3).
square(2, 1).  square(2, 2).  square(2, 3).
square(3, 1).  square(3, 2).  square(3, 3).

connects(square(1, 1), square(1, 2)).
connects(square(1, 1), square(2, 1)).
connects(square(1, 2), square(1, 3)).
connects(square(1, 2), square(2, 2)).
connects(square(2, 1), square(2, 2)).
connects(square(2, 2), square(3, 2)).
connects(square(3, 2), square(3, 3)).

calling solveFirst(3, 3, 1, 1, L), I get (in L) the following paths

[square(1,2),square(2,2),square(3,2),square(3,2)]
[square(2,1),square(2,2),square(3,2),square(3,2)]

But this work because there aren't loops. If you add the following connection

connects(square(2, 2), square(1, 2)).

so you can loop ((1,2) -> (2,2) -> (1,2) -> (2,2) ...) and from solveFirst(3, 3, 1, 1, L) I get a stack overflow.

To avoid this problem, you can remember the visited squares and avoid to use them again.

I've written the following example but consider that

(1) I've switched start and target (start first, target second)

(2) I've added start and target in the resulting path

(3) I'm using gprolog so I don't have not/1; I've used \+ member.... instead

getPath(Tx, Ty, Tx, Ty, _, [square(Tx, Ty)]).

getPath(Sx, Sy, Tx, Ty, Visited, [square(Sx, Sy) | Path]) :-
  connects(square(Sx, Sy), square(Nx, Ny)),
  \+ member(square(Nx, Ny), Visited), % or not(member(square(Nx, Ny), Visited)
  getPath(Nx, Ny, Tx, Ty, [square(Nx, Ny) | Visited], Path).

getPath(Sx, Sy, Tx, Ty, Path) :-
  getPath(Sx, Sy, Tx, Ty, [square(Sx, Sy)], Path).

Using the following facts

square(1, 1).  square(1, 2).  square(1, 3).
square(2, 1).  square(2, 2).  square(2, 3).
square(3, 1).  square(3, 2).  square(3, 3).

connects(square(1, 1), square(1, 2)).
connects(square(1, 1), square(2, 1)).
connects(square(1, 2), square(1, 3)).
connects(square(1, 2), square(2, 2)).
connects(square(2, 2), square(1, 2)).
connects(square(2, 1), square(2, 2)).
connects(square(2, 2), square(3, 2)).
connects(square(3, 2), square(3, 3)).

from getPath(1, 1, 3, 3, L) I get the following paths

[square(1,1),square(1,2),square(2,2),square(3,2),square(3,3)]
[square(1,1),square(2,1),square(2,2),square(3,2),square(3,3)]

--- EDIT ---

As suggested by Mat in a comment (thanks!), instead of \+ member(square(Nx, Ny), Visited) (or not(member(square(Nx, Ny), Visited)) you could write (if your prolog environment support maplist/2)

maplist(dif(square(Nx,Ny)), Visited)

to impose that square(Nx, Ny) isn't in the Visited list.

This solution is more general because (if I understand correctly) the unification works in both directions.

Answer 2

Your rationale seems valid. The only thing left for you to do is to implement it correctly.

First, a general comment about your code:

When you see a goal like:

T = T2

ask yourself: Why did you introduce T2 at all? You can simply use T instead, since these are the same term if this goal succeeds.

This pattern arises twice in your program.

Another issue: Never put ; at the end of a line It looks too similar to ,.

So, after these changes, your solve/6 looks like this:

solve(TargetX, TargetY, SourceX, SourceY, NewSquare, [Tail]):-
    getFirst(Tail, HeadOfTail),
    (   connects(NewSquare, square(TargetX, TargetY)),
        addFirst(NewSquare, Tail, Tail)
    ;   connects(NewSquare, E),
        solve(TargetX, TargetY, SourceX, SourceY, E, Tail)
    ).

Now ask yourself: Does this even make sense? In particular, can addFirst(NewSquare, Tail, Tail) ever succeed? It's kind of hard to tell for us, since you have omitted its definition.

Also, when you compile this, you get a warning:

Singleton variables: [HeadOfTail]

So why did you even introduce this variable?

Conceptually, the following pattern may help you:

path(Current, Target, Path) :-
    (   connects(Current, Target),
        Path = [Current]
    ;   connects(Current, Next),
        Path = [Current|Ps],
        path(Next, Target, Ps)
    ).