Prolog-在矩阵中查找单词

Question

给定一个nxn字母矩阵和一个单词列表，该程序应在矩阵中找到单词的所有外观及其位置。

它们可以上下，左右和对角线出现(在所有8个方向上)。一个单词可以出现任意次(包括零次)，并且可以重叠(例如单词bad和adult)，甚至可以是彼此的子集(例如单词bad和ad)。

Answer 1

编辑这是完整的代码(也可以在对角线上找到单词)。缺点之一:主要对角线中的单词被发现两次。

% word(X) iff X is a word
word("foo").
word("bar").
word("baz").

% prefix(?A, +B) iff A is a prefix of B
prefix([], _).
prefix([A|B], [A|C]) :- prefix(B, C).

% sublist(?A, +B) iff A is a sublist of B
sublist(A, B) :- prefix(A, B).
sublist(A, [_|B]) :- sublist(A, B).

% reversed(?A, +B) iff A is reversed B
reversed(A, B) :- reversed(B, [], A).
reversed([A|B], C, D) :- reversed(B, [A|C], D).
reversed([], A, A).

% rowsreversed(?A, +B) iff matrix A is matrix B with reversed rows
rowsreversed([A|B], [C|D]) :- reversed(A, C), rowsreversed(B, D).
rowsreversed([], []).

% transposed(+A, ?B) iff matrix B is transposed matrix A
transposed(A, B) :- transposed(A, [], B).
transposed(M, X, X) :- empty(M), !.
transposed(M, A, X) :- columns(M, Hs, Ts), transposed(Ts, [Hs|A], X).

% empty(+A) iff A is empty list or a list of empty lists
empty([[]|A]) :- empty(A).
empty([]).

% columns(+M, ?Hs, ?Ts) iff Hs is the first column
%   of matrix M and Ts is the rest of matrix M
columns([[Rh|Rt]|Rs], [Rh|Hs], [Rt|Ts]) :- columns(Rs, Hs, Ts).
columns([[]], [], []).
columns([], [], []).

% inmatrix(+M, ?W) iff word W is in the matrix M
inmatrix(M, W) :- inrows(M, W).
inmatrix(M, W) :- incolumns(M, W).
inmatrix(M, W) :- inleftdiagonals(M, W).
inmatrix(M, W) :- inrightdiagonals(M, W).

% inrows(+M, ?W) iff W or reversed W is in a row of M
inrows([R|_], W) :- word(W), sublist(W, R).
inrows([R|_], W) :- word(W), reversed(V, W), sublist(V, R).
inrows([_|Rs], W) :- inrows(Rs, W).

% incolumns(+M, ?W) iff W or reversed W is in a column of M
incolumns(M, W) :- transposed(M, N), inrows(N, W).

% inleftdiagonals(+M, ?W) iff W or reversed W is in a left diagonal of M
inleftdiagonals(M, W) :- inupperleftdiagonals(M, W).
inleftdiagonals(M, W) :- transposed(M, N), inupperleftdiagonals(N, W).

% inupperleftdiagonals(+M, ?W) iff W or reversed W is in an upper left diagonal of M
inupperleftdiagonals(M, W) :- upperdiags(M, N), inrows(N, W).

% upperdiags(+M, ?X) iff X is a list of upper diagonals of matrix M
upperdiags(M, X) :- upperdiags(M, [], Y), reversed(Z, Y), transposed(Z, X).
upperdiags([R|Rs], A, X) :- columns(Rs, _, T), upperdiags(T, [R|A], X).
upperdiags([], X, X).

% inrightdiagonals(+M, ?W) iff W or reversed W is in a right diagonal of M
inrightdiagonals(M, W) :- rowsreversed(N, M), inleftdiagonals(N, W).