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

["Dimitre Novatchev" <dnovatchev@xxxxxxxxx>]

Hi Andrew,



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


That's good news!

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


The fiendish board can be found here:

    http://www.fiendishsudoku.com/sudoku.html


It's great you've started a blog!  Can you publish there some of the
most interesting and hardest board configuarations you're dealing
with?


Cheers,
Dimitre.



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


--
Cheers,
Dimitre Novatchev
---------------------------------------
A writer is a person for whom writing is more difficult than it is for
other people.