Finding the Route
So much for the input and output of the stylesheet, now for the substance: the algorithm to calculate the knight 's tour.
The basic algorithm we use is that at each move, we consider all the squares we could go to, and choose the one with the fewest exits. For example, if we are on c2 then we could move to a1, e1, a3, e3, b4, or d4, assuming they are all unvisited. Of these, the corner square a1 has only one exit, namely b3, and if we don't visit the corner square now, then we'll never get another chance later. It turns out that this strategy of always visiting the square with least exits nearly always succeeds in generating a complete knight's tour, though in the rare cases where it doesn't, the algorithm is resilient enough to backtrack and try a different route if the first one fails.
The root template makes a call on the function named «make-moves ». This function, starting from any given start position, works out all the moves needed to complete the knight's tour. Of course, it does this by recursion: but unlike previous functions which called themselves directly, this one does so indirectly, via another function named «try-possible-moves ».
The first thing the «make-moves » template does is to call the template «list-possible- moves » to construct a list of moves that are legal in the current situation. The result of this function, a list of moves, uses a very similar data structure to that of the chessboard itself. The list is represented as a sequence, and each possible move is represented by an integer whose value is the number of the square to which the knight travels . So in Figure 12-3, after move 5 the set of possible moves is the list (3, 19, 28, 30, 23). The list is in no particular order.
Figure 12-3
Having established the list of possible moves, the function then calls «try-possible-moves » to select one of these moves and execute it.
Here is the function. Its parameters are the number of this move (starting at move 2, because the knight's initial position is numbered 1), the state of the board before this move, and the number of the square on which the knight is currently sitting.
<xsl:function name="tour:make-moves" as="xs:integer*"> <!-- This function takes the board in a given state, decides on the next move to make, and then calls itself recursively to make further moves, until the knight has completed his tour of the board. It returns the board in its final state. --> <xsl:param name="move" as="xs:integer" /> <xsl:param name="board" as="xs:integer*" /> <xsl:param name="square" as="xs:integer" /> <!-- determine the possible moves that the knight can make --> <xsl:variable name="possible-move-list" as="xs:integer*" select="tour:list-possible-moves($board, $square)"/> <!-- try these moves in turn until one is found that works --> <xsl:sequence select="tour:try-possible-moves($move, $board, $square, $possible-move-list)"/> </xsl:function>
Finding the Possible Moves
The next function to examine is «list-possible-moves » . This takes as input the current state of the board and the position of the knight, and it produces a list of squares that the knight can move to. For a knight in the center of the board there are eight possible squares it can move to (as shown in Figure 12-4): those squares that are either two columns and one row, or two rows and one column, removed from the current row.
Figure 12-4
However, we have to consider the case where some of these squares are unavailable because they are off the edge of the board, and we also have to eliminate any squares that have already been visited. The logic I have used is simple, if verbose; it simply examines each of the eight candidate squares in turn:
<xsl:function name="tour:list-possible-moves" as="xs:integer*"> <xsl:param name="board" as="xs:integer*" /> <xsl:param name="square" as="xs:integer" /> <xsl:variable name="row" as="xs:integer" select="$square idiv 8"/> <xsl:variable name="column" as="xs:integer" select="$square mod 8"/> <xsl:sequence select=" (if ($row > 1 and $column > 0 and $board[($square - 17) + 1]=0) then $square - 17 else (), if ($row > 1 and $column < 7 and $board[($square - 15) + 1]=0) then $square - 15 else (), if ($row > 0 and $column > 1 and $board[($square - 10) + 1]=0) then $square - 10 else (), if ($row > 0 and $column < 6 and $board[($square - 6) + 1]=0) then $square - 6 else (), if ($row < 6 and $column > 0 and $board[($square + 15) + 1]=0) then $square + 15 else (), if ($row < 6 and $column < 7 and $board[($square + 17) + 1]=0) then $square + 17 else (), if ($row < 7 and $column > 1 and $board[($square + 6) + 1]=0) then $square + 6 else (), if ($row < 7 and $column < 6 and $board[($square + 10) + 1]=0) then $square + 10 else () )" /> </xsl:function>
An observation: not everyone is happy with the idea of writing a single XPath expression that is 16 lines long in the middle of a stylesheet. Some would prefer to write this code using XSLT instructions, using <xsl:choose>. I'm comfortable with the code as written, but you can express the same logic at the XSLT level if you prefer.
Another approach would be to try and capture all the logic in a single expression, as follows :
for $r in (-2, -1, +1, +2), $c in (-(3-abs($r)), +(3-abs($r))) if ($row+$r = 0 to 7 and $column+$c = 0 to 7 and $board[($row+$r)*8 + ($column+$c) + 1] eq 0)) then ($row+$r)*8 + ($column+$c) + 1 else ()
So having found the possible moves we can make, we need to select one of them and make it. This is the job of the try-possible-moves function.
Trying the Possible Moves
At the top level, this function is quite simple. As input it gets the current state of the board, the current position of the knight, the current move, and the list of moves that the knight can make from its current position. If there is at least one move that it can make, then it makes the best move it can find and returns the new state of the board; otherwise , it returns the special value «() » to indicate that it has failed, and that another path needs to be found.
<xsl:function name="tour:try-possible-moves" as="xs:integer*" > <xsl:param name="move" as="xs:integer" /> <xsl:param name="board" as="xs:integer*" /> <xsl:param name="square" as="xs:integer" /> <xsl:param name="possible-moves" as="xs:integer*" /> <xsl:sequence select="if (count($possible-moves)!=0) then tour:make-best-move($move, $board, $square, $possible-moves) else ()"/> <!-- if there is no possible move, we return the special value () as the final state of the board, to indicate to the caller that we got stuck --> </xsl:function>
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.
<xsl:function name="tour:make-best-move" as="xs:integer*"> <xsl:param name="move" as="xs:integer" /> <xsl:param name="board" as="xs:integer*" /> <xsl:param name="square" as="xs:integer" /> <xsl:param name="possible-moves" as="xs:integer*" /> <!-- if at least one move is possible, find the best one --> <xsl:variable name="best-move" select="tour:find-best-move($board, $possible-moves, 9, 999)"/> <!-- find the list of possible moves excluding the best one --> <xsl:variable name="other-possible-moves" as="xs:integer*" select="$possible-moves[. != $best-move]"/> <!-- update the board to make the move chosen as the best one --> <xsl:variable name="next-board" as="xs:integer*" select="tour:place-knight($move, $board, $best-move)"/> <!-- now make further moves using a recursive call, until the board is complete --> <xsl:variable name="final-board" as="xs:integer*" select = "if (count($next-board[.=0])!=0) then tour:make-moves($move+1, $next-board, $best-move) else $next-board"/> <!-- if the final board has the special value '()', we got stuck, and have to choose the next best of the possible moves. This is done by a recursive call. --> <xsl:sequence select=" if (empty($final-board)) then tour:try-possible-moves($move, $board, $square, $other-possible-moves) else $final-board"/> </xsl:function>
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 » template described earlier. Using this board, we then call the «list-possible-moves » template, 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 » template calls itself recursively to process the remaining moves in the list. On completion, the value returned by the template is the best move, that is, the square to which the knight should move next.
<xsl:function name="tour:find-best-move" as="xs:integer*" > <!-- This function finds from among the possible moves, the one with fewest exits. It calls itself recursively. --> <xsl:param name="board" as="xs:integer*" /> <xsl:param name="possible-moves" as="xs:integer*" /> <xsl:param name="fewest-exits" as="xs:integer" /> <xsl:param name="best-so-far" as="xs:integer" /> <!-- split the list of possible moves into the first move and the rest of the moves --> <xsl:variable name="trial-move" as="xs:integer" select="$possible-moves[1]"/> <xsl:variable name="other-possible-moves" as="xs:integer*" select="$possible-moves[position() gt 1]"/> <!-- try making the first move --> <xsl:variable name="trial-board" as="xs:integer*" select="tour:place-knight(99, $board, $trial-move)"/> <!-- see how many moves would be possible the next time --> <xsl:variable name="trial-move-exit-list" as="xs:integer*" select="tour:list-possible-moves($trial-board, $trial-move)"/> <xsl:variable name="number-of-exits" as="xs:integer" select="count($trial-move-exit-list)"/> <!-- determine whether this trial move has fewer exits than those considered up till now --> <xsl:variable name="minimum-exits" as="xs:integer" select="min(($number-of-exits, $fewest-exits))"/> <!-- determine which is the best move (the one with fewest exits) so far --> <xsl:variable name="new-best-so-far" as="xs:integer" select="if ($number-of-exits lt $fewest-exits) then $trial-move else $best-so-far"/> <!-- if there are other possible moves, consider them too, using a recursive call. Otherwise return the best move found. --> <xsl:sequence select="if (count ($other-possibie-moves)!=0) then tour:find-best-move($board, $other-possible-moves, $minimum-exits, $new-best-so-far) else $new-best-so-far"/> </xsl:function>
And that's it.
Running the Stylesheet
To run the stylesheet, download it from the Wrox.com and execute it. No source document is needed. With Saxon, for example, try:
java -jar saxon7.jar -it main tour.xsl start=b6 >tour.html This requires Saxon version 7.9 or later. Earlier versions do not allow the «-it » option, which causes execution of the stylesheet to start by calling the named template «main ». However, if you want to run the stylesheet with an earlier version of Saxon you can do this simply by supplying a dummy source document, which will not actually be used.
The output of the stylesheet is written to the file tour.html which you can then display in your browser.
The stylesheet requires an XSLT 2.0 processor, so at the time of writing, Saxon is your only choice. If you use a different XSLT 2.0 processor, you will need to consult its documentation to find out how to supply parameters from the command line. If you don't supply a starting square, the tour will start at the a1 square.
Observations
The knight's tour not a typical stylesheet, but it illustrates the computational power of the XSLT language, and in particular the essential part that recursion plays in any stylesheet that needs to do any non-trivial calculation or handle non-trivial data structures. And although you will probably never need to use XSLT to solve chess problems, you may just find yourself doing complex calculations to work out where best to place a set of images on a page, or how many columns to use to display a list of telephone numbers , or which of today's news stories should be featured most prominently given your knowledge of the user 's preferences.
So if you're wondering why I selected this example, there are two answers: firstly, I enjoyed writing it, and secondly, I hope it persuaded you that there are no algorithms too complex to be written in XSLT.
The other thing that's worth noting about this stylesheet is how much it benefits from the new features in XSLT 2.0. In the first edition of this book, I published a version of this stylesheet that was written in pure XSLT 1.0: it used formatted character strings to represent all the data structures. In the second edition, I published a revised version that used temporary trees (as promised in the later- abandoned XSLT 1.1 specification) to hold the data structures. The following table shows the size of these three versions (in non-comment lines of code), revealing the extent to which the new language features contribute to making the stylesheet easier to write and easier to read. However it also shows the execution times in milliseconds of each version, using Saxon 7.8, which reveals that my first solution, which used formatted character strings to hold all the data, is actually the fastest :
| Version | Data structure | Lines of code | Execution time |
|---|---|---|---|
| 1.0 | character strings | 276 | 580 |
| 1.1 | temporary trees | 267 | 1050 |
| 2.0 | sequences | 59 | 900 |
The reason that the solution using character strings is the fastest almost certainly reflects the costs associated with memory management. Representing a chessboard as a sequence of 64 integers requires Java to allocate many more objects than when the board is represented as a single string of 192 characters (for each square I used two characters for the knight's position, plus a separator character). A better optimizer might do better, for example by avoiding the cost of copying the whole sequence of 64 integers when placing the knight on a particular square. But this result does suggest that if you want the ultimate in performance and don't mind writing a lot more code, representing a sequence as a structured character string might still be an approach worth considering.
The earlier versions of the stylesheet are included in the download file under the names tour10.xsl and tour11.xsl. The file ms-tour11.xsl is a variant of tour11.xsl designed to work with Microsoft's MSXML3 and later processors.
EAN: 2147483647
Pages: 324