XSLT 2.0 and XPath 2.0 Programmer's Reference, 4th Edition (738 page)

This depends, of course, on the function
make-best-move()
, which we will look at next. This function is a bit more complex, even though it delegates the task of finding the best move yet again, to another function called
find-best-move()
.

In fact, the first thing that this function does is to call
find-best-move()
to decide which move to make. It then makes a note of all the other possible moves, just in case it needs to backtrack (lazy evaluation comes in handy here: the variable
$other-possible-moves
won't be evaluated unless it's actually needed).

Then the function makes the selected move by placing the knight on the chosen square, using the
place-knight()
function that we saw earlier, and finally it makes a recursive call on
make-moves()
, which we've also seen earlier, to complete the rest of the tour from this new position.

If this final call returns a normal board, then we've finished, and the function exits, unwinding the whole stack down to the initial template, which can now print the final board and quit. However, if the final board is the special value
()
, then backtracking is needed. This is done by calling
try-possible-moves()
with a reduced list of possible moves, that excludes the move that we've found to be a cul-de-sac.

Selecting the Best Move

The one thing remaining is to look at the template
find-best-move
, which from a set of possible moves chooses the best one, namely the move to the square with fewest exits.

As always, the logic is recursive. We keep track of the best move so far, and the number of exits that the best move so far possesses. If the first move in the list (the
trial move
) is better than the best move so far, it replaces the previous best, and we then call the template to process the other moves in the list. The final output is the best move after examining the whole list.

To find the number of exits for a given move, we create a trial board, and make that move by calling the
place-knight
function described earlier. Using this board, we then call the
list-possible- moves
function, also described earlier, to see what moves would be available after the trial move. We aren't interested in the details of these moves, only in how many there are, which we can find out simply by examining the length of the list.

We can now calculate two variables: the best move so far and the least number of exits, based on whether the trial move is better than the previous best. If the move is the best one so far, it is output. Finally, the
find-best-move
function calls itself recursively to process the remaining moves in the list. On completion, the value returned by the function is the best move, that is, the square to which the knight should move next.