将表谓词从 b-prolog 转换为 gprolog

Question

为了好玩，我一直在尝试使用 Warnsdorf 规则在 gprolog 中编写 Knight's Tour (https://en.wikipedia.org/wiki/Knight%27s_tour) 求解器。

我发现另一个 SO post 询问效率，它在 B-prolog 中提供了一个解决方案： knight's tour efficient solution.

我的问题出现在以下部分：

:- table warnsdorff(+,+,+,+,+,-,-,min).
warnsdorff(R, C, X, Y, Visits, NewX, NewY, Score) :-
    possible_knight_moves(R, C, X, Y, Visits, NewX, NewY),
    possible_moves_count(R, C, NewX, NewY, [(NewX, NewY) | Visits], Score).

B-prolog 具有 tabled 谓词而 gprolog 没有。我在尝试将 table 部分翻译成 gprolog 时遇到了很大的困难。在实践中，该函数应该 return 从当前位置开始的移动，导致从新位置开始的可能移动数最少（平局是随机选择的）。

如有任何帮助，我们将不胜感激。干杯！

Answer 1

对于这个问题，表格可能有点过分了。由于 Visits 列表已经在求解时进行，因此只需使用 memberchk/2。我在 SWI-Prolog 中得到了这个解决方案（其中，顺便说一句，实现了制表，但无法使用您链接到的原始编码解决难题）：

?- time(knight(8, 8, 1, 1, [], Path))...
% 19,973 inferences, 0.019 CPU in 0.019 seconds (100% CPU, 1047591 Lips)
[(1,1),(2,3),(1,5),(2,7),(4,8),(6,7),(8,8),(7,6),(6,8),(8,7),(7,5),(8,3),(7,1),(5,2),(3,1),(1,2),(2,4),(1,6),(2,8),(3,6),(1,7),(3,8),(5,7),(7,8),(8,6),(7,4),(8,2),(6,1),(4,2),(2,1),(1,3),(3,2),(5,1),(6,3),(8,4),(7,2),(5,3),(4,1),(2,2),(1,4),(3,3),(2,5),(4,4),(6,5),(4,6),(3,4),(5,5),(4,3),(6,2),(8,1),(7,3),(5,4),(3,5),(4,7),(2,6),(1,8),(3,7),(4,5),(6,4),(5,6),(7,7),(5,8),(6,6),(8,5)]

如果你愿意，我可以告诉你Warnsdorff规则。我使用 setof/3 来获得最小计数，加入 possible_knight_moves/7 和 possible_moves_count/6。

编辑

按要求：

warnsdorff(R, C, X, Y, Visits, NewX_, NewY_) :-
    setof((Count, NewX, NewY), (
              possible_knight_moves(R, C, X, Y, Visits, NewX, NewY),
              possible_moves_count(R, C, NewX, NewY, [(NewX, NewY) | Visits], Count)
          ), [(_, NewX_, NewY_)|_]).

为清楚起见，我已将输出变量重命名为 NewX_、NewY_，但这无关紧要 - 它也适用于原始命名。

将表谓词从 b-prolog 转换为 gprolog

Translating a tabled predicate from b-prolog to gprolog

prolog

predicate

declarative

knights-tour