How to generate a grid of predicates in Prolog?

Question

I'm trying to create a program in Prolog, but I'm still new to it and not sure what the best approach is to generating a grid-like structure in Prolog.

As an example, say I have the predicate cell/4 that has 4 arguments; North, West, South, and East. What I want to create is a NxN grid of the predicate cell/4 that connects to each other based on their position in the grid.

For example, I can create a 2x2 grid manually. The desired result would be the following:

               North_1                               North_2
                  |                                     |
        +---------+----------+                +---------+----------+
        |       North        |                |       North        |
        |                    | Interconnect_1 |                    |
West_1 -+ West  cell/4  East +----------------+ West  cell/4  East +- East_1
        |                    |                |                    |
        |       South        |                |       South        |
        +---------+----------+                +---------+----------+
                  |                                     |
            Interconnect_2                        Interconnect_3
                  |                                     |
        +---------+----------+                +---------+----------+
        |       North        |                |       North        |
        |                    | Interconnect_4 |                    |
West_2 -+ West  cell/4  East +----------------+ West  cell/4  East +- East_2
        |                    |                |                    |
        |       South        |                |       South        |
        +---------+----------+                +---------+----------+
                  |                                     |
               South_1                               South_2

cell(North, West, South, East) :- % Processing logic.
problem(North_1, North_2, West_1, West_2, South_1, South_2, East_1, East_2) :-
    cell(North_1, West_1, Interconnect_2, Interconnect_1),
    cell(North_2, Interconnect_1, Interconnect_3, East_1),
    cell(Interconnect_2, West_2, South_1, Interconnect_4),
    cell(Interconnect_3, Interconnect_4, South_2, East_2).

So my question is, how can I generalize this process for a NxN grid? I'm sure there can be good ways to handle the arguments of the problem predicate to make it a more general problem(North, West, South, East) where each argument is a List. I'm struggling with generating this kind of grid-like structure though.

Answer 1

Let's say cell(X, Y) represents the grid cell at coordinate X and Y, where X and Y are greater than 0. Now, you can write interesting things about grid cells. For example, you could capture what it means for a cell to be valid.

valid(cell(X, Y)) :- X > 0, Y > 0.

Or capture relations like right_neighbor, left_neighbor, etc.

right_neighbor(cell(X, Y1), cell(X, Y2)) :-
    Y2 is Y1 + 1,
    valid(cell(X, Y1)),
    valid(cell(X, Y2)).

left_neighbor(cell(X, Y1), cell(X, Y2)) :-
    Y1 is Y2 + 1,
    valid(cell(X, Y1)),
    valid(cell(X, Y2)).

You can define the R'th row of a grid that has N columns as follows.

grid_row(R, 1, [cell(R, 1)]) :-
    valid(cell(R, 1)).

grid_row(R, N, [cell(R, N) | Row]) :-
    M is N - 1,
    valid(cell(R, M)),
    grid_row(R, M, Row).

Then it is a simple matter to define a grid of M rows by N columns.

grid(1, N, [Row]) :-
    grid_row(1, N, Row).

grid(M, N, [Row | Rows]) :-
    grid_row(M, N, Row),
    P is M - 1,
    grid(P, N, Rows).

For example, querying for grid(3,2,X). yields:

X = [[cell(3, 2), cell(3, 1)], [cell(2, 2), cell(2, 1)], [cell(1, 2), cell(1, 1)]]

If we use the representation cell(North, West, South, East) where North, West, South and East are the cell connection points to respectively its north, west, south, and east cells, if any, then the solution is similar. We first define the cells of a single row as follows.

problem_row([N], W, [S], E, [cell(N, W, S, E)]).

problem_row([N|Ns], W, [S|Ss], E, [cell(N, W, S, I)|Cs]) :-
    problem_row(Ns, I, Ss, E, Cs).

Querying for problem_row([n1,n2], w1, [s1,s2], e1, R). yields:

R = [cell(n1, w1, s1, _1428), cell(n2, _1428, s2, e1)]

And we define the problem predicate as follows.

problem(Ns, [W], Ss, [E], Cs) :-
    problem_row(Ns, W, Ss, E, Cs).

problem(Ns, [W|Ws], Ss, [E|Es], Cs) :-
    problem_row(Ns, W, Is, E, R),
    problem(Is, Ws, Ss, Es, Rs),
    append(R, Rs, Cs).

Querying for problem([n1,n2], [w1,w2], [s1,s2], [e1,e2], G) yields:

G = [cell(n1, w1, _1460, _1462), cell(n2, _1462, _1476, e1),
     cell(_1460, w2, s1, _1494), cell(_1476, _1494, s2, e2)]

You should note that I have reified your cell predicate as a functor to avoid having to add clauses to the program at runtime, most likely not what you want. Also, note that the grid answer contains unbound variables as you requested in the problem. You could create atoms for them. For example, by concatenating every combination of the north and west atoms.

Answer 2

Here's my solution:

First we set the stage and make some access predicates:

