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>