Re: A new Sudoku xslt implementation (Was: Re:

On 3/11/06, andrew welch <andrew.j.welch@xxxxxxxxx> wrote:
> > I tested your new stylesheet on the following "fiendish" board, and it
> > performs almost 5 times better than the previous one:
> >
> > <board>
> >   <row>0,0,0,0,0,5,0,0,0</row>
> >   <row>0,0,0,0,2,0,9,0,0</row>
> >   <row>0,8,4,9,0,0,7,0,0</row>
> >   <row>2,0,0,0,9,0,4,0,0</row>
> >   <row>0,3,0,6,0,2,0,8,0</row>
> >   <row>0,0,7,0,3,0,0,0,6</row>
> >   <row>0,0,2,0,0,9,8,1,0</row>
> >   <row>0,0,6,0,4,0,0,0,0</row>
> >   <row>0,0,0,5,0,0,0,0,0</row>
> > </board>
> >
> > The results:
> >
> >   AW1                                AW2
> > =============================
> >
> > 113016    14.8MB        24407    35MB
> >
> >
> > My results on this board are:
> >
> >    6688    10MB
>
> Hi Demitre,
>
> I ran the fiendish board with both stylesheets and have different
> results to you!
>
> I have:
>
> AW1     AW2     DN
> 52.5      10.7      15.75
> 50.5      10.3      15.81
> 49.5      10.5      15.9
>
> The tests were run using SaxonB 8.7 from the command line with the -3
> option to run the transform 3 times.

I've managed to reduce the time to just over the 5 second mark by
processing the center column first, then the sides in the order of
least possible values first.

In the general case, ordering the lot by least possible values first
gives the best overall performance, but in this specific "fiendish"
case not ordering the center column gives the fastest times (something
peculiar to this board I think).

So, using this board:

<!-- Fiendish board -->
<xsl:variable name="testBoard4" select="(
0,0,0,  0,0,5,  0,0,0,
0,0,0,  0,2,0,  9,0,0,
0,8,4,  9,0,0,  7,0,0,

2,0,0,  0,9,0,  4,0,0,
0,3,0,  6,0,2,  0,8,0,
0,0,7,  0,3,0,  0,0,6,

0,0,2,  0,0,9,  8,1,0,
0,0,6,  0,4,0,  0,0,0,
0,0,0,  5,0,0,  0,0,0
)" as="xs:integer+"/>

With this updated function:

<xsl:function name="fn:solveSudoku" as="xs:integer+">
 <xsl:param name="startBoard" as="xs:integer+"/>

 <!-- First process the cells in the center column, then the sides
starting with the
      cells with the least number of options.  This gives much better
performance
      than starting top-left and working from there. -->
 <xsl:variable name="theSides" select="for $x in 1 to 81 return
$x[not($x = $center)][not($x = $topGroup)][not($x = $bottomGroup)]"
as="xs:integer+"/>

 <xsl:variable name="emptyCenterColumnCells" select="for $x in
($topGroup, $center, $bottomGroup) return if ($startBoard[$x] = 0)
then $x else ()" as="xs:integer*"/>
 <xsl:variable name="emptySideCells" select="for $x in ($theSides)
return if ($startBoard[$x] = 0) then $x else ()" as="xs:integer*"/>

 <xsl:variable name="theSidesOrdered" as="xs:integer+">
 	<xsl:for-each select="$emptySideCells">
 	  <xsl:sort select="count(fn:getAllowedValues($startBoard, .))"
data-type="number" order="ascending"/>
 	  <xsl:sequence select="."/>
 	</xsl:for-each>
 </xsl:variable>

 <xsl:variable name="endBoard" select="fn:populateValues($startBoard,
($emptyCenterColumnCells, $theSidesOrdered))" as="xs:integer*"/>

 <xsl:choose>
  <xsl:when test="empty($endBoard)">
   <xsl:message>! Invalid board - The starting board is not
correct</xsl:message>
   <xsl:sequence select="$startBoard"/>
  </xsl:when>
  <xsl:otherwise>
   <xsl:sequence select="$endBoard"/>
  </xsl:otherwise>
 </xsl:choose>
</xsl:function>

Gives these times:

5985
5265
5250

cheers
andrew