cell(_, _, _, _). % Define the cell

% Access the positions
north(cell(C, _, _, _), C).
south(cell(_, C, _, _), C).
east( cell(_, _, C, _), C).
west( cell(_, _, _, C), C).

Now we need to think what it means to make a connection. There are two directions, so we unify the variables to connect two cells

connect_horizontally(C1, C2) :-
    east(C1, C), west(C2, C). % ltr Unify variables in cells
connect_vertically(C1, C2) :-
    south(C1, C), north(C2, C). % top to bottom

This leads me to think, we can apply this to a whole row or column

connect_row([_|[]]). % Base case is single element
connect_row([H1, H2|T]) :-
    connect_horizontally(H1, H2),
    connect_row([H2|T]).

connect_column([_|[]]).
connect_column([H1, H2|T]) :-
    connect_vertically(H1, H2),
    connect_column([H2|T]).

Thus we can connect all the rows and all the columns. I'm assuming a flat list to represent the grid, we'll declare that soon.

connect_rows(_, []).
connect_rows(RL, Grid) :-
    \+ Grid = [],
    length(Row, RL), % A template row list
    connect_row(Row), % Make the row and connect
    append(Row, Tail, Grid), % The row appended to the tail makes the grid
    connect_rows(RL, Tail). % Recurse with the tail.

connect_cols(N, Grid) :-
    connect_cols(1, N, Grid). % 1 to start from first column
connect_cols(M, M, Grid) :- % This'll be the last column
    get_col(M, M, Grid, Col), 
    connect_column(Col), !.
connect_cols(N, M, Grid) :- 
    get_col(N, M, Grid, Col), % Get column numbered N
    connect_column(Col), % Connect them
    succ(N, O),
    connect_cols(O, M, Grid). % Carry on with the next column

So now we can make a grid by creating a list of suitable length and connecting all the rows and columns.

% to make an N by N Grid
grid(N, Grid) :-
    M is N*N,
    length(Grid, M),
    connect_rows(N, Grid),
    connect_cols(N, Grid).

We still have a utility predicates undeclared: get_col/4. This'll be inelegant...

%! get_col(+Index, +RowWidth, +Grid, -Col)
get_col(N, W, Grid, Col) :-
    N =< W,
    length(Grid, L),
    col_indexes(N, W, L, I), % Get a list of the column indexes for the given width and length of the whole list
    maplist(nth(Grid), I, Col). % Get those cols

% nth is nth1/3 with arguments re-ordered for the sake of maplist
nth(List, N, El) :-
    nth1(N, List, El).

% Indexes is a list of numbers starting from S, incremented by N, up to M.
col_indexes(S, N, M, Indexes) :-
    col_indexes(N, S, M, [S|H]-H, Indexes).
col_indexes(N, A, M, Indexes-[], Indexes) :-
    N + A > M, !.
col_indexes(N, A, M, Acc-[NA|H], Indexes) :-
    NA is N + A,
    col_indexes(N, NA, M, Acc-H, Indexes).

Finally the problem predicate (which needs a size too so that it can generate a grid):

problem(Size, North, South, East, West) :-
    grid(Size, Grid),
    maplist(north, Grid, North),
    maplist(south, Grid, South),
    maplist(east, Grid, East),
    maplist(west, Grid, West).

The other approach I'd try would be to pass a connection predicate over a 2D list of lists that would generate all the connections in a single pass rather than this method which passes over the rows and then columns. This method also has a couple of flags that suggest some inefficiency, such as append/3 in a recursion and the column connection method could be improved. But if you understand it and it works within sufficient time for your use-case, then it'll do the job.

Answer 3

I'm having trouble imagining you'll be happy with cell/4, since you've got four pointers to the other directions, but what's going to be in those cells is just pointers to other cells, which are just pointers to other cells... I think probably you actually want cell/5, which is more like some value plus the pointers in each direction.

In general, if you want a list of size N, you can use length/2 to generate one for you like this:

?- length(L, 3).
L = [_772, _778, _784].

Then you can pass that list of variables around. Presumably you're making a maze or something and you want to pass your grid to some process that's going to place grues and walls or something in it, and that's why you want this grid. My comment above is meant to say that this structure, in an Mx1 arrangement, resembles a doubly-linked list:

            +--------------------+                +--------------------+
            |                    | Interconnect_1 |                    | 
    West_1 -+ West  cell/2  East +----------------+ West  cell/2  East +- East_1
            |                    |                |                    |
            +--------------------+                +--------------------+  

You can build this structure manually in a similar way:

?- West = cell(West_1, East), East = cell(West, East_1).
West = cell(West_1, cell(West, East_1)),
East = cell(West, East_1).

@false correctly points out this will be recursive, since West is equal to some structure with West inside it. I share his misgivings with it because infinite terms present interesting problems, and moreover, usually you can just hold onto the previous value during your traversal and avoid the problem. (In your case, that would be forming a grid with just East and South pointers, I guess, or some other combination of one latitudinal and one longitudinal direction instead of both of each).

