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!

Nuuou, please do not try to change answers given. If you have your own post to add, add an additional answer, but do not deface or wipe out the answer @CapelliC has posted — Dave Alperovich

CapelliC CapelliC · Accepted Answer · 2013-12-03T06:47:10

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]]).

Prolog Shortest Path using list of lists

1 Answers