The Algorithm | NetBeansв„ў IDE Field Guide: Developing Desktop, Web, Enterprise, and Mobile Applications (2nd Edition)

The strategy for getting the knight round the board is based on the observation that if a square hasn't been visited yet, and if it isn't the knight's final destination, then it had better have at least two unvisited squares that are a knight 's move away from it, because there needs to be a way of getting in and another way of getting out. That means that if we can get to a square that's only got one exit left, we'd better go there now or we never will.

This suggests an approach where at each move, we look at all the squares we can jump to next , and choose the one that has fewest possible exits. It turns out that this strategy works, and always gets the knight round the board.

It's possible that this could lead the knight into a blind alley, especially in the case where two of the possible moves look equally good. In this case, the knight might need to retrace its steps and try a different route. In the version of the stylesheet that I published in the previous edition of this book, I included code to do this backtracking, but made the assertion that it was never actually used (though I couldn't prove why). Recently, one of my readers reported that if the knight starts on square f8, it does indeed take a wrong turning at move 58, and needs to retrace its steps. Moreover, this appears to be the only case where this happens.

The place I usually start design is with the data structures. Here the main data structure we need is the board itself. We need to know which squares the knight has visited, and so that we can print out the board at the end, we need to know the sequence in which they were visited. In XSLT 2.0 the obvious choice is to represent the board as a sequence of 64 integers: the value will be zero for a square that has not been visited, or a value in the range 1 to 64 representing the number of the move on which the knight arrived at this square.

In a conventional program this data structure would probably be held in a global variable and updated every time the knight moves. We can't do this in XSLT, because variables can't be updated. Instead, every time a function is called, it passes the current state of the board as a parameter, and when the knight moves, a new copy of the board is created, that differs from the previous one only in the details of one square.

It doesn't really matter which way the squares are numbered, but for the sake of convention we'll number them as shown in Figure 12-2.

Figure 12-2

So if we number the rows 0-7, and the columns 0-7, the square number is given as «row * 8 + column + 1 », remembering that in XSLT, numbering of the items in a sequence always starts at one.

Having decided on the principal data structure we can decide the broad structure of the program. There are three stages:

Prepare the initial data structures (the empty board with a knight placed on it, somewhere)
Calculate the tour
Display the final state of the board

Calculating the tour involves 63 steps, each one taking the form:

Find all the unvisited squares that the knight can move to from the current position
For each one of these, count the number of exits (that is, the number of unvisited squares that can be reached from there)
Choose the square with the fewest exits, and move the knight there

We're ready to start coding. The tricky bit, as you've probably already guessed, is that all the loops have to be coded using recursion. That takes a bit of getting used to at first, but it quickly becomes a habit.

The Initial Template

Let's start with the framework of top-level elements:

  <xsl:transform   xmlns:xsl="http://www.w3.org/1999/XSL/Transform"   xmlns:xs="http://www.w3.org/2001/XMLSchema"   xmlns:tour="http://www.wrox.com/5067/tour"   exclude-result-prefixes="xs tour"   version="2.0"   >   <xsl:output method="html" indent="yes"/>   <xsl:param name="start" select="'a1'" as="xs:string"/>   <!-- start-column is an integer in the range 0-7 -->   <xsl:variable name="start-column"   select="number(translate(substring($start, 1, 1),   'abcdefgh', '01234567'))"/>   <!-- start-row is an integer in the range 0-7, with zero at the top -->   <xsl:variable name="start-row"   select="8 - number(substring($start, 2, 1))"/>   . . .   </xsl:transform>

All I'm doing here is declaring the global parameter, start, which defines the starting square, and deriving from it two global variables: a row number and column number.

Some observations:

The parameter start has the default value a1. As this is a string-value, it needs to be in quotes; these quotes are additional to the quotes that surround the XML attribute. If I had written «select="a1" », the default value would be the string-value of the <a1> element child of the document root.
The simplest way of converting the alphabetic column identifier (a-h) into a number (0-7) is to use the translate () function, which is described in XPath 2.0 Programmer's Reference , in Chapter 10.
The row number is subtracted from 8 so that the lowest -numbered row is at the top, and so that row numbers start from zero. Numbering from zero makes it easier to convert between row and column numbers and a number for each square on the board in the range 0-63.
I haven't yet checked that the supplied start square is valid. I'll do that in the initial template.

