Subject: Re: [xsl] A new Sudoku xslt implementation (Was: Re: [xsl] Sudoku - A solution in XSLT 2) From: "andrew welch" <andrew.j.welch@xxxxxxxxx> Date: Sat, 11 Mar 2006 09:47:00 +0000 |
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
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
[xsl] A new Sudoku xslt implementat, Dimitre Novatchev | Thread | Re: [xsl] A new Sudoku xslt impleme, Dimitre Novatchev |
[xsl] check this out..., Robina Brintha | Date | Re: [xsl] A new Sudoku xslt impleme, Dimitre Novatchev |
Month |