Monday, March 20, 2006

Dimitre's tuned Sudoku solution

Never one to settle for second place Dimitre set about performance tuning his Sudoku solving stylesheet... with dramatic effect.

His latest effort is *blisteringly* fast...

With this board, known as "Fiendish 2" his solution takes just 7.1 seconds. To put that into perspective, my performance tuned implementation takes well over 5 minutes! I'll have to find out why the time is so bad for me...

Here's the "Fiendish 2" board, in the format Dimite's solution requires:



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




Dimitre's stylesheet:



<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:variable name="vFixed" select="f:cellsGroup('Fixed', /*/*)"/>
<xsl:variable name="vEmpty" select="f:cellsGroup('Empty', /*/*)"/>

<xsl:variable name="vallFillers" as="element()*">
<xsl:for-each select=
"f:makeFillers(f:cellsGroup('Fixed', /*/*), f:cellsGroup('Empty', /*/*))">
<xsl:sort select="@row"/>
<xsl:sort select="@col"/>

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


<xsl:sequence
select="f:sudoku($vFixed, $vEmpty, $vallFillers)"/>
</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:param name="pallFillers" as="element()*"/>

<!--
<xsl:message>
f:sudoku:
Fixed: <xsl:sequence select="count($pFixedCells)"/>
Empty: <xsl:sequence select="count($pEmptyCells)"/>
</xsl:message>
-->
<xsl:choose>
<xsl:when test="empty($pEmptyCells)">
<xsl:sequence select="f:printBoard($pFixedCells)"/>
</xsl:when>
<xsl:otherwise>
<xsl:if test="f:canContinue($pFixedCells, $pEmptyCells, $pallFillers)">
<xsl:variable name="vBestCells" as="element()*"
select="f:bestCellsToTry($pEmptyCells,$pallFillers)"/>
<xsl:variable name="vBestCell" select="$vBestCells[1]"/>
<xsl:variable name="vcellFillers" as="element()+"
select="f:cellFillers($pallFillers,$vBestCell)"/>

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

<xsl:function name="f:canContinue" as="xs:boolean">
<xsl:param name="pFixedCells" as="element()*"/>
<xsl:param name="pEmptyCells" as="element()*"/>
<xsl:param name="pallFillers" as="element()*"/>
<xsl:sequence select=
"empty($pEmptyCells[empty(f:cellFillers($pallFillers,.))])"
/>
<!-- -->
</xsl:function>

<xsl:function name="f:cellFillers" as="element()*">
<xsl:param name="pallFillers" as="element()*"/>
<xsl:param name="pemptyCell" as="element()"/>

<xsl:sequence select="$pallFillers[@row eq $pemptyCell/@row
and
@col eq $pemptyCell/@col
]"/>

</xsl:function>

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

<xsl:for-each select="$pEmptyCells">
<xsl:sort select="count(f:cellFillers($pallFillers,.))" order="ascending"/>

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

<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:makeFillers" as="element()*">
<xsl:param name="pFixedCells" as="element()*"/>
<xsl:param name="pEmptyCells" as="element()*"/>

<xsl:sequence select="$pEmptyCells/f:makeFillersForCell($pFixedCells,.)"/>
</xsl:function>

<xsl:function name="f:makeFillersForCell" 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="pallFillers" 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:message>
Trying filler: <xsl:sequence select="$vtheFiller"/>
</xsl:message>
-->
<xsl:variable name="vreducedFilllers" as="element()*"
select="f:reduceAllFillers($pallFillers, $pBestCell,$vtheFiller)"/>
<!--
<xsl:variable name="vmadeFilllers" as="element()*"
select="f:makeFillers(($pFixedCells,$vtheFiller),$pEmptyCells[not(. is $pBestCell)])"/>
<xsl:if test="count($vmadeFilllers) != count($vreducedFilllers)">
<xsl:message>
Problem:
count($vmadeFilllers) = <xsl:value-of select="count($vmadeFilllers)"/>
count($vreducedFilllers) = <xsl:value-of select="count($vreducedFilllers)"/>

madeFillers:
<xsl:copy-of select="$vmadeFilllers"/>

reducedFillers:
<xsl:copy-of select="$vreducedFilllers"/>
</xsl:message>
</xsl:if>
-->
<xsl:variable name="vSolution" select=
"f:sudoku(($pFixedCells,$vtheFiller),$pEmptyCells[not(. is $pBestCell)],
f:reduceAllFillers($pallFillers, $pBestCell,$vtheFiller)
(: f:makeFillers(($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, $pallFillers,
$pFillers[position() gt 1],$pBestCell)"/>
</xsl:otherwise>
</xsl:choose>
</xsl:if>
</xsl:function>

<xsl:function name="f:reduceAllFillers" as="element()*">
<xsl:param name="pallFillers" as="element()*"/>
<xsl:param name="ppickedCell" as="element()"/>
<xsl:param name="pthisFiller" as="element()"/>

<xsl:sequence select=
"$pallFillers[(@row ne $ppickedCell/@row
or
@col ne $ppickedCell/@col
)
and
(
if(@row = $ppickedCell/@row
or
@col = $ppickedCell/@col
or
(
((@row - 1) idiv 3 eq ($ppickedCell/@row -1) idiv 3)
and
((@col - 1) idiv 3 eq ($ppickedCell/@col -1) idiv 3)
)
)
then
@val ne $pthisFiller/@val
else
true()
)
]"
/>
</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...

Hi Andrew,

I have continued working on the Sudoku stylesheet, which now's got up two versions since the one I sent to you and the time of which you measured.

The new stylesheet is about 6 times faster (on difficult puzzles) than the one I gave you last time.

I'll send you this latest stylesheet.

While there's still some space for future optimisations, I have essentially reached my goal -- on my laptop solving any Sudoku puzzle takes less than a second.

It would be interesting to see yet new xslt implementations and I'd also like to invite other people to join in the "Sudoku Frenzy".

Cheers,
Dimitre.