C.2. The Stylesheet
C.2.1. Headers
The stylesheet starts with standard “boilerplate” headers.
Declare it as an XML document:
<?xml version="1.0" encoding="ISO-8859-1"?>
A copyright notice:
<!-- Copyright (C) 2000 Oren Ben-Kiki This stylesheet is public domain. However, if you modify it or decide to use it as part of an XSLT benchmark/testing suite, I'd appreciate it if you let me know at [email protected] -->
A descriptive comment:
<!-- This XSL stylesheet will convert an XML document of the form: <BoardSize>8</BoardSize> Into an HTML document listing all 8x8 chess boards containing 8 queens such that no one threatens another. It uses XSLT version 1.0, as per http://www.w3.org/TR/1999/REC-xslt-19991116 -->
Now we get to the stylesheet itself. Since we would like to emit HTML output, we need to supply an <xsl:output> element. Providing a public doctype isn't strictly necessary, but it is good form. It helps browsers realize which brand of HTML you are using.
<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output method="html"
doctype-public="-//W3C//DTD HTML 4.0 Transitional//EN"/>
C.2.1.1. BoardSize
<xsl:template match="BoardSize">
This template will match the single element expected in the input document. It is a pretty standard template, emitting the overall HTML document structure and invoking the PlacedQueens template to actually generate all the solutions to the problem. The parameters to PlacedQueens are:
<html>
<head>
<title>
<xsl:text>Solutions to the </xsl:text>
<xsl:value-of select="."/>
<xsl:text>-Queens problem</xsl:text>
</title>
</head>
<body>
<h1>
<xsl:text>Solutions to the </xsl:text>
<xsl:value-of select="."/>
<xsl:text>-Queens problem</xsl:text>
</h1>
<xsl:call-template name="PlaceQueenInRow">
<xsl:with-param name="BoardSize"
select="."/>
<xsl:with-param name="Row" select="0"/>
<xsl:with-param name="PlacedQueens"
select="'-'"/>
</xsl:call-template>
</body>
</html>
</xsl:template>
C.2.2. Compute the Set of Solutions
C.2.2.1. PlaceQueensInRow
<xsl:template name="PlaceQueenInRow"> <xsl:param name="BoardSize"/> <xsl:param name="PlacedQueens"/> <xsl:param name="Row"/>
This template will emit all the solutions to the problem, given that all the queens in the rows up to Row were already placed. This placement is given in PlacedQueens, and is represented as described in Section C.1.2.
Thus, the first invocation specified Row="0" and PlacedQueens="-", indicating that no queens have yet been placed, and therefore requests emitting all the possible solutions to the problem. An invocation with Row="1" and PlacedQueens="-1-" would request to emit only the solutions where the queen in the first row is placed in the second column, and so on. Note that there may be zero, one, or several such solutions; the template's task is to print (as HTML) each and every valid solution, or nothing at all if there are none. This principle is used in all the rest of templates in this section.
<xsl:choose> <xsl:when test="$Row = $BoardSize">
This template is called repeatedly as parts of solutions are generated, with increasing Row values. Eventually, all the queens will be placed. In this case, we are actually given a complete solution, not just part of one. All that remains to be done is to print it. Note that here we strip the leading - from the placement string to make it easier to process.
<xsl:call-template name="PrintBoard">
<xsl:with-param name="BoardSize" select="$BoardSize"/>
>
<xsl:with-param name="PlacedQueens"
select="substring-
after($PlacedQueens, '-')"/>
</xsl:call-template>
</xsl:when>
<xsl:otherwise>
In the general case, however, we are given only a partial solution—for example, just the two first queens out of four. In this case, we need to explore all the possible columns where the third queen can be placed. PlaceQueenInColumn will do this for us.
<xsl:call-template name="PlaceQueenInColumn">
<xsl:with-param name="BoardSize" select="$BoardSize"/>
<xsl:with-param name="PlacedQueens"
select="$PlacedQueens"/>
<xsl:with-param name="Row" select="$Row"/>
<xsl:with-param name="Column" select="0"/>
</xsl:call-template>
</xsl:otherwise>
</xsl:choose>
</xsl:template>
C.2.2.2. PlaceQueenInColumn
<xsl:template name="PlaceQueenInColumn"> <xsl:param name="BoardSize"/> <xsl:param name="PlacedQueens"/> <xsl:param name="Row"/> <xsl:param name="Column"/>
This template will emit all the solutions to the problem, given that all the queens in the rows up to Row were already placed. This placement is given in PlacedQueens, and is represented as described in Section C.1.2. The queen to be placed at the specified Row must be placed at or after the given Column.
This is our first loop template. We need to go over each column, check whether it is valid to place a queen there, and if so, emit all the solutions with the queen placed in that column. Therefore, this template follows the form described in Section C.1.3. The complete list of inputs is the integers 0, 1, ..., BoardSize - 1. The Column parameter serves as the list of the rest of the inputs; the remaining integers are those no smaller then Column.
<xsl:if test="$Column < $BoardSize">
Test whether there are more inputs to process—that is, verify we haven't finished checking all the columns. If we haven't, do the repeated processing steps. These apply to the next input—in our case, the specified column.
<xsl:if test="not(contains($PlacedQueens,
concat('-', $Column, '-')))">
The first step is to ensure that no previously placed queen was assigned the same column. We use a small trick here, using string operations to do that. Given our representation, we can check that no queen was placed in column 1 by looking for the substring -1- in the PlacedQueens string. This is why we need the leading -; if it weren't there, we'd miss on checking the column of the queen in the first row. Checking just for 1- doesn't work when working with large problems (e.g., in the 12-Queens problem, it would match the placement -11-).
If no queen was placed in this column, we still need to check that there is no queen placed in the same diagonal. Here we can't use any string tricks, so we have to resort to using another loop, testing this column against each of the previously placed queens in turn. Again, we strip the leading - from the string to make it easier to process.
<xsl:call-template name="TestQueenPosition">
<xsl:with-param name="BoardSize" select="$BoardSize"/>
<xsl:with-param name="PlacedQueens" select="$PlacedQueens"/>
<xsl:with-param name="Row" select="$Row"/>
<xsl:with-param name="Column" select="$Column"/>
<xsl:with-param name="TestQueens"
select="substring-after($PlacedQueens, '-')"/>
<xsl:with-param name="Offset" select="$Row"/>
</xsl:call-template>
</xsl:if>
Finally, there is the recursive invocation. We invoke the same template, but tell it to start working from the next column. Eventually, we will reach the end of the row and we will be done.
<xsl:call-template name="PlaceQueenInColumn">
<xsl:with-param name="BoardSize" select="$BoardSize"/>
<xsl:with-param name="PlacedQueens" select="$PlacedQueens"/>
<xsl:with-param name="Row" select="$Row"/>
<xsl:with-param name="Column" select="$Column + 1"/>
</xsl:call-template>
</xsl:if>
</xsl:template>
C.2.2.3. TestQueenPosition
<xsl:template name="TestQueenPosition"> <xsl:param name="BoardSize"/> <xsl:param name="PlacedQueens"/> <xsl:param name="Row"/> <xsl:param name="Column"/> <xsl:param name="TestQueens"/> <xsl:param name="Offset"/>
This template will emit all the solutions to the problem, given that all the queens in the rows up to Row were already placed. This placement is given in PlacedQueens, and is represented as described in Section C.1.2. The tentative placement of the queen in Row is in the specified Column. It needs to be verified that this placement is not on the same diagonal as any of the queens whose placement is listed in TestQueens, such that the offset in rows between the newly placed queen and the first queen in this list is given in Offset. TestQueens is in the same format as PlacedQueens, minus the leading -.
Again, this is a loop template. We need to check each of the TestQueens to see they are not on the same diagonal as the proposed placement. Only if none are, we may try to place additional queens in the remaining rows. Unlike the previous template, in this case the list of inputs is a real list, represented as a string.
<xsl:choose> <xsl:when test="not($TestQueens)">
There are no more queens to test. This means that the newly placed queen was not on the same diagonal as any of the previous ones. We still need to place the rest of the queens, in the rows below the current one. Invoking PlacedQueenInRow again will do this for us, by asking it to start one row down and adding this row's placement into PlacedQueens.
<xsl:call-template name="PlaceQueenInRow">
<xsl:with-param name="BoardSize" select="$BoardSize"/>
<xsl:with-param name="PlacedQueens">
<xsl:value-of select="$PlacedQueens"/>
<xsl:value-of select="$Column"/>
<xsl:text>-</xsl:text>
</xsl:with-param>
<xsl:with-param name="Row" select="$Row + 1"/>
</xsl:call-template>
</xsl:when>
<xsl:otherwise>
Otherwise, there are more queens to test.
<xsl:variable name="NextQueenColumn"
select="substring-before($TestQueens, '-')"/>
<xsl:if test="not($Column = $NextQueenColumn + $Offset)
and not($Column = $NextQueenColumn - $Offset)">
The new queen is on the same diagonal as the next queen to test if the offset in rows is identical to the offset in columns. Using a variable here makes the code a bit more readable. If we pass this test, we move to the recursive invocation to test the rest of the queens (if any). Since we are dealing with a physical list here, we have to pass it the tail of the list as well as update the diagonal's offset.
<xsl:call-template name="TestQueenPosition">
<xsl:with-param name="BoardSize" select="$BoardSize"/>
<xsl:with-param name="PlacedQueens" select="$PlacedQueens"/>
<xsl:with-param name="Row" select="$Row"/>
<xsl:with-param name="Column" select="$Column"/>
<xsl:with-param name="TestQueens"
select="substring-after($TestQueens, '-')"/>
<xsl:with-param name="Offset" select="$Offset - 1"/>
</xsl:call-template>
</xsl:if>
</xsl:otherwise>
</xsl:choose>
</xsl:template>
C.2.3. Print a Solution
C.2.3.1. PrintBoard
<xsl:template name="PrintBoard"> <xsl:param name="BoardSize"/> <xsl:param name="PlacedQueens"/>
This template will print a single solution to the problem as an HTML table. Like the BoardSize template, it doesn't do much but generate the overall structure and invoke PrintBoardRow to actually do the work. PlacedQueens contains the solution to print, as described in Section C.1.2, minus the leading -.
<hr/>
<table border="1">
<xsl:call-template name="PrintBoardRow">
<xsl:with-param name="BoardSize" select="$BoardSize"/>
<xsl:with-param name="PlacedQueens" select="$PlacedQueens"/>
</xsl:call-template>
</table>
</xsl:template>
C.2.3.2. PrintBoardRow
<xsl:template name="PrintBoardRow"> <xsl:param name="BoardSize"/> <xsl:param name="PlacedQueens"/>
This template will print a row (actually, all the remaining rows) of a solution to the problem. This is a pretty simple loop template; the only complication is that it invokes a nested loop template to print the columns in each row. PlacedQueens contains the remaining part of the solution to print, as described in Section C.1.2, minus the leading -.
<xsl:if test="$PlacedQueens">
Test that the remaining part of the solution to print is not empty.
<tr>
<xsl:call-template name="PrintBoardColumn">
<xsl:with-param name="ColumnsLeft" select="$BoardSize"/>
<xsl:with-param name="QueenColumn"
select="substring-before($PlacedQueens, '-')"/>
</xsl:call-template>
</tr>
The repeated processing steps are as follows: print all the columns in the next row (inside a <tr> element), using a nested loop template; followed by the recursive call, given the placement of the remaining rows to print.
<xsl:call-template name="PrintBoardRow">
<xsl:with-param name="BoardSize" select="$BoardSize"/>
<xsl:with-param name="PlacedQueens"
select="substring-after($PlacedQueens, '-')"/>
</xsl:call-template>
</xsl:if>
</xsl:template>
C.2.3.3. PrintBoardColumn
<xsl:template name="PrintBoardColumn"> <xsl:param name="ColumnsLeft"/> <xsl:param name="QueenColumn"/>
This template will print a column (actually, all the remaining columns) of a row of a solution to the problem. This is the simplest loop template in the stylesheet. The list to process is all the remaining columns, whose numbers are given in ColumnsLeft. A queen is placed in one of these columns; it is given in QueenColumn. This number is relative to the remaining columns; that is, when it is zero, the next column to print (the first in the list of remaining columns) is the one containing the queen. It is possible to rewrite this template to use an absolute queen column, but that would require us to pass an additional parameter (the BoardSize).
<xsl:if test="not($ColumnsLeft = 0)">
Test that there are more columns to print.
<td>
<xsl:choose>
<xsl:when test="$QueenColumn = 0">Q</xsl:when>
<xsl:otherwise> </xsl:otherwise>
</xsl:choose>
</td>
The repeated processing step here is simply to print the column. If this is where the queen is placed, put a Q in it; otherwise, use a nonbreaking space (some browsers require this to force them to draw the border around the cell). Note that we can't use the symbolic name because the XSLT processor does not recognize it.
Next is the recursive call, starting at the next column and with an adjusted queen column number.
<xsl:call-template name="PrintBoardColumn">
<xsl:with-param name="ColumnsLeft" select="$ColumnsLeft - 1"/>
<xsl:with-param name="QueenColumn" select="$QueenColumn - 1"/>
</xsl:call-template>
</xsl:if>
</xsl:template>
</xsl:stylesheet>