为解谜程序序言程序生成矩阵

Question

我编写了一个 prolog 程序来解决和显示类似数独的谜题的解决方案。起初我使用这样的东西，如果网格是例如4x4:

main:-
     Matrix = [[_,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]],
     solve_puzzle(Matrix),
     display_matrix(Matrix).

但我希望能够设置矩阵的大小，所以我写了这个：

generate_list(N, [ ]) :-
    N =< 0, !.
generate_list(N, [_ | T]) :-
    N > 0,
    N2 is N - 1,
    generate_list(N2, T).

generate_matrix(_, N, []) :-
    N =< 0, !.
generate_matrix(M, N, [R|T]) :-
    generate_list(M,R),
    N2 is N - 1,
    generate_matrix(M, N2, T).

然后我可以做：

main:-
    Rows = 4, Columns = 4,
    generate_matrix(Columns,Rows,Matrix),
    solve_puzzle(Matrix),
    display_matrix(Matrix).

但这似乎减慢了我的程序。有没有更好的方法生成N x M矩阵？

Answer 1

length/2 和 maplist/2 的组合在这里效果很好：

length_list(N, List) :- length(List, N).

generate_matrix(Cols, Rows, Matrix) :-
    length_list(Rows, Matrix),
    maplist(length_list(Cols), Matrix).

我定义 length_list/2 将长度参数放在前面以便在 maplist/2 中使用它。

length/2 是关系型的，因此当您使用实例化的长度调用 length/2（例如，N），但将列表参数作为变量时，它会导致 [_,_, ..., _] 和 N 个元素。因此，第一个 length_list 创建了一个列表 Matrix，看起来像 [_, _, _, ..., _]，长度为 Rows。然后下面的 maplist/2 将针对 Matrix 的每个元素（第 R 行）调用 length_list(Cols, R) 生成一个列表 _ 来代替每个 _ 29=] 长度 Cols.

maplist/2 将调用第一个参数作为第二个参数（列表）的每个元素的谓词。由于我们给它 length_list(Cols)，它正在为 [_, _, ..., _] 中的每个元素调用 call(length_list(Cols), _)，这等同于 call(length_list(Cols, _))，这将实例化 _ ] 和 [_, _, ..., _]，一个长度为 Cols.

的匿名变量列表

我使用 SWI Prolog 的 time/1 进行了一些快速计时检查，上述方法似乎快得多。

为解谜程序序言程序生成矩阵

Generate a matrix for a puzzle solver prolog program

matrix

prolog