Write a Prolog program to model a gorilla moving across a grid

Question

I have done very little programming in Prolog and find it quite difficult so far.

I was given the question: A gorilla moves along an 8x8 grid and can only move right or up. it has to remain within the grid and must finish at (8,8) starting at any arbitrary location.

Write a move predicate that describes all the possible moves.

My attempt:

move(X,Y,X+1,Y).
move(X,Y,X,Y+1).

Write a path predicate that uses the move predicate to determine the path thte robot shuld take.

My attempt:

path('right'):-
    move(X,Y,X+1,Y).
path('up'):-
    move(X,Y,X,Y+1).

Write prolog predicates that model blockages at (1,2), (4,2), and (4,1).

So far, from what I have found it seems I need to set up a list that would give all possible positions.

I have written a list of the possible positions but do not understand how to implement it:

[(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),
 (2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),
 (3,1),(3,2),(3,3),(3,4),(3,5),(3,6),(3,7),(3,8),
 (4,1),(4,2),(4,3),(4,4),(4,5),(4,6),(4,7),(4,8),
 (5,1),(5,2),(5,3),(5,4),(5,5),(5,6),(5,7),(5,8),
 (6,1),(6,2),(6,3),(6,4),(6,5),(6,6),(6,7),(6,8),
 (7,1),(7,2),(7,3),(7,4),(7,5),(7,6),(7,7),(7,8),
 (8,1),(8,2),(8,3),(8,4),(8,5),(8,6),(8,7),(8,8)]

This seems like it would be a simple program but I cannot seem to grasp the concepts or at least put them all together into a workable program.

Any help in direction would be greatly appreciated.

Answer 1

There are quite some issues with your code. Let's go through it one at a time.

1. Possible positions

Although your list of possible positions is OK, I wouldn't hard-code it like that. It's very easy to do a check if a position is on the grid:

grid_position(X, Y) :- 
    X >= 1,
    X =< 8,
    Y >= 1,
    Y =< 8.

Do note that this can only be used to verify a given position. If you want to be able to generate all possible positions, you can use in/2 from library(clpfd).

2. Allowed positions

If there is no simple logic as above for positions that are blocked, there is no other way than to enumerate them yourself.

blocked(1, 2).
blocked(4, 2).
blocked(4, 1).

Using this, we can determine which are the allowed positions for our gorilla: any position that is on the grid, but is not blocked.

allowed_position(X, Y) :-
    grid_position(X, Y),
    \+blocked(X, Y).

3. move

The main problem here is that writing X+1 in the head of the clause doesn't do what you think it does. To evaluate arithmetic expressions, you need to use the is predicate.

Additionally, I would only allow a move if the next location is allowed. Since the gorilla is already at the current location, I don't include a check to see if this location is actually allowed.

move(X, Y, X2, Y) :- 
    X2 is X + 1, 
    allowed_position(X2, Y).
move(X, Y, X, Y2) :- 
    Y2 is Y + 1, 
    allowed_position(X, Y2).

4. path

Here's how I interpret the requirement: given a start position, return the list of moves used to reach the end position.

To do this, we're going to need 3 arguments: the X and Y positions, and the output. The output here will be a list of positions rather than a list of moves, I'll leave it up to you to change that if needed.

So what makes up our path? Well, first you make one move, and then you find the rest of the path from the next position.

path(X, Y, [(X,Y)|Ps]) :- 
    move(X, Y, X2, Y2), 
    path(X1, Y1, Ps).

Of course we have to make sure this ends at the target position, so for base case we can use:

path(8, 8, (8, 8)).

You may also want to verify that the initial position is an allowed position, which I have left out.

---

Combine everything, and you get output such as below.

?- path(5,6,L).        
L = [(5,6),(6,6),(7,6),(8,6),(8,7)|(8,8)] ? ;
L = [(5,6),(6,6),(7,6),(7,7),(8,7)|(8,8)] ? ;
L = [(5,6),(6,6),(7,6),(7,7),(7,8)|(8,8)] ? ; 
...

This may not be exactly what you're looking for, but I hope it helps you well on the way.

Answer 2

So you might want to say where you are moving while you're doing that. So I'll suggest a predicate move/3 like this:

% move(From_Position, To_Position, Direction).

move((X,Y),(X,Y1), up)   :- 
    grid(G), 
    member((X,Y1),G),
    Y1 is Y + 1.
move((X,Y),(X1,Y), rigth):- 
    grid(G), 
    member((X1,Y),G),
    X1 is X + 1.

The grid calls are there to ensure that you'll always stay on the grid. you also could use a smarter predicate in_grid and avoid the member call (which is quite time consuming).

grid([(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),
 (2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),
 (3,1),(3,2),(3,3),(3,4),(3,5),(3,6),(3,7),(3,8),
 (4,1),(4,2),(4,3),(4,4),(4,5),(4,6),(4,7),(4,8),
 (5,1),(5,2),(5,3),(5,4),(5,5),(5,6),(5,7),(5,8),
 (6,1),(6,2),(6,3),(6,4),(6,5),(6,6),(6,7),(6,8),
 (7,1),(7,2),(7,3),(7,4),(7,5),(7,6),(7,7),(7,8),
 (8,1),(8,2),(8,3),(8,4),(8,5),(8,6),(8,7),(8,8)]).

A path should probably be a list of directions:

path((8,8), []).
path(Position, [Direction| Before]):-
    \+ Position = (8,8),
    move(Position, NewPosition, Direction),
    path(NewPosition,Before).

To Accumulate, you can use bagof or setof

all_paths(Position,Paths):-
    setof(Path,path(Position,Path),Paths).