N-Queens revision on xt

[Tom Myers <tom.myers@xxxxxxxxxxxxxxxxxxxxxxxxxxx>]

As a maybe-kind-of-silly but certainly fun abuse of xsl, I'd
like to add to the on-and-off N-queens thread begun by Oren 
Ben-Kiki quite some time ago, when he said

>I've written an XSL stylesheet which solves the N queens 
>problem (place N chess queens on an NxN square board so 
>that no queen 
>threatens another), just to see whether it can be done.

and Michael Kay wrote on June 15th

>I've now tried this on some other XSL processors:
>
>SAXON interpreter 76 seconds
>SAXON compiler    21 seconds
>LotusXSL          65 seconds, but appears to produce no output
>xt                15 seconds (by wristwatch)
>infoteria       ~240 seconds, but outputs the first 8x8 board only

The N-queens stylesheet below uses a somewhat different approach,
in a couple of ways...I _think_ it ought to run faster, and it
does the 8 queens (92 solutions) in 6.70 seconds on xt, but I 
can't compare my figures with Michael's because I'm using a 
later version of xt (which won't accept Oren's stylesheet) 
on a different machine...a DellDim 450 running Win98, Java 
1.2.2-W. More interesting for performance testing is that it 
does the 12 queens (14,200 solutions) in 39min,10sec --- the
resulting html page is 1,916KB which I can't open in IE4, but
it looks good (one table with 14200 rows) in the pfe editor.

For those who are interested but haven't thought about it much:
the basic idea is to keep a list of the row you occupy for each
column; for each new column, you check each row 1..N and go
onwards if a queen placed there would not be on a previously 
used row, upwards diagonal or downwards diagonal.
The reason I was expecting it to be faster is that this algorithm
doesn't involve converting substrings back into numbers to see
if one queen threatens another diagonally: instead, I keep a
list of rows-already-used _and_ a list of updiags _and_ a list
of downdiags. As Oren commented, there is some awkwardness in
representing a list of numbers by putting them into a string;
I actually represent (3,12,1) as ",3,12,1," and when searching
to see if (2) is in there, search for ",2,"--otherwise I get
too many matches, too few queens solutions. 

Here's a overview, in which only the first line
generates (one <tr>...</tr> row of) output. "queenstry" is 
essentially a loop which, for each value 1..N, calls queens
recursively if that value is new.
---------------------------------------------------------
queens(lim,list,upd,downd,listlen)=list, if lim=listlen
  =queenstry(1,lim,list,upd,downd,listlen) otherwise

queenstry(val,lim,list,upd,downd,listlen)= "", if val>lim
  =addifnew(val,lim,list,upd,downd,listlen) +
     queenstry(val+1,lim,list,listlen) otherwise.

addifnew(val,lim,list,upd,downd,listlen)="",
               if val in list or udv in upd or ddv in downd
     = queens(lim,list+val+",",
              upd+udv+",",downd+ddv+",",listlen+1) otherwise.
       where udv=val+listlen, ddv=boardsize+val-listlen;
---------------------------------------------------------

There is one other difference: instead of a document specifying
BoardSize, as with the OB-K solution, this one simply uses a top-level
<xsl:param name="boardsize" select="8"/>
and it ignores the document, matching "/". That's because I'm mostly
setting things up with jclark's XSLServlet, calling it, e.g., as

  http://localhost:8080/queens/greeting?boardsize=6

to (ignore the greeting.xml file and) find solutions for size=6;
there are four. 2 4 6 1 3 5, 3 6 2 5 1 4, 4 1 5 2 6 3, 5 3 1 6 4 2 
(That's really one solution with vert, horiz, and vert/horiz reflections.)

Anyway, it works, and it's sufficiently different to be amusing
(I hope), and if you didn't press your delete button yet I'd
love to see comments. 

WARNING. the crucial line is

     test="not(contains($list,$valcomma) or contains($upd,$valup) or
contains($dnd,$valdn))">

which may wrap within email. If you search for "contains" within
the text, you'll get there...it's on the last screen.

Tom Myers   tom.myers@xxxxxxxxxxxxxxxx tommy@xxxxxxxxxxxxxx

---------      queens.xsl begins here   -------------------------
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
                version="1.0">
<!--
    (C) Tom Myers, 11/19/1999  tom.myers@xxxxxxxxxxxxxxxx
    use it freely, tell me if you have ideas for it.
-->
<xsl:output method="html"/>
<xsl:param name="boardsize" select="8"/>

<xsl:template match="/">
  
<html><head><title>N Queens</title></head>
<body>
   <h3>We will now call "queens"</h3>
to generate all solutions of the
<xsl:value-of select="$boardsize"/>-Queens problem.
   <table border="1">
   <xsl:call-template name="queens"/>
   </table>

<xmp>
queens(lim,list,upd,downd,listlen)=list, if lim=listlen
  =queenstry(1,lim,list,upd,downd,listlen) otherwise

queenstry(val,lim,list,upd,downd,listlen)= "", if val<xsl:text
           disable-output-escaping="yes">&gt;</xsl:text>lim
  =addifnew(val,lim,list,upd,downd,listlen) +
     queenstry(val+1,lim,list,listlen) otherwise.

