prolog - Prolog谓词遍历网格

Question

考虑以下谓词：path(Start, End, Size, Path)

Start是网格中由列表 [row, column] 标识的单元格。 End是由列表 [row, column] 标识的网格中的一个单元格。大小是给出最大行和列值的列表。路径由相邻单元格的列表组成，其中相邻是左/右和上/下。路径没有环路；即一个单元格只能在列表中出现一次。

使用以下查询：path([1,1], [4,4], [4,4], Path]。有效路径为：[[1,1], [1,2], [1, 3]、[1,4]、[2,4]、[2,3]、[3,3]、[3,4]、[4,4)]。

你会如何解决这个问题？

score 0 · Accepted Answer

这是一个开始。首先定义路径。

path(X,Y,[X,Y]):- edge(X,Y).
path(X,Y,[X|Xs]):- edge(X,W), path(W,Y,Xs).

然后定义边缘：

edge([X,Y], [X1,Y]) :- X1 is X + 1.
edge([X,Y], [X,Y1]) :- Y1 is Y + 1.

现在你的谓词：

grid_path(START, END, LIMIT, SOLUTION) :-
    within_limit(END, LIMIT),
    path(START,END, SOLUTION).

我不想破坏乐趣，所以我把它留给你。该解决方案只会生成所有可能的候选者，而且效率非常低。您可以玩耍并优化搜索。

1 回答 1