How to generate a list of available steps on a grid?

Question

I have a 5x5 grid which is described by max_size(5, 5). I need to generate a list of all cells from that description using DCG.

Here's the code I have so far:

:- use_module(library(clpfd)).

map_size(5, 5).

natnum(0).
natnum(X) :-
    X #= X0 + 1,
    natnum(X0).

list_all_cells(Visited) -->
    { length(Visited, 25) },
    []. 
list_all_cells(Visited) -->
    [X-Y],
    { map_size(X_max, Y_max),
      natnum(X), natnum(Y),
      X #< X_max, Y #< Y_max,
      maplist(dif(X-Y), Visited) },
    list_all_cells([X-Y|Visited]).

However, it doesn't generate a list and outputs only 4 pairs.

A possible query to the DCG looks like list_all_cells([]) which is supposed to list all cells on the grid. For example, it's gonna be [0-0, 1-0, 1-1, 0-1] for a 2x2 grid (order doesn't matter).

In fact, I need this predicate to build another one called available_steps/2 that would generate a list of all possible moves for a given position. Having available_steps(CurrentPos, Visited), I will be able to brute-force Hunt the Wumpus game and find all possible routes to gold.

Guy Coder · Accepted Answer · 2019-03-10T23:18:07.220

1

list_all_cells(Cells) :-
    bagof(C,cell(C),Cells).

cell(X-Y) :-
    between(0,4,X),
    between(0,4,Y).

Example run:

?- list_all_cells(Cells); true.
Cells= [0-0, 0-1, 0-2, 0-3, 0-4, 1-0, 1-1, 1-2, ... - ...|...] [write]  % The letter w was pressed.
Cells= [0-0, 0-1, 0-2, 0-3, 0-4, 1-0, 1-1, 1-2, 1-3, 1-4, 2-0, 2-1, 2-2, 2-3, 2-4, 3-0, 3-1, 3-2, 3-3, 3-4, 4-0, 4-1, 4-2, 4-3, 4-4] ;
true.

edited Mar 10 '19 at 23:18

answered Mar 10 '19 at 12:39

Guy Coder

24,501
8
71
136

Why do we have `true` in the goal? – Radical Ed Mar 10 '19 at 13:01
1

@RadicalEd adding `;true` to the goal is used to force SWI-Prolog to prompt for user input before returning, so that `w` can be entered to show the entire answer. Without `;true`, the answer is returned with `...` and then ends. I did this to show you that all 25 values are in the list. When you use this in your code, `; true` is not needed. See: [SWI-Prolog how to show entire answer (list)?](https://stackoverflow.com/q/32910541/1243762). I am leaving this as a comment because it is not really part of the answer and something that any good Prolog programmer should know when starting. – Guy Coder Mar 10 '19 at 13:03
Why not `cell(X-Y)`? – repeat Mar 10 '19 at 14:37
@repeat Thx, again. Fixed. Yes it should be `cell(X-Y).` I have been doing DCGs for the last few weeks returning structures without names and thus using `functor((parm1,pam2,...)).`. Didn't even notice I did it. – Guy Coder Mar 10 '19 at 23:20
These extra parentheses can make a difference, sometimes they are necessary, sometimes they are a minor problem. Consider the compound term `f((a,b,c,d))`: that is not `f/4`, but `f/1` with a (defaulty) "comma list" inside: `(a,b,c,d) == (a,(b,(c,d)))`, which takes more memory than a compound of arity 4 and is also slower to access (as it is a tree, not flat). HTH – repeat Mar 11 '19 at 08:02
So these structures *do* have a name: `(,)/2`. – repeat Mar 11 '19 at 08:04
@repeat Thx. Never considered `(,)/2` a name, will have to look into it more or ask a question to better comprehend it. – Guy Coder Mar 11 '19 at 10:05

How to generate a list of available steps on a grid?

1 Answers1