Re: [xsl] A new Sudoku xslt implementation (Was: Re: [xsl] Sudoku - A solution in XSLT 2)
2006-03-11 09:34:13
On 3/11/06, andrew welch <andrew(_dot_)j(_dot_)welch(_at_)gmail(_dot_)com>
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
--~------------------------------------------------------------------
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>
--~--
|
|