xsl-list
[Top] [All Lists]

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

2006-03-11 03:29:49
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

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




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

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