Now we can move on to the initial template. In XSLT 2.0 I can define the initial template as a named template, so that it can be invoked directly from the command line, without specifying a source document. However, just in case you're using a processor that doesn't support this capability, it does no harm to define the template with «match=" / " » as well.

The root template defines the stages of processing, as follows :

Validate the supplied parameter
Set up the empty board and place the knight on it at the specified starting square
Compute the knight's tour
Print out the tour in HTML format

These tasks are all delegated to other templates, so the root template itself is quite simple:

  <xsl:template name="main" match="/">   <!-- This template controls the processing.   It does not access the source document. -->   <!-- Validate the input parameter -->   <xsl:if test="not(matches($start, '^[a-h][1-8]$'))">   <xsl:message terminate="yes"   select="Invalid start parameter: try say 'a1' or 'g6'"/>   </xsl:if>   <!-- Set up the empty board -->   <xsl:variable name="empty-board" as="xs:integer*"   select="for $i in (1 to 64) return 0"/>   <!-- Place the knight on the board at the chosen starting position -->   <xsl:variable name="initial-board" as="xs:integer*"   select="tour:place-knight(1, $empty-board,   $start-row * 8 + $start-column)"/>   <!-- Evaluate the knight's tour -->   <xsl:variable name="final-board" as="xs:integer*"   select="tour:make-moves(2, $initial-board,   $start-row * 8 + $start-column)"/>   <!-- produce the HTML output -->   <xsl:call-template name="print-board">   <xsl:with-param name="board" select="$final-board"/>   </xsl:call-template>   </xsl:template>

Notice the style of coding here, which uses a sequence of variables, each one computed from the value of the previous variable. Each variable is used only once, which means the variables aren't actually necessary: it would be possible to nest all the function calls inside each other, and express the whole calculation using one big XPath expression inside the call to the final print-board template. But in my view, writing the processing logic like this as a sequence of steps makes it much easier to explain what's going on. The «as » clauses, which define the type of each variable, also provide useful documentation. (I also found that while I was writing this code, the type checking provided by the «as » clauses caught many of my errors.)

The code for validating the start parameter uses a simple regular expression. The symbols «^ » and «$ » match the start and end of the input string, and the body of the regular expression specifies that the string must consist of a single letter in the range [a-h] followed by a single digit in the range [1-8]. If the parameter doesn't match, the stylesheet outputs a message using <xsl:message>, and terminates.

Several of the variables ( empty-board, initial-board, and final-board ) represent a chessboard containing all or part of a knight's tour. Each of these variables is a sequence of 64 integers in the range 0 to 64. If the square has been visited, it contains a sequence number representing the order of visiting (1 for the start square, 2 for the next square visited, and so on). If the square has not been visited, the value is zero. The type «as="xs:integer* " » is actually much more liberal that this: it doesn't constrain the sequence to be of length 64, and it doesn't constrain the range of values to be 0 to 64. We could define a schema with a user -defined atomic type that allows only integers in the range 0 to 64, but it would seem overkill to import a schema just for this purpose, quite apart from the fact that the stylesheet would then work only with a schema-aware XSLT processor. Even then, restricting the size of the sequence to 64 is not something that the type system can achieve. Although list types can be defined in XML Schema to have a fixed length, this constraint can only be exploited in XSLT when validating an element or attribute node against this list type. Free-standing sequences of atomic values, like the ones being used here, cannot refer to a list type defined in the schema.

In parameters to function calls and in variables, squares on the board will always be represented by an integer in the range 0-63, which is calculated as $row * 8 + $column. When we use the square number to index the sequence that represents the board, we have to remember to add one.

The empty board is first initialized to a sequence of 64 zeroes, and the knight is then placed on its starting square by calling the function place-knight. Let's see how this function works.