Gprolog Knight's Tour using Warnsdorff's Rule

Question

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).

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 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.

Thanks in advance!

Answer 1

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).