Prolog predicate to traverse a grid

Question

Consider the following predicate: path(Start, End, Size, Path)

Start is a cell in the grid identified by the list [row, column]. End is a cell in the grid identified by the list [row, column]. Size is the list giving the maximum row and column values. Path consists of a list of adjacent cells, where adjacent is left/right and up/down. A path has no loops; i.e. a cell can only occur once in the list.

With the following query: path([1,1], [4,4], [4,4], Path]. A valid path would be: [[1,1], [1,2], [1,3], [1,4], [2,4], [2,3], [3,3], [3,4], [4,4)].

How would you solve this?

well, it seems pretty easy, from the start position move to the left or right until you reach the destination column; then move up or down until you reach the destination row and you are done. — salva

NotAUser NotAUser · Accepted Answer · 2013-10-07T10:07:29

Here's a start. First define path.

path(X,Y,[X,Y]):- edge(X,Y).
path(X,Y,[X|Xs]):- edge(X,W), path(W,Y,Xs).

Then define edge:

edge([X,Y], [X1,Y]) :- X1 is X + 1.
edge([X,Y], [X,Y1]) :- Y1 is Y + 1.

Now your predicate:

grid_path(START, END, LIMIT, SOLUTION) :-
    within_limit(END, LIMIT),
    path(START,END, SOLUTION).

I don't want to spoil the fun, so I'll leave it for you. This solution just generates all the possible candidates and it's highly inefficient. You can play around and optimise the search.

Prolog predicate to traverse a grid

1 Answers