xsl-list
[Top] [All Lists]

Re: [xsl] A new Sudoku xslt implementation

2006-03-22 10:20:56
Hello,
   Inspired by the discussion in this thread, I got quite interested
in Sudoku. I developed a  Sudoku solver application written in Java
(sorry no XSLT used here!). I thought of sharing the same with any
interested person. The application is available for download at
http://gandhimukul.tripod.com/sudoku/sudoku.html.

Any suggestions are welcome. Since this mail is not related to XSLT,
you can write to me offline.

Regards,
Mukul

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.


Here's the code I came up with (160 lines vs 214 AW) (no efforts on
optimization were made):


<xsl:stylesheet version="2.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
 xmlns:xs="http://www.w3.org/2001/XMLSchema";
 xmlns:f="http://fxsl.sf.net/";
 exclude-result-prefixes="f xs">

 <xsl:output omit-xml-declaration="yes" indent="yes"/>

 <xsl:template match="/">
  <xsl:sequence
    select="f:sudoku(f:cellsGroup('Fixed', /*/*),
f:cellsGroup('Empty', /*/*))"/>
 </xsl:template>

 <xsl:variable name="vAllVals" select="1 to 9" as="xs:integer+"/>

 <xsl:function name="f:cellsGroup" as="element()*">
  <xsl:param name="pgrpType" as="xs:string"/>
  <xsl:param name="pRows" as="element()*"/>
    <xsl:sequence select=
     "for $i in 1 to count($pRows),
           $vRow in $pRows[$i],
               $vNum in tokenize($vRow, ',')
                          [if($pgrpType='Fixed')
                              then . ne '0'
                              else . eq '0'
                          ][if($pgrpType='Empty')
                              then 1
                              else true()],
               $k in index-of(tokenize($vRow, ','),$vNum)
              return
                f:makeCell($i,$k, xs:integer($vNum))
     "/>
 </xsl:function>

 <xsl:function name="f:makeCell" as="element()">
 <xsl:param name="pnRow" as="xs:integer"/>
 <xsl:param name="pnCol" as="xs:integer"/>
 <xsl:param name="pnVal" as="xs:integer"/>

 <cell row="{$pnRow}" col="{$pnCol}" val="{$pnVal}"/>
 </xsl:function>

 <xsl:function name="f:sudoku" as="item()*">
  <xsl:param name="pFixedCells" as="element()*"/>
  <xsl:param name="pEmptyCells" as="element()*"/>

  <xsl:choose>
   <xsl:when test="empty($pEmptyCells)">
      <xsl:sequence select="f:printBoard($pFixedCells)"/>
   </xsl:when>
   <xsl:otherwise>
      <xsl:variable name="vBestCells" as="element()*"
        select="f:bestCellsToTry($pEmptyCells)"/>
         <xsl:if test="empty($vBestCells[empty(f:fillers($pFixedCells,.))])">
            <xsl:variable name="vBestCell" select="$vBestCells[1]"/>
            <xsl:variable name="vFillers" as="element()+"
                select="f:fillers($pFixedCells,$vBestCell)"/>

          <xsl:sequence select=
            "f:tryFillers($pFixedCells,$pEmptyCells, $vFillers,$vBestCell)"
            />
       </xsl:if>
   </xsl:otherwise>
  </xsl:choose>
 </xsl:function>

 <xsl:function name="f:bestCellsToTry" as="element()*">
  <xsl:param name="pEmptyCells" as="element()*"/>

  <xsl:variable name="vbestRow" as="element()+">
          <xsl:for-each-group select="$pEmptyCells" group-by="@row">
             <xsl:sort select="count(current-group())" order="ascending"/>
             <xsl:sequence select=
                 "if(position() = 1)
                     then current-group()
                     else ()"/>
          </xsl:for-each-group>
  </xsl:variable>
 <!--  Output the resulting cell -->
       <xsl:for-each-group select="$vbestRow"
             group-by="count(f:column($pEmptyCells, current()/@col))">
          <xsl:sort select="current-grouping-key()" order="ascending"/>

          <xsl:sequence select="."/>
        </xsl:for-each-group>
 </xsl:function>

 <xsl:function name="f:fillers" as="element()*">
 <xsl:param name="pFixedCells" as="element()*"/>
 <xsl:param name="pEmptyCell" as="element()"/>

   <xsl:for-each select="$vAllVals">
     <xsl:if test="not(. = f:column($pFixedCells,$pEmptyCell/@col)/@val)
                 and
                   not(. = f:row($pFixedCells,$pEmptyCell/@row)/@val)
                 and
                   not(. = f:region($pFixedCells, $pEmptyCell)/@val)
                  ">
         <xsl:sequence
select="f:makeCell($pEmptyCell/@row,$pEmptyCell/@col,.)"/>
     </xsl:if>
   </xsl:for-each>
 </xsl:function>

 <xsl:function name="f:tryFillers" as="item()*">
 <xsl:param name="pFixedCells" as="element()*"/>
 <xsl:param name="pEmptyCells" as="element()*"/>
 <xsl:param name="pFillers" as="element()*"/>
 <xsl:param name="pBestCell" as="element()"/>

 <xsl:if test="exists($pFillers)">
  <xsl:variable name="vtheFiller" select="$pFillers[1]"/>

  <xsl:variable name="vSolution" select=
  "f:sudoku(($pFixedCells,$vtheFiller),$pEmptyCells[not(. is $pBestCell)])
  "/>

    <xsl:choose>
      <xsl:when test="exists($vSolution)">
          <xsl:sequence select="$vSolution"/>
      </xsl:when>
      <xsl:otherwise>
        <xsl:sequence select=
        "f:tryFillers($pFixedCells,$pEmptyCells, $pFillers[position()
gt 1],$pBestCell)"/>
      </xsl:otherwise>
    </xsl:choose>
 </xsl:if>
 </xsl:function>

 <xsl:function name="f:column" as="element()*">
  <xsl:param name="pCells" as="element()*"/>
  <xsl:param name="pColno" as="xs:integer"/>

  <xsl:sequence select="$pCells[(_at_)col = $pColno]"/>
 </xsl:function>

 <xsl:function name="f:row" as="element()*">
  <xsl:param name="pCells" as="element()*"/>
  <xsl:param name="pRowno" as="xs:integer"/>

  <xsl:sequence select="$pCells[(_at_)row = $pRowno]"/>
 </xsl:function>

 <xsl:function name="f:region" as="element()*">
  <xsl:param name="pCells" as="element()*"/>
  <xsl:param name="paCell" as="element()"/>

  <xsl:variable name="vregRowStart" as="xs:integer"
       select="3*(($paCell/@row -1) idiv 3) +1"/>
  <xsl:variable name="vregColStart" as="xs:integer"
       select="3*(($paCell/@col -1) idiv 3) +1"/>

  <xsl:sequence select=
     "$pCells[xs:integer(@row) ge $vregRowStart and xs:integer(@row)
lt ($vregRowStart +3)
                                   and
                                           xs:integer(@col) ge $vregColStart 
and xs:integer(@col) lt
($vregColStart +3)
             ]"/>
 </xsl:function>

 <xsl:function name="f:printBoard">
 <xsl:param name="pCells" as="element()+"/>

 <xsl:for-each-group select="$pCells" group-by="@row">
   <xsl:sort select="current-grouping-key()"/>
   <row>
      <xsl:for-each select="current-group()">
        <xsl:sort select="@col"/>
        <xsl:value-of select=
         "concat(@val, if(position() ne last()) then ', ' else ())"
         />
      </xsl:for-each>
   </row>
 </xsl:for-each-group>
 </xsl:function>
</xsl:stylesheet>


The input accepted by my implementation is slightly different than the
one used by Andrew Welch. Below is the Suzuki Supereasy 1 board:

<board>
 <row>0,1,6,7,0,3,4,2,0</row>
 <row>5,0,3,8,0,9,6,0,1</row>
 <row>7,4,0,0,0,0,0,3,5</row>
 <row>4,5,0,0,0,0,0,8,6</row>
 <row>0,0,0,0,0,0,0,0,0</row>
 <row>3,7,0,0,0,0,0,9,2</row>
 <row>6,8,0,0,0,0,0,1,9</row>
 <row>2,0,4,1,0,6,3,0,7</row>
 <row>0,3,5,9,0,2,8,6,0</row>
</board>

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





On 2/16/06, andrew welch <andrew(_dot_)j(_dot_)welch(_at_)gmail(_dot_)com> 
wrote:
It took a while but I've finally written a stylesheet that can solve a
Sudoku puzzle...

This stylesheet represents a 9x9 board as 81 integers of 1 to 9, with
zeros for empty cells.  A board can be passed to the stylesheet as a
parameter - there's a default already and I've included some of my
test cases at the bottom as variables (just change the argument in the
solveSudoku() function in the main template to try them).

It works by first narrowing down the possible values for a cell by
checking the existing values in the row, column and group for that
cell.  It then tries each value in the cell until a solution is found
(or all the values have been exhausted, in which case it reports a
broken starting sudoku).

It seems reasonably fast as it is, but I intend to add a few extra
things to make it faster, such as functions that return the other rows
and columns in the group for any index, which will reduce the possible
values further.  Any suggestions for improvements of the algorithm are
welcome.

Thanks to Mike Kay for his Knights Tour stylesheet which was the basis
for solving this problem - a great bit of code.

cheers
andrew

<xsl:stylesheet version="2.0"
xmlns:xs="http://www.w3.org/2001/XMLSchema";
xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
xmlns:fn="sudoku">

<xsl:param name="board" select="(
1,0,0,  3,0,0,  6,0,0,
0,2,0,  5,0,0,  0,0,4,
0,0,9,  0,0,0,  5,2,0,

0,0,0,  9,6,3,  0,0,0,
7,1,6,  0,0,0,  0,0,0,
0,0,0,  0,8,0,  0,4,0,

9,0,0,  0,0,5,  3,0,7,
8,0,0,  4,0,6,  0,0,0,
3,5,0,  0,0,0,  0,0,1
)" as="xs:integer+"/>

<xsl:variable name="rowStarts" select="(1, 10, 19, 28, 37, 46, 55, 64,
73)" as="xs:integer+"/>

<xsl:variable name="topLeftGroup"     select="(1, 2, 3,     10, 11,
12,  19, 20, 21)" as="xs:integer+"/>
<xsl:variable name="topGroup"         select="(4, 5, 6,     13, 14,
15,  22, 23, 24)" as="xs:integer+"/>
<xsl:variable name="topRightGroup"    select="(7, 8, 9,     16, 17,
18,  25, 26, 27)" as="xs:integer+"/>
<xsl:variable name="midLeftGroup"     select="(28, 29, 30,  37, 38,
39,  46, 47, 48)" as="xs:integer+"/>
<xsl:variable name="center"           select="(31, 32, 33,  40, 41,
42,  49, 50, 51)" as="xs:integer+"/>
<xsl:variable name="midRightGroup"    select="(34, 35, 36,  43, 44,
45,  52, 53, 54)" as="xs:integer+"/>
<xsl:variable name="bottomLeftGroup"  select="(55, 56, 57,  64, 65,
66,  73, 74, 75)" as="xs:integer+"/>
<xsl:variable name="bottomGroup"      select="(58, 59, 60,  67, 68,
69,  76, 77, 78)" as="xs:integer+"/>
<xsl:variable name="bottomRightGroup" select="(61, 62, 63,  70, 71,
72,  79, 80, 81)" as="xs:integer+"/>


<xsl:function name="fn:getRow" as="xs:integer+">
       <xsl:param name="board" as="xs:integer+"/>
       <xsl:param name="index" as="xs:integer+"/>
       <xsl:variable name="rowStart" select="floor(($index - 1) div 9) * 
9"/>
       <xsl:sequence select="$board[position() > $rowStart and position()
&lt;= $rowStart + 9]"/>
</xsl:function>

<xsl:function name="fn:getCol" as="xs:integer+">
       <xsl:param name="board" as="xs:integer+"/>
       <xsl:param name="index" as="xs:integer+"/>
       <xsl:variable name="gap" select="($index - 1) mod 9"/>
       <xsl:variable name="colIndexes" select="for $x in $rowStarts return
$x + $gap" as="xs:integer+"/>
       <xsl:sequence select="$board[some $x in position() satisfies $x =
$colIndexes]"/>
</xsl:function>

<xsl:function name="fn:getGroup" as="xs:integer+">
       <xsl:param name="board" as="xs:integer+"/>
       <xsl:param name="index" as="xs:integer+"/>
       <xsl:choose>
               <xsl:when test="$index = $topLeftGroup">
                       <xsl:sequence select="$board[some $x in position() 
satisfies $x =
$topLeftGroup]"/>
               </xsl:when>
               <xsl:when test="$index = $topGroup">
                       <xsl:sequence select="$board[some $x in position() 
satisfies $x =
$topGroup]"/>
               </xsl:when>
               <xsl:when test="$index = $topRightGroup">
                       <xsl:sequence select="$board[some $x in position() 
satisfies $x =
$topRightGroup]"/>
               </xsl:when>
               <xsl:when test="$index = $midLeftGroup">
                       <xsl:sequence select="$board[some $x in position() 
satisfies $x =
$midLeftGroup]"/>
               </xsl:when>
               <xsl:when test="$index = $center">
                       <xsl:sequence select="$board[some $x in position() 
satisfies $x = $center]"/>
               </xsl:when>
               <xsl:when test="$index = $midRightGroup">
                       <xsl:sequence select="$board[some $x in position() 
satisfies $x =
$midRightGroup]"/>
               </xsl:when>
               <xsl:when test="$index = $bottomLeftGroup">
                       <xsl:sequence select="$board[some $x in position() 
satisfies $x =
$bottomLeftGroup]"/>
               </xsl:when>
               <xsl:when test="$index = $bottomGroup">
                       <xsl:sequence select="$board[some $x in position() 
satisfies $x =
$bottomGroup]"/>
               </xsl:when>
               <xsl:when test="$index = $bottomRightGroup">
                       <xsl:sequence select="$board[some $x in position() 
satisfies $x =
$bottomRightGroup]"/>
               </xsl:when>
       </xsl:choose>
</xsl:function>

<xsl:function name="fn:getAllowedValues" as="xs:integer*">
       <xsl:param name="board" as="xs:integer+"/>
       <xsl:param name="index" as="xs:integer+"/>

       <xsl:variable name="existingValues" select="(fn:getRow($board,
$index), fn:getCol($board, $index), fn:getGroup($board, $index))"
as="xs:integer+"/>

       <xsl:sequence select="for $x in (1 to 9) return
                               if (not($x = $existingValues))
                                 then $x
                           else ()"/>
</xsl:function>

<xsl:function name="fn:tryValues" as="xs:integer*">
       <xsl:param name="board" as="xs:integer+"/>
       <xsl:param name="emptyCells" as="xs:integer+"/>
       <xsl:param name="possibleValues" as="xs:integer+"/>

       <xsl:variable name="index" select="$emptyCells[1]" as="xs:integer"/>
       <xsl:variable name="newBoard" select="($board[position() &lt;
$index], $possibleValues[1], $board[position() > $index])"
as="xs:integer+"/>

       <xsl:message>Trying <xsl:value-of select="$possibleValues[1]"/> out
of a possible <xsl:value-of select="$possibleValues"/> at index
<xsl:value-of select="$index"/></xsl:message>

       <xsl:variable name="result" select="fn:populateValues($newBoard,
$emptyCells[position() != 1])" as="xs:integer*"/>

       <xsl:sequence select="if (empty($result)) then
                                                       if 
(count($possibleValues) > 1) then
                                 fn:tryValues($board, $emptyCells,
$possibleValues[position() != 1])
                               else
                                 ()
                         else
                           $result"/>
</xsl:function>

<xsl:function name="fn:populateValues" as="xs:integer*">
       <xsl:param name="board" as="xs:integer+"/>
       <xsl:param name="emptyCells" as="xs:integer*"/>
       <xsl:choose>
               <xsl:when test="not(empty($emptyCells))">
                       <xsl:variable name="index" select="$emptyCells[1]" 
as="xs:integer"/>

                       <xsl:variable name="possibleValues"
select="distinct-values(fn:getAllowedValues($board, $index))"
as="xs:integer*"/>

                       <xsl:choose>
                               <xsl:when test="count($possibleValues) > 1">
                                       <xsl:sequence 
select="fn:tryValues($board, $emptyCells, $possibleValues)"/>
                               </xsl:when>
                               <xsl:when test="count($possibleValues) = 1">
                                       <xsl:variable name="newBoard" 
select="($board[position() &lt;
$index], $possibleValues[1], $board[position() > $index])"
as="xs:integer+"/>
                                       <xsl:message>Only one value 
<xsl:value-of
select="$possibleValues[1]"/> for index <xsl:value-of
select="$index"/></xsl:message>
                                       <xsl:sequence 
select="fn:populateValues($newBoard,
$emptyCells[position() != 1])"/>
                               </xsl:when>
                               <xsl:otherwise>
                                       <xsl:message>! Cannot go any further 
!</xsl:message>
                                       <xsl:sequence select="()"/>
                               </xsl:otherwise>
                       </xsl:choose>

               </xsl:when>
               <xsl:otherwise>
                       <xsl:message>Done!</xsl:message>
                       <xsl:sequence select="$board"/>
               </xsl:otherwise>
       </xsl:choose>
</xsl:function>

<xsl:function name="fn:solveSudoku" as="xs:integer+">
       <xsl:param name="startBoard" as="xs:integer+"/>

       <xsl:variable name="emptyCells" select="for $x in (1 to 81) 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>

<xsl:template match="/" name="main">
       <xsl:call-template name="drawResult">
               <xsl:with-param name="board" 
select="fn:solveSudoku($board)"/>
       </xsl:call-template>
</xsl:template>


<xsl:template name="drawResult">
       <xsl:param name="board" as="xs:integer+"/>
       <html>
               <head>
                       <title>Sudoku - XSLT</title>
                       <style>
                         table { border-collapse: collapse;
                                 border: 1px solid black; }
                         td { padding: 10px; }
                         .norm { border-left: 1px solid #CCC;
                                 border-top: 1px solid #CCC;}
                         .csep { border-left: 1px solid black; }
                         .rsep { border-top: 1px solid black; }
                       </style>
               </head>
               <body>
                       <xsl:call-template name="drawBoard">
                               <xsl:with-param name="board" 
select="$board"/>
                       </xsl:call-template>
               </body>
       </html>
</xsl:template>

<xsl:template name="drawBoard">
       <xsl:param name="board" as="xs:integer+"/>
       <table>
               <xsl:for-each select="1 to 9">
                       <xsl:variable name="i" select="."/>
                               <tr>
                                       <xsl:for-each select="1 to 9">
                                               <xsl:variable name="pos" 
select="(($i - 1) * 9) + ."/>
                                               <td class="{if (position() 
mod 3 = 1) then 'csep' else ('norm')}
{if ($i mod 3 = 1) then 'rsep' else ('norm')}">
                                                       <xsl:value-of 
select="$board[$pos]"/>
                                               </td>
                                       </xsl:for-each>
                               </tr>
               </xsl:for-each>
       </table>
</xsl:template>

<!-- Easy board, 32 existing numbers -->
<xsl:variable name="testBoard1" select="(
0,2,0,  0,0,0,  0,3,6,
0,0,7,  4,0,0,  0,9,0,
0,0,5,  6,0,0,  0,4,8,

0,0,0,  9,3,0,  0,1,2,
2,9,0,  0,0,0,  0,7,5,
1,5,0,  0,8,2,  0,0,0,

6,7,0,  0,0,9,  1,0,0,
0,3,0,  0,0,7,  6,0,0,
4,8,0,  0,0,0,  0,2,0
)" as="xs:integer+"/>

<!-- Hard board, 24 existing numbers -->
<xsl:variable name="testBoard2" select="(
1,0,0,  5,6,0,  0,0,0,
9,0,0,  0,0,0,  2,0,8,
0,0,0,  0,0,0,  7,0,0,

0,8,0,  9,0,7,  0,0,2,
2,0,0,  0,0,0,  0,0,1,
6,0,0,  3,0,2,  0,4,0,

0,0,5,  0,0,0,  0,0,0,
4,0,3,  0,0,0,  0,0,9,
0,0,0,  0,4,1,  0,0,6
)" as="xs:integer+"/>

<!-- Extremely Hard board, 18 existing numbers -->
<xsl:variable name="testBoard3" select="(
0,0,7,  0,0,0,  0,0,8,
0,0,0,  0,9,5,  0,0,0,
0,0,2,  0,0,0,  0,4,0,

0,4,0,  0,0,0,  0,1,0,
5,3,0,  8,0,7,  0,2,6,
0,9,0,  0,0,0,  0,3,0,

0,1,0,  0,0,0,  4,0,0,
0,0,0,  6,2,0,  0,0,0,
3,0,0,  0,0,0,  5,0,0
)" as="xs:integer+"/>

<!-- Failing board, an erroneous 9 has been added at index 1 -->
<xsl:variable name="testBoard_Fail" select="(
9,2,0,  0,0,0,  0,3,6,
0,0,7,  4,0,0,  0,9,0,
0,0,5,  6,0,0,  0,4,8,

0,0,0,  9,3,0,  0,1,2,
2,9,0,  0,0,0,  0,7,5,
1,5,0,  0,8,2,  0,0,0,

6,7,0,  0,0,9,  1,0,0,
0,3,0,  0,0,7,  6,0,0,
4,8,0,  0,0,0,  0,2,0
)" as="xs:integer+"/>
</xsl:stylesheet>

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

<Prev in Thread] Current Thread [Next in Thread>