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 16:33:53 +0000 |
On 3/11/06, andrew welch <andrew.j.welch@xxxxxxxxx> 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
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] A new Sudoku xslt impleme, Joe Fawcett | Thread | Re: [xsl] A new Sudoku xslt impleme, Dimitre Novatchev |
Re: [xsl] A new Sudoku xslt impleme, Joe Fawcett | Date | Re: [xsl] Advocate for C# .NET + 10, M. David Peterson |
Month |