In any event, you can build a doubly-linked list by following the example of length/2 and passing in a length you want and constructing one node at a time:

generate(0, Prev, cell(Prev, _)).
generate(N, Prev, cell(Prev, Next)) :-
    succ(N0, N),
    generate(N0, cell(Prev, Next), Next).

Here's the N=3 case:

?- generate(3, Start, X).
X = cell(Start, cell(_S1, cell(_S2, _S3))), % where
    _S1 = cell(Start, cell(_S1, cell(_S2, _S3))),
    _S2 = cell(_S1, cell(_S2, _S3)),
    _S3 = cell(cell(_S2, _S3), _656) 

Again, let me point out that a cons cell in a singly-linked list is going to be something like cell/2 because there's a value and a next pointer, so we probably need to add a value slot to this and return cell/3 structures instead.

So, returning to the grid, what you probably need to do to generate an NxN grid is something akin to generating a row at a time, holding onto the previous row you made each time and passing it to some kind of zip-up process that equates the previous row's South pointers to the current row's North pointers.

I have a solution for the singly-linked grid case here. I hope this turns out to be sufficient for what you need. It was a little tricky to come up with!

First, we will need to be able to generate a row:

generate_row(1, cell(_, nil, _)).
generate_row(N, cell(_, Next, _)) :-
    succ(N0, N),
    generate_row(N0, Next).

The plan here is that we have a cell(Value, NextRight, NextDown) structure. Both NextRight and NextDown are cells, which are the East and South directions in your grid respectively. I am using nil to represent what the empty list does; it terminates our recursion and represents a null pointer. This turns out to be an important thing to have since otherwise my stitch-up procedure will have unbounded recursion.

Now that we have a row, let's worry about how we'll combine an upper and a lower row. All we're really doing here is walking both rows from left to right, equating the NextBelow of the upper one to the cell below it in the second list. This is a little weird to read, but it does work:

stitch(cell(_, NextAbove, Below), Below) :-
    Below = cell(_, NextBelow, _),
    stitch(NextAbove, NextBelow).
stitch(cell(_, nil, Below), Below).

Because we need Below to remain whole, we take it apart in the body rather than the head. I match nil here to terminate the recursion.

Now we have all the pieces we need to generate a whole grid: we will generate a row, recursively generate the rest of the rows, and use stitch/2 to place the new row on top of the recursively generated rows. Now we will also need a secondary parameter so we can count down rows.

generate_rows(2, N, Above) :-
    generate_row(N, Above),
    generate_row(N, Below),
    stitch(Above, Below).
generate_rows(M, N, Grid) :-
    succ(M0, M),
    generate_row(N, Grid),
    generate_rows(M0, N, Below),
    stitch(Grid, Below).

I felt like my base case was a 2xM matrix; it probably could be made to work for 1xM with more careful coding but this is what I came up with.

Running it, it will not be immediately obvious that you have a useful result:

?- generate_rows(3, 3, X).
X = cell(_8940, cell(_8948, cell(_8956, nil, cell(_8980, nil, cell(_9004, nil, _9008))), cell(_8972, cell(_8980, nil, cell(_9004, nil, _9008)), cell(_8996, cell(_9004, nil, _9008), _9000))), cell(_8964, cell(_8972, cell(_8980, nil, cell(_9004, nil, _9008)), cell(_8996, cell(_9004, nil, _9008), _9000)), cell(_8988, cell(_8996, cell(_9004, nil, _9008), _9000), _8992))) ;

However, if you format it, it will start to make sense:

X = cell(_8940,
         cell(_8948,
              cell(_8956,
                   nil,
                   cell(_8980,
                        nil,
                        cell(_9004, nil, _9008))),
              cell(_8972,
                   cell(_8980,
                        nil,
                        cell(_9004, nil, _9008)),
                   cell(_8996, cell(_9004, nil, _9008), _9000))),
         cell(_8964,
              cell(_8972,
                   cell(_8980,
                        nil,
                        cell(_9004, nil, _9008)),
                   cell(_8996, cell(_9004, nil, _9008), _9000)),
              cell(_8988,
                   cell(_8996,
                        cell(_9004, nil, _9008),
                        _9000),
                   _8992))) ;

OK, read all the variables in the first position until you are indented as far as you can go. Then read them in the first position from the second-leftmost cell, and repeat. You should get a table of 3x3 variables:

_8940 _8948 _8956
_8964 _8972 _8980
_8988 _8996 _9004

Now looking at that table, you should notice that _8940 should have two children: 8948 (East) and 8964 (South), and it does. You'll notice that 8972 should have two children: 8980 (East) and 8996 (South), and it does. There is a lot of repetition in the tree, but it is consistent.

Anyway, this isn't exactly a solution to your question. But I hope it is helpful to you. If you do still decide to doubly-link it, you will have to generalize this solution the way the doubly-linked list is generalized from length/2. Hopefully, there is enough here for you to see what you'd have to do if you decide you have to do that, but this is as far as I am willing to take it for now.