使用 Warnsdorff 规则的 Gprolog Knight's Tour [英] Gprolog Knight's Tour using Warnsdorff's Rule

问题描述

我正在尝试在 Gprolog 中实施 Warnsdorff 规则以在任意棋盘上生成游览.我发现了一个 SO post 在 B-pr​​olog 中提供了一个很好的解决方案，我只需要翻译 Warnsdorff 步骤(骑士之旅高效解决方案).

I'm trying to implement Warnsdorff's Rule in Gprolog to generate tours on an arbitrary chessboard. I found an SO post providing a good solution in B-prolog, and I simply needed to translate the Warnsdorff step (knight's tour efficient solution).

以下是我对 Warnsdorff 步骤的实现:

Below is my implementation of the Warnsdorff step:

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 返回从一个位置开始的所有合法移动，countMoves/6 返回从一个位置移动的数量.

possibleMovesFromPosWithBoard/7 returns all legal moves from a position and countMoves/6 returns the number of moves from a position.

当函数未能选择导致从新位置开始移动次数最少的移动，而是选择返回结果列表中的第一个移动(也就是说，它似乎没有进行排序).最后，程序总是以否"为结果，因为它把自己逼到了角落.

My problem happens when the function fails to select the move that results in the lowest number of moves from the new position and instead opts to return the first move in the resulting list (that is to say, it doesn't appear to be sorting). In the end the program always results in 'no' because it backs itself into a corner.

提前致谢！

推荐答案

很容易恢复完整的搜索空间:

The full search space is easily recovered:

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的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！