Knight 在 Prolog 中的游览：超出堆栈限制

Question

在我尝试使用 Warnsdorff 规则优化程序后，编译器开始发出 Stack limit exceeded。所有部分似乎都单独工作，但我不知道如何优化它。我在一台32位的旧笔记本电脑上写程序windows，所以我不能手动增加堆栈的大小，因为它在官方网站上写https://www.swi-prolog.org/FAQ/StackSizes.html。

knightpath(Board, [1 / 1 | Path]) :-
    Jumps is Board * Board,
    the_way(Jumps, [1 / 1 | Path]).
the_way(1, [X / Y]) : -
    between(1, 5, X),
    between(1, 5, Y).
the_way(Jumps, [X1 / Y1, X2 / Y2 | Path]) : -
    Jumps1 is Jumps - 1,
    the_way(Jumps1, [X2 / Y2 | Path]),
    warnsdorff(X2 / Y2, Path, X1 / Y1).
jump(X1 / Y1, X2 / Y2) : -
    ((X1 is X2 + 2;
      X1 is X2 - 2),
     (Y1 is Y2 + 1;
      Y1 is Y2 - 1);
     (X1 is X2 + 1;
      X1 is X2 - 1),
     (Y1 is Y2 + 2;
      Y1 is Y2 - 2)),
    between(1, 5, X1),
    between(1, 5, Y1).
warnsdorff(X1 / Y1, Path, X2 / Y2) :-
    find_posible(X1 / Y1, Path, Pos),
    find_best(_, [X1 / Y1 | Path], Pos, X2 / Y2).
find_best(N, Path, [X / Y], X / Y) : -
    find_posible(X / Y, Path, Pos),
    length(Pos, N).
find_best(N1, Path, [X / Y | List], X / Y) : -
    find_best(N2, Path, List, _),
    find_posible(X / Y, Path, Pos),
    length(Pos, N1),
    N1 < N2.
find_best(N2, Path, [X1 / Y1 | List], X2 / Y2) : -
    find_best(N2, Path, List, X2 / Y2),
    find_posible(X1 / Y1, Path, Pos),
    length(Pos, N1),
    N1 >= N2.
find_posible(X1 / Y1, Path, Pos) : -
    findall(X2 / Y2, jump(X2 / Y2, X1 / Y1), All_tog),
    filter_path(All_tog, Path, Pos).
filter_path([], _, []).
filter_path([X / Y | All_tog], Path, [X / Y | Pos]) : -
    not(member(X / Y, Path)),
    filter_path(All_tog, Path, Pos).
filter_path([X / Y | All_tog], Path, Pos) : -
    member(X / Y, Path),
    filter_path(All_tog, Path, Pos).

这是编译器生成的

ERROR: Stack limit (0.5Gb) exceeded
ERROR:   Stack sizes: local: 0.1Gb, global: 42.7Mb, trail: 0Kb
ERROR:   Stack depth: 1,863,822, last-call: 0%, Choice points: 3
ERROR:   In:
ERROR:     [1,863,822] user:the_way(-1863788, [length:1|_22365890])
ERROR:     [1,863,821] user:the_way(-1863787, '<garbage_collected>')
ERROR:     [1,863,820] user:the_way(-1863786, '<garbage_collected>')
ERROR:     [1,863,819] user:the_way(-1863785, '<garbage_collected>')
ERROR:     [1,863,818] user:the_way(-1863784, '<garbage_collected>')

Answer 1

回溯已经显示出了什么问题：the_way 被调用：

[1,863,822] user:the_way(<b>-1863788</b>, [length:1|_22365890])

这意味着 Jumps 变量是 -1863788。您没有在递归中执行正确的检查以避免使路径长于阈值。您应该添加一个约束，例如：

the_way(1, [X / Y]) : -
    between(1, 5, X),
    between(1, 5, Y).
the_way(Jumps, [X1 / Y1, X2 / Y2 | Path]) : -
    <b>Jumps > 1,</b>
    Jumps1 is Jumps - 1,
    the_way(Jumps1, [X2 / Y2 | Path]),
    warnsdorff(X2 / Y2, Path, X1 / Y1).

Answer 2

问题是 Warnsdorff 的规则没有为第一个（堆栈中的最后一个）方格为 1/1 的情况提供解决方案。我要写

knightpath(Answ) :-
    Jumps is Board * Board,
    the_way(Jumps, Path),
    reverse(Path, Answ).
...

the_way(1, [1/1]).

顺便说一下，如果我按照 Willem Van Onsem 的建议编写，那么可以避免错误，编译器将简单地输出 'false'.

Knight 在 Prolog 中的游览：超出堆栈限制

Knight's tour in Prolog: Stack limit exceeded

prolog

swi-prolog

knights-tour