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>
--~--