使用 Warnsdorff 规则的 Gprolog Knight's Tour

Question

我正在尝试在 Gprolog 中实施 Warnsdorff 规则以在任意棋盘上生成游览。我发现一个 SO post 在 B-prolog 中提供了一个很好的解决方案，我只需要翻译 Warnsdorff 步骤 (knight's tour efficient solution)。

下面是我对 Warnsdorff 步骤的实现：

warnsdorffSelect(X, Y, Row, Col, Past, NewX_, NewY_) :-
  setof((Count, NewX, NewY), (
    possibleMovesFromPosWithBoard(X, Y, Row, Col, Past, NewX, NewY),
    countMoves(NewX, NewY, Row, Col, [(NewX, NewY) | Past], Count).
  ), [(_, NewX_, NewY_)|_]).

possibleMovesFromPosWithBoard/7 returns 从一个位置的所有合法移动和 countMoves/6 returns 从一个位置的 number 移动位置。

我的问题发生在函数无法select导致新位置移动次数最少的移动，而是选择return结果列表中的第一个移动（即也就是说，它似乎没有排序）。最后，程序总是会导致 'no'，因为它让自己陷入困境。

提前致谢！

Answer 1

完整搜索space轻松恢复：

warnsdorffSelect(X, Y, Row, Col, Past, NewX_, NewY_) :-
  setof((Count, NewX, NewY), (
    possibleMovesFromPosWithBoard(X, Y, Row, Col, Past, NewX, NewY),
    countMoves(NewX, NewY, Row, Col, [(NewX, NewY) | Past], Count).
  ), Sorted),
  % on backtracking, get all steps sorted from lower Count to higher
  member((_, NewX_, NewY_), Sorted).

使用 Warnsdorff 规则的 Gprolog Knight's Tour

Gprolog Knight's Tour using Warnsdorff's Rule

prolog

knights-tour