Search code examples
prologpredicatemaze

Moving within a list, by giving the possible moves. Prolog


So I recently started to learn Prolog and I had a question regarding making a predicate which gives u all the possible solutions (next moves) as the current spot is given. The best example is a maze. So this is my data which tells me 'w = white' and 'b = black' within a 5x5 maze:

grid([ [w, w, w, b, w],
    [b ,b, w, w, w],
    [w, w, w, b, w],
    [w, b, b, b, b],
    [w, w, w, w, w] ]). 

I also implemented a predicated called white/1, which tells me if the given spot in the maze is white:

white(X/Y) :-
    grid(M),
    nth1(X, M, Line),
    nth1(Y, Line, w).

What I now want to do is make a predicate that gives me all the possible moves within the maze. For example if I query:

?- move(5/2, NextState).
NextState = 4/2 ;
NextState = 5/1 ;
NextState = 5/3 ;
No

This is my code, but it gives false and I know it's completely wrong, but I don't know how to implement such a predicate:

move(5/5, _).

move(X/Y, NextState) :-
    white(X/Y),
    X1 is X + 1,
    X1 =< 5,
    move(X1/Y, NextState),
    Y1 is Y + 1,
    Y1 =< 5,
    move(X/Y1, NextState),
    X2 is X - 1,
    X2 >= 5,
    move(X2/Y, NextState),
    Y2 is Y - 1,
    Y2 >= 0,
    move(X/Y2, NextState).

If someone could help me, I would really appreciate it! :)

EDIT:

move(X/Y, _) :-
    white(X/Y).

move(X/Y, X/Y) :-
    X1 is X + 1,
    move(X/Y, X1/Y);
    X2 is X - 1,
    move(X/Y, X2/Y);
    Y1 is Y + 1,
    move(X/Y, X/Y1);
    Y2 is Y - 1,
    move(X/Y, X/Y2).

If I query it gives me:

?- move(3/3, NextState).
true ;
NextState = 3/3 ;
NextState = 3/3 ;
NextState = 3/3 ;
NextState = 3/3 ;

Solution

  • move(X/Y, X1/Y1, Xm/Ym) :-
        X1 is X + 1, Y1 = Y, X1 =< Xm;
        X1 is X - 1, Y1 = Y, X1 > 0;
        X1 = X, Y1 is Y + 1, Y1 =< Ym;
        X1 = X, Y1 is Y - 1, Y1 > 0.
    

    For each line in the above predicate we have a new direction. The Xm/Ym are bounds of the maze.

    | ?- move(5/2, X, 5/5).
    
    X = 4/2 ? ;
    
    X = 5/3 ? ;
    
    X = 5/1
    
    yes
    

    You can remove Xm/Ym as an argument and just put 5 in the body. Or you can define a new predicate

    move1(Current, Next) :- move(Current, Next, 5/5)
    

    Instead of disjunctions, we can also write multiple clauses.

    move(X/Y, X1/Y) :- X1 is X + 1, X1 =< 5.
    move(X/Y, X1/Y) :- X1 is X - 1, X1 > 0.
    move(X/Y, X/Y1) :- Y1 is Y + 1, Y1 =< 5.
    move(X/Y, X/Y1) :- Y1 is Y - 1, Y1 > 0.
    

    Both are equivalent and this is even clearer.