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

On 3/11/06, Dimitre Novatchev <dnovatchev@xxxxxxxxx> wrote:
> Yesterday I bought for my daughter the book
>
>   "IQ Sudoku"  by Yukio Suzuki,
>    http://www.amazon.co.uk/exec/obidos/ASIN/0572032552/203-2606325-8114308
>
> and for the first time was interested in this type of puzzle.
>
> After four hours of fiddling around I came up with a new xslt Sudoku
> implementation. The code is provided at the end of my post.
>
> Here's a short comparison between the implementation of Andrew Welch
> (AW) and this one, performed on 6 differnt board configurations (5
> from AW's xslt implementation plus the first one from the book of
> Suzuki). The two xslt transformations were run using Saxon 8.7 on my
> laptop (Intel Pentium M, 2.13GHz, 2GB). Time is in milliseconds.
>
>
> Board             AW               DN
> ===========================================
> SuperEasy1,  375,  29MB         94,  13.9MB
> Suzuki
>
> AW Easy1    3250,  27MB        360,   4MB
>
> AW Easy2     328,  17.7MB      344,  61MB
>
> AW Hard     6031,  56MB      16853,  63MB
>
> AW Extr.
>    Hard   103303,   3.7MB    10734,  32.6MB
>
> AW Fail.     500,  28MB         94,  13.9MB
>
>
> It seems likely that both implementations could be further improved
> considering what was done better and how in the other implementation.

Hi Dimitre,

I have made a couple of improvements to the version you used there - I
found if you tackle the center cells first, followed by the top-middle
group the time can be greatly reduced.

I've also improved the test boards to be genuinely hard (taken from
the newspaper :)

Use this function instead of the old one to get a better result:

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

 <!-- First process the center cells, then the top, then the rest of the
board.
      This should give better performance than starting top-left and
working from there. -->
 <xsl:variable name="theRest" select="for $x in 1 to 81 return
$x[not($x = $center)][not($x = $topGroup)]" as="xs:integer+"/>

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

 <xsl:variable name="endBoard" select="fn:populateValues($startBoard,
$emptyCells)" 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>


The entire stylesheet can be found at the blog I've started (yesterday):

http://www.ajwelch.blogspot.com/

cheers
andrew