Dimitre Novatchev's Sudoku solution

The Sudoku solving stylesheet craze has been catching on...

Dimitre Novatchev, creator of FXSL and xsl-list regular, has written a stylesheet (in typical Dimitre style) which attacks the problem from a slightly different angle.

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