xsl-list
[Top] [All Lists]

Re: [xsl] A new Sudoku xslt implementation (Was: Re: [xsl] Sudoku - A solution in XSLT 2)

2006-03-11 02:47:15
On 3/11/06, Dimitre Novatchev <dnovatchev(_at_)gmail(_dot_)com> 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

--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--