Prolog Shortest Path using list of lists

Question

Okay, so I've been trying to teach myself Prolog recently, and am having a hard time wrapping my head around finding a "Shortest Path" between two (defined) elements in a list of lists. It may not be the most effective way of representing a Grid or finding a Shortest Path, but I'd like to try it this way.

For example:

[[x,x,x,x,x,x,x],
 [x,1,o,o,o,o,x],
 [x,-,-,-,o,-,x],
 [x,-,-,o,o,-,x],
 [x,o,o,o,o,2,x],
 [x,o,-,-,o,o,x],
 [x,x,x,x,x,x,x]]

A few assumptions I can make (either given or based on checking before path-finding):

• The grid is square
• Their will always exist a path from 1 to 2
• '1' can pass through anything except '-' (walls) or 'x' (borders)

The goal is for '1' to find a shortest path to '2'.

In the instance of:

[[x,x,x,x,x,x,x],
 [x,o,o,1,o,o,x],
 [x,-,o,o,o,-,x],
 [x,-,o,-,o,-,x],
 [x,o,o,2,o,o,x],
 [x,o,-,-,-,o,x],
 [x,x,x,x,x,x,x]]

Notice, there are two "Shortest paths":

[d,l,d,d,r]

and

[d,r,d,d,l]

In Prolog, I'm trying to make the function (if that's the proper name):

shortestPath(Grid,Path)

I've made a function to find elements '1' and '2', and a function that verifies that the grid is valid, but I can't even begin how to start constructing a function to find a shortest path from '1' to '2'.

Given a defined Grid, I'd like the output of Path to be the shortest path. Or, given a defined Grid AND a defined Path, I'd like to check if it's indeed a shortest path.

Help would be much appreciated! If I missed anything, or was unclear, let me know!

Answer 1

not optimized solution

shortestPath(G, S) :-
    findall(L-P, (findPath(G,P), length(P,L)), All),
    keysort(All, [_-S|_]).

findPath(G, Path) :-
    pos(G, (Rs,Cs), 1),
    findPath(G, [(Rs,Cs)], [], Path).

findPath(G, [Act|Rest], Trail, Path) :-
    move(Act,Next,Move),
    pos(G, Next, Elem),
    (   Elem == 2
    ->  reverse([Move|Trail], Path)
    ;   Elem == o
    ->  \+ memberchk(Next, Rest),
        findPath(G, [Next,Act|Rest], [Move|Trail], Path)
    ).

move((R,C), (R1,C1), M) :-
    R1 is R-1, C1 is C  , M = u;
    R1 is R  , C1 is C-1, M = l;
    R1 is R+1, C1 is C  , M = d;
    R1 is R  , C1 is C+1, M = r.

pos(G, (R,C), E) :- nth1(R, G, Row), nth1(C, Row, E).

grid(1,
[[x,x,x,x,x,x,x],
 [x,1,o,o,o,o,x],
 [x,-,-,-,o,-,x],
 [x,-,-,o,o,-,x],
 [x,o,o,o,o,2,x],
 [x,o,-,-,o,o,x],
 [x,x,x,x,x,x,x]]).

grid(2,
[[x,x,x,x,x,x,x],
 [x,o,o,1,o,o,x],
 [x,-,o,o,o,-,x],
 [x,-,o,-,o,-,x],
 [x,o,o,2,o,o,x],
 [x,o,-,-,-,o,x],
 [x,x,x,x,x,x,x]]).