Appendix C. Using XSLT for the Artificial Intelligence N-Queens Problem
 | CONTENTS |  |
Appendix C. Using XSLT for the Artificial Intelligence "N-Queens" Problem
|
by Oren Ben-Kiki
We are pleased to include a unique use of XSLT devised and summarized below by Oren Ben-Kiki. The N-Queens problem is discussed in many places dealing with artificial intelligence search algorithms. It is a problem which simply asks how to place the maximum number of queens on a chess board such that no queen can attack another (while I was writing a draft of this book, my niece Anna Marie was avidly occupied using pawns for some 27 minutes before finding a solution).
It was originally attributed to Max Bezzel in the German chess magazine Schach in 1848.[1] It was called the 8-Queens problem and was eventually republished in 1850, catching the attention of mathematicians seeking to solve all possible arrangements (there are 92). It was generalized to "n-Queens" under the work of E. Netto in 1901, who summarized it as the n x n chessboard problem (i.e., 4 x 4, 8 x 8). The 4 x 4 version became something of a craze in the United States, under the name 15-puzzle in the 1870s. Mathematicians again examined it in this iteration, with publications emerging in the American Journal of Mathematics. It began to be used on computers and revealed itself as a useful tool for comparing search algorithm performance in 1967. In 1986, it was shown that the n x n version's shortest possible solution belonged to a special class of problems known as NP-complete (nondeterministic polynomial) which are "most extreme" in difficulty.
Oren Ben-Kiki has worked with XSLT for some time and is currently Vice-President of R&D at Rich FX, Ltd. He devised this solution some time ago, in the early months of the XSLT specification. He annotated the solution below as a courtesy to the readers of this book. As an added point of interest, Oren has included a comparison set of statistics for a C++ solution at the end of his presentation below.
John Robert Gardner
C.1 Architecture
C.1.1 Overall structure
Aside from headers, the stylesheet consists of two sets of templates.
The first set computes the set of solutions to the N-Queens problem. It is built around the following principle: each template invocation is responsible for emitting all the solutions to the problem, given that part of the solution is known. The second set is in charge of formatting each solution into an HTML table for display. It processes a solution row by row and column by column, emitting the relevant HTML table tags for displaying the resulting chessboard.
C.1.2 Solution representation
To make this architecture work, we need some way to represent a solution during the execution of the stylesheet. The first set of templates would build this representation and the second set would convert it to HTML. Since we are working in XML, the immediate solution that comes to mind is something like:
<solution> <queen row="0" column="0"/> ... </solution>
Alas, this doesn't work. The reason is that once such a solution (or part of it) is created, XSLT does not allow us to do anything with it except emit it to the output document. This is because any XML generated by an XSLT fragment is considered to be a result tree fragment. In order to further process such fragments, we would need to apply templates to them. However, templates can only be applied to node-sets. Currently, XSLT does not allow us to convert a result tree fragment into a node-set. Allowing this operation opens up many interesting possibilities for writing stylesheets, and several XSLT processors support it as an extension. It is best to stick to standard XSLT whenever possible, so we will use strings to represent solutions instead. The scheme used in the stylesheet is based on the insight that there can be only one queen in each row (this insight is also used to efficiently search for all the valid solutions). Therefore, to represent a solution, all we need is the column number for each queen. To allow processing the solution string, we separate the column numbers by - characters. Thus, the following solution to the 4-Queens problem is represented as -1-3-0-2-:
Another thing we need is to represent a part of a solution. The representation we have chosen makes it possible by using a prefix of the full solution string. For example, -1- represents placing the first queen as in the above solution, without saying anything about the rest of the queens.
A final subtle point is that the leading - in the representation is there for a reason (see Section C.2.2.2). However, in templates processing each column number in the solution, this becomes a nuisance. We therefore strip the leading "-" before invoking such templates.
C.1.3 Implementing Loops
The final part of the architecture is the concept of loops and how to implement them in XSLT. A loop is the application of the same processing steps to a list of different inputs. Typically in XSLT, these inputs are available in the input document, allowing two ways of achieving this. The easiest is to write the following:
<xsl:for-each select="... the list of inputs ...">
repeated processing steps would otherwise be here, removed for brevity
</xsl:for-each>
Sometimes it is worthwhile to factor out the repeated processing to a separate template and use:
<xsl:apply-templates select="... the list of inputs ..."/>... repeated processing steps would otherwise be here, removed for brevity ... <xsl:template match="... the list of inputs ..."> ... repeated processing steps would otherwise be here, removed for brevity ...</xsl:template>
This is mostly useful when the same processing steps are invoked from multiple templates. In such cases, it may be impossible to write a match pattern that will identify the list of inputs and will not be triggered from undesired areas of the input document. To solve that, it is best to use a mode:
<xsl:apply-templates mode="bloop" select="... the list of inputs ..."/> ... <xsl:template mode="bloop" match="*"> ... repeated processing steps would otherwise be here, removed for brevity ...</xsl:template>
Specifying a mode ensures that the template will only be invoked from the matching <xsl:apply-template> calls, and nowhere else.
At any rate, our problem here is that for us, the list of inputs can't exist in the input document. The input document is just one element, and we'll need to perform many repeated operations, such as printing all the rows of a solution, all the columns in each row, and so on.
It turns out that this is possible in XSLT, with some effort. The general technique is that for each loop, we need to write a template along the following lines:
<xsl:template name="RepeatedWorkForManyInputs"> <xsl:param name="ListOfTheRestOfTheInputs"/>
other parameters repeated here
<xsl:if test="... there is at least one more input in the list ...">
<!-- do the work for the first input in the list -->
<xsl:call-template name="RepeatedWorkForManyInputs"> <xsl:with-param name="ListOfTheRestOfTheInputs">
<!-- the (possibly empty) list of the rest of the inputs -->
</xsl:with-param>
<!-- other parameters -->
</xsl:call-template> </xsl:if> </xsl:template>
Note
Computer scientists call this technique for implementing loops tail recursion. Recursion is defined as a function (or, in our case, a template) invoking itself. Tail recursion is the special case where the invocation appears as the very last thing in the body of the function.
This technique was originally invented as part of researching a family of computer languages known as functional languages. It turned out that it is relatively easy to optimize systems such that the tail recursive form is as efficient as a direct loop implementation; in fact, in most such languages, both forms are implemented in exactly the same way, internally.
People quickly found out, however, that having an explicit loop construct in the language is much easier to work with. Therefore every practical functional language has some sort of an explicit loop construct.
XSLT is still a young language, and it is conceivable that a future version of it will contain better support for loops. In the meantime, we are forced to use tail recursion whenever we need to loop on lists that are not a part of the input document.
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 oren@ben-kiki.org -->
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>
C.3 Final notes
The above stylesheet was tested using James Clark's XT XSLT processor. I also wrote a C++ implementation. Running both on my computer yielded the results in Table C-1.
| Number of Queens | Number of Solutions | Time to run in XSLT | Time to run in C++ |
|---|---|---|---|
| 4 | 2 | 1.0 second | 0.065 seconds |
| 6 | 4 | 1.5 second | 0.065 seconds |
| 8 | 92 | 8.5 seconds | 0.065 seconds |
| 10 | 724 | 3.0 minutes | 0.180 seconds |
XT is a pretty fast XSLT processor. It is just not optimized for the kind of processing this stylesheet performs. Not only that, while the stylesheet does print all the solutions to the N-Queens problem, it does not print a serial number by each. It turns out that doing so is a non-trivial problem. To achieve this, the stylesheet would need to collect all the valid solutions into a single long string, and only then print them one by one, as opposed to printing each solution the moment it was found. That would probably make it even less efficient. There's no such problem in the C++ program.
This demonstrates that while it is possible to perform general-purpose computations in XSLT, it may be impossible to do so in an efficient manner. In general, the techniques demonstrated in this stylesheet (using loop templates and using strings to represent complex data) do not scale well for large processing tasks.
It is doubtful that this situation will change in the future. XSLT was not design for such tasks. Instead, it provides standard mechanisms for accessing external functionality from an XSLT stylesheet, using extension elements and extension functions.
It is therefore important to assess the practicality of writing a complex processing task in XSLT as opposed to providing it as an extension function. As long as XSLT is used for small amounts of data, such as a single HTML page, the need for portability may well favor implementing the task in straight XSLT. For large amounts of data, such as processing large archives, the loss of portability may well be worth the huge increase in efficiency.
[1] A detailed discussion of N-Queens, from which the notes in the foreword are derived, is found with bibliographical references for further reading in Russell and Norvig's excellent AI text, Artificial Intelligence: A Modern Approach (Upper Saddle River, NJ: Prentice Hall, 1995, pp. 85ff.).
| CONTENTS | |
EAN: 2147483647
Pages: 18