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

["Dimitre Novatchev" <dnovatchev@xxxxxxxxx>]

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[@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[@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.j.welch@xxxxxxxxx> 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>