prolog - 如何在 Prolog 中生成谓词网格？

Question

我正在尝试在 Prolog 中创建一个程序，但我仍然是新手，不确定在 Prolog 中生成类网格结构的最佳方法是什么。

举个例子，假设我有一个有 4 个参数的谓词 cell/4； 北、西、南和东。我想要创建的是谓词 cell/4 的 NxN 网格，该网格根据它们在网格中的位置相互连接。

例如，我可以手动创建一个 2x2 网格。期望的结果如下:

               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).

所以我的问题是，如何将此过程概括为 NxN 网格？我确信可以有很好的方法来处理 problem 谓词的参数，使其成为更通用的 problem(North, West, South, East) 其中每个参数是一个列表。不过，我正在努力生成这种类似网格的结构。

Answer 1

这是我的解决方案:

首先我们设置舞台并制作一些访问谓词:

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

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

现在我们需要思考建立联系意味着什么。有两个方向，所以我们统一变量来连接两个cell

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

这让我想到，我们可以将其应用于整行或整列

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]).

因此我们可以连接所有的行和所有的列。我假设一个简单的列表来表示网格，我们很快就会宣布。

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

所以现在我们可以通过创建一个合适长度的列表并连接来制作一个网格所有的行和列。

% 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).

我们还有一个未声明的实用谓词:get_col/4。这将是不优雅的...

%! 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).

最后是问题谓词(它也需要一个大小，以便它可以生成网格):

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).

我尝试的另一种方法是通过一个二维列表列表传递一个连接谓词，这将在一次传递中生成所有连接，而不是这种先传递行然后传递列的方法。此方法还有一些标志表明效率低下，例如递归中的 append/3 并且可以改进列连接方法。但是，如果您了解它并且它在足够的时间内为您的用例工作，那么它就能完成工作。