Prolog program to find path list of 'right' and 'up' moves across a 10X10 grid

Question

I have not programmed in prolog, or any other logical programming language, much and I'm trying to get the hang of it, so I am working on an Exercise I found.

The Exercise is: You have a 10X10 grid, and you can only move right or up from a location point in the grid (locations represented as a list with 2 elements [2, 3] where 2 is on the x-axis and 3 is on the y-axis, like a regular graph).

The first step is to define the 2 predicates called step that describe the two types of moves you can make.

Here are the correct step predicates:

step([D1, D2], 'right', [Z, D2]) :- Z is D1 + 1.
step([D1, D2], 'up', [D1, Z]) :- Z is D2 + 1.

With the step predicates above, Let's give an example query below:

step([4, 4], 'up', [4, X]).

This example Query above would return the output below:

X = 5.

The next step is to define a path predicate that is recursive and uses the step predicate to determine the path(s) (represented by a list of steps 'up' or 'right' like ['up', 'up', 'right', 'right']) that should be taken to reach the end point location of the 10X10 grid [10, 10].

Below is an example Query of how this path predicate would give proper output bindings for list of steps.

path([4,4],X).

This example query above should return all the possible bindings of X as a list of steps taken to reach [10, 10]. For example is should return something like X = ['up', 'up', 'up', 'up', 'up', 'up', 'right', 'right', 'right', 'right', 'right', 'right'].

So, I tried to write path predicates to serve this function and I don't understand why my predicate code below is not working and always gives errors. Here is my attempt.

path([StartX, StartY], [Move|Rest]) :- StartX =< 8, StartY =< 8, step([StartX, StartY], Move, [NextX, NextY]), path([NextX, NextY], Rest).

If anyone could explain how I should go about this that would be killer!

Also, there is a final step that is to assume that blockages exist at the Grid points implement blockages: (4,1), (4,2), (6,3), (1,2), (7,6) so that you cannot step pass these blocked spots. The Final step is to write predicates that model these blockages.

TA_intern TA_intern · Accepted Answer · 2020-12-02T07:58:59

With a very small re-write to make it easier, here is your program that finds paths:

step(right, X, Y, X1, Y) :- succ(X, X1), between(1, 10, X1).
step(up, X, Y, X, Y1) :- succ(Y, Y1), between(1, 10, Y1).

path(X, Y, X, Y, []) :- !.
path(X0, Y0, X, Y, [Step|Path]) :-
    step(Step, X0, Y0, X1, Y1),
    path(X1, Y1, X, Y, Path).

It only checks the new position on the grid, it assumes the current position is valid.

You can use it to find all paths between two points, for example starting at 7,9 and going to 10, 10:

?- path(7, 9, 10, 10, P).
P = [right, right, right, up] ;
P = [right, right, up, right] ;
P = [right, up, right, right] ;
P = [up, right, right, right] ;
false.

You can add "blocked" positions on the grid in several ways. Do you want them "permanently" on the field or do you want to give them to the path algorithm at run-time? At run-time, with this definition of "path" ("step" is unchanged):

path(X, Y, X, Y, _, []) :- !.
path(X0, Y0, X, Y, Blocked, [Step|Path]) :-
    step(Step, X0, Y0, X1, Y1),
    \+ memberchk(X1-Y1, Blocked),
    path(X1, Y1, X, Y, Blocked, Path).

You can now list the blocked positions in the fifth argument.

?- path(7, 9, 10, 10, [7-10, 9-10], P).
P = [right, right, right, up] ;
false.

?- path(7, 9, 10, 10, [7-10, 10-9], P).
P = [right, right, up, right] ;
P = [right, up, right, right] ;
false.

Prolog program to find path list of 'right' and 'up' moves across a 10X10 grid

1 Answers