addifnew(val,lim,list,upd,downd,listlen)="",
               if val in list or udv in upd or ddv in downd
     = queens(lim,list+val+",",
              upd+udv+",",downd+ddv+",",listlen+1) otherwise.
       where udv=val+listlen, ddv=boardsize+val-listlen;
</xmp>
In other words,
<p>queens(lim,list,upd,downd,listlen) assumes that "list" is
of length "listlen", with each number followed by a
comma, and the goal of queens is to add to that list
in every possible way to bring it to length "lim"
with numbers no greater than "lim" and without repeats.
</p><p>queenstry(val,lim,list,upd,downd,listlen) will try the
value "val" and all values between it and "lim" in
extending the list.
</p><p>addifnew(val,lim,list,upd,downd,listlen) does nothing
if "val" is already in the list; otherwise adds it
and goes on with "queens" of the longer list.
</p>
</body>
</html>

</xsl:template>

<xsl:template name="queens">
  <xsl:param name="lim" select="$boardsize"/>
  <xsl:param name="list" select="','"/>
  <xsl:param name="upd" select="','"/>
  <xsl:param name="dnd" select="','"/>
  <xsl:param name="listlen" select="0"/>
  <xsl:if test="$lim>$listlen">
    <xsl:call-template name="queenstry">
       <xsl:with-param name="lim" select="$lim"/>
       <xsl:with-param name="list" select="$list"/>
       <xsl:with-param name="upd" select="$upd"/>
       <xsl:with-param name="dnd" select="$dnd"/>
       <xsl:with-param name="listlen" select="$listlen"/>
    </xsl:call-template>
  </xsl:if>
  <xsl:if test="$listlen>=$lim">
    <tr>
    <xsl:call-template name="outperm">
      <xsl:with-param name="list" select="substring($list,2)"/>
    </xsl:call-template>
    </tr>
  </xsl:if>
</xsl:template>

<!-- 
queenstry(val,lim,list,upd,dnd,listlen)= "", if val>lim
  =addifnew(val,lim,list,upd,dnd,listlen) +
     queenstry(val+1,lim,list,upd,dnd,listlen) otherwise.
-->

<xsl:template name="queenstry">
  <xsl:param name="val" select="1"/>
  <xsl:param name="lim" select="$boardsize"/>
  <xsl:param name="list" select="','"/>
  <xsl:param name="upd" select="','"/>
  <xsl:param name="dnd" select="','"/>
  <xsl:param name="listlen" select="0"/>
  <xsl:if test="$lim>=$val" >
    <xsl:call-template name="addifnew">
       <xsl:with-param name="val" select="$val"/>
       <xsl:with-param name="lim" select="$lim"/>
       <xsl:with-param name="list" select="$list"/>
       <xsl:with-param name="upd" select="$upd"/>
       <xsl:with-param name="dnd" select="$dnd"/>
       <xsl:with-param name="listlen" select="$listlen"/>
    </xsl:call-template>
    <xsl:call-template name="queenstry">
       <xsl:with-param name="val" select="1+$val"/>
       <xsl:with-param name="lim" select="$lim"/>
       <xsl:with-param name="list" select="$list"/>
       <xsl:with-param name="upd" select="$upd"/>
       <xsl:with-param name="dnd" select="$dnd"/>
       <xsl:with-param name="listlen" select="$listlen"/>
    </xsl:call-template>
  </xsl:if>
</xsl:template>

<!--
addifnew(val,lim,list,listlen)="", if val in list
     = queens(lim,list+":"+val,listlen+1) otherwise.
-->
<xsl:template name="addifnew">
  <xsl:param name="val" select="1"/>
  <xsl:param name="lim" select="$boardsize"/>
  <xsl:param name="list" select="','"/>
  <xsl:param name="upd" select="','"/>
  <xsl:param name="dnd" select="','"/>
  <xsl:param name="listlen" select="0"/>
  <xsl:variable name="valcomma"
               select="concat(',',$val,',')"/>
  <xsl:variable name="valup"
               select="concat(',',($val+$listlen),',')"/>
  <xsl:variable name="valdn"
               select="concat(',',(($boardsize+$val)-$listlen),',')"/>
  <xsl:if
     test="not(contains($list,$valcomma) or contains($upd,$valup) or
contains($dnd,$valdn))">
    <xsl:call-template name="queens">
       <xsl:with-param name="lim" select="$lim"/>
       <xsl:with-param name="list"
            select="concat($list,substring($valcomma,2))"/>
       <xsl:with-param name="upd"
            select="concat($upd,substring($valup,2))"/>
       <xsl:with-param name="dnd"
            select="concat($dnd,substring($valdn,2))"/>
       <xsl:with-param name="listlen" select="1+$listlen"/>
    </xsl:call-template>
  </xsl:if>    
</xsl:template>

<xsl:template name="outperm">
  <xsl:param name="list" select="''"/>
  <xsl:if test="contains($list,',')">
    <td>
     <xsl:value-of select="substring-before($list,',')"/>
    </td>
    <xsl:call-template name="outperm">
      <xsl:with-param name="list" select="substring-after($list,',')"/>
    </xsl:call-template>
  </xsl:if>
</xsl:template>

</xsl:stylesheet>


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list