Thursday, March 16, 2006

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>

1 comment:

Dimitre said...

Thanks for publishing my Sudoku XSLT 2.0 implementation.

In the meantime I came up with a second version, in which there's some initial optimization. This runs many times faster and seems to be probably the fastest Sudoku XSLT implementation I am aware of.

I have sent you this new stylesheet with a "fiendish 2" board and would appreciate it very much if you can confirm the new timings.

Thank you for starting this "Sudoku frenzy" -- in it both implementations -- yours and mine have greatly improved. I'd be waiting eagerly your next version.

Cheers,
Dimitre Novatchev