|
| | | Altova Mailing List Archives>Archive Index >xsl-list Archive Home >Recent entries >Thread Prev - [xsl] Sudoku solver - complete [Thread Next] Re: [xsl] Sudoku solver - completeTo: Date: 5/2/2006 4:00:00 PM Wow...
Congratulations to Andrew for doing a fantastic speedup.
I will use this occasion to give you my latest two solutions
(sudoku4.xsl and sudoku5.xsl). From these the latter is a little bit
more sophisticated and works slightly faster when solving very
difficult boards.
My comparisons of Andrew's latest solution vs the two I provide below,
shows that there are cases where Andrew's solution outperforms mine up
to 4-5 times, other cases where they have the same time and still
other, where the two solutions below are 2-3 times faster.
Clearly, this is a valuable result, because it shows that both
Andrew's and mine sudoku solutions have a significant space for
improvement.
Therefore, wait for the next generation... :o)
I think that at this moment we have already improved our speed
hundreds of times.
Here are my two sudoku solvers:
sudoku4.xsl:
=========
<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:import href="func-apply.xsl"/>
<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:choose>
<xsl:when test="empty($pEmptyCells)">
<xsl:sequence select="f:printBoard($pFixedCells)"/>
</xsl:when>
<xsl:otherwise>
<xsl:variable name="vreducedFillers" select=
"f:reduceFillersByRules($pallFillers)"
/>
<xsl:if test="f:canContinue($pFixedCells, $pEmptyCells,
$vreducedFillers)">
<xsl:variable name="vBestCell" select=
"f:bestCellToTry($pEmptyCells,$vreducedFillers)"/>
<xsl:variable name="vcellFillers" as="element()*"
select="f:cellFillers($vreducedFillers,$vBestCell)"/>
<xsl:sequence select=
"f:tryFillers($pFixedCells,$pEmptyCells, $vreducedFillers,
$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:variable name="vallSingleFillers" as="element()*" select=
"f:getSingleFillers($pallFillers, $pEmptyCells)"
/>
<xsl:sequence select=
"if(empty(
for $i in 1 to 9
return
$i[f:hasDuplicates(
f:row($vallSingleFillers,$i)/@val
)
or
f:hasDuplicates(
f:column($vallSingleFillers,$i)/@val
)
or
f:hasDuplicates(
f:staticRegion($vallSingleFillers,$i)/@val
)
]
)
)
then
true() (:
empty($pEmptyCells[empty(f:cellFillers($pallFillers,.))]) :)
else
false()
"/>
<!-- -->
</xsl:function>
<xsl:function name="f:getSingleFillers" as="element()*">
<xsl:param name="pallFillers" as="element()*"/>
<xsl:param name="pEmptyCells" as="element()*"/>
<xsl:for-each select="$pEmptyCells">
<xsl:variable name="vtheFillers"
select="f:cellFillers($pallFillers,.)"/>
<xsl:sequence select=
"if(not($vtheFillers[2]))
then $vtheFillers[1]
else ()
"
/>
</xsl:for-each>
</xsl:function>
<xsl:function name="f:hasDuplicates" as="xs:boolean">
<xsl:param name="pSeq" as="item()*"/>
<xsl:sequence select="count(distinct-values($pSeq)) ne count($pSeq)"/>
</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:bestCellToTry" as="element()?">
<xsl:param name="pEmptyCells" as="element()*"/>
<xsl:param name="pallFillers" as="element()*"/>
<xsl:for-each-group select="$pEmptyCells"
group-by="count(f:cellFillers($pallFillers,.))">
<xsl:sort select="current-grouping-key()" order="ascending"/>
<xsl:if test="position() = 1">
<xsl:sequence select="current-group()[1]"/>
</xsl:if>
</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:variable name="vreducedFilllers" as="element()*"
select="f:reduceAllFillers($pallFillers, $pBestCell,$vtheFiller)"/>
<xsl:variable name="vSolution" select=
"f:sudoku(($pFixedCells,$vtheFiller),$pEmptyCells[not(. is $pBestCell)],
$vreducedFilllers
)
"/>
<xsl:choose>
<xsl:when test="exists($vSolution)">
<xsl:sequence select="$vSolution"/>
</xsl:when>
<xsl:otherwise>
<xsl:sequence select=
"f:tryFillers($pFixedCells,$pEmptyCells, $pallFillers,
subsequence($pFillers,2),$pBestCell)"/>
</xsl:otherwise>
</xsl:choose>
</xsl:if>
</xsl:function>
<xsl:function name="f:reduceFillersByRules" as="element()*">
<xsl:param name="pFillers" as="element()*"/>
<xsl:variable name="vSingleFillers" as="element()*">
<xsl:for-each select="f:row(), f:column(), f:staticRegion()">
<xsl:variable name="vcurgroupFun" select="."/>
<xsl:for-each select="1 to 9">
<xsl:variable name="vthisGroupFillers"
select="f:apply($vcurgroupFun,$pFillers, .)"/>
<xsl:for-each-group select="$vthisGroupFillers"
group-by="@val"
>
<xsl:sort select="count(current-group())"/>
<xsl:if test="not(current-group()[2])">
<xsl:sequence select="current-group()[1]"/>
</xsl:if>
</xsl:for-each-group>
</xsl:for-each>
</xsl:for-each>
</xsl:variable>
<xsl:sequence select=
"for $filler in $pFillers
return
if(not(exists($vSingleFillers
[not(. is $filler)
and
@row=$filler/@row
and
@col=$filler/@col
]
)
)
)
then $filler
else ()
"/>
</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:variable name="vfunRow" as="element()">
<f:row/>
</xsl:variable>
<xsl:template match="f:row" mode="f:FXSL" as="element()*">
<xsl:param name="arg1" as="element()*"/>
<xsl:param name="arg2" as="xs:integer"/>
<xsl:sequence select="f:row($arg1,$arg2)"/>
</xsl:template>
<xsl:function name="f:row" as="element()">
<xsl:sequence select="$vfunRow"/>
</xsl:function>
<xsl:variable name="vfunColumn" as="element()">
<f:column/>
</xsl:variable>
<xsl:template match="f:column" mode="f:FXSL" as="element()*">
<xsl:param name="arg1" as="element()*"/>
<xsl:param name="arg2" as="xs:integer"/>
<xsl:sequence select="f:column($arg1,$arg2)"/>
</xsl:template>
<xsl:function name="f:column" as="element()">
<xsl:sequence select="$vfunColumn"/>
</xsl:function>
<xsl:variable name="vfunStatRegion" as="element()">
<f:staticRegion/>
</xsl:variable>
<xsl:template match="f:staticRegion" mode="f:FXSL" as="element()*">
<xsl:param name="arg1" as="element()*"/>
<xsl:param name="arg2" as="xs:integer"/>
<xsl:sequence select="f:staticRegion($arg1,$arg2)"/>
</xsl:template>
<xsl:function name="f:staticRegion" as="element()">
<xsl:sequence select="$vfunStatRegion"/>
</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:variable name="vRegdata" as="element()+">
<reg rstart="1" colstart="1"/>
<reg rstart="1" colstart="4"/>
<reg rstart="1" colstart="7"/>
<reg rstart="4" colstart="1"/>
<reg rstart="4" colstart="4"/>
<reg rstart="4" colstart="7"/>
<reg rstart="7" colstart="1"/>
<reg rstart="7" colstart="4"/>
<reg rstart="7" colstart="7"/>
</xsl:variable>
<xsl:function name="f:staticRegion" as="element()*">
<xsl:param name="pCells" as="element()*"/>
<xsl:param name="pRegNo" as="xs:integer"/>
<xsl:variable name="vregRowStart" as="xs:integer?"
select="xs:integer($vRegdata[$pRegNo]/@rstart)"/>
<xsl:variable name="vregColStart" as="xs:integer?"
select="xs:integer($vRegdata[$pRegNo]/@colstart)"/>
<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>
sudoku5.xsl:
=========
<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:import href="func-apply.xsl"/>
<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: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="vBestCell" select=
"f:bestCellToTry($pEmptyCells,$pallFillers)"/>
<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:variable name="vallSingleFillers" as="element()*" select=
"f:getSingleFillers($pallFillers, $pEmptyCells)"
/>
<xsl:sequence select=
"if(empty(
for $i in 1 to 9
return
$i[f:hasDuplicates(
f:row($vallSingleFillers,$i)/@val
)
or
f:hasDuplicates(
f:column($vallSingleFillers,$i)/@val
)
or
f:hasDuplicates(
f:staticRegion($vallSingleFillers,$i)/@val
)
]
)
)
then
true() (:
empty($pEmptyCells[empty(f:cellFillers($pallFillers,.))]) :)
else
false()
"/>
</xsl:function>
<xsl:function name="f:getSingleFillers" as="element()*">
<xsl:param name="pallFillers" as="element()*"/>
<xsl:param name="pEmptyCells" as="element()*"/>
<xsl:for-each select="$pEmptyCells">
<xsl:variable name="vtheFillers"
select="f:cellFillers($pallFillers,.)"/>
<xsl:sequence select=
"if(not($vtheFillers[2]))
then $vtheFillers[1]
else ()
"
/>
</xsl:for-each>
</xsl:function>
<xsl:function name="f:hasDuplicates" as="xs:boolean">
<xsl:param name="pSeq" as="item()*"/>
<xsl:sequence select="count(distinct-values($pSeq)) ne count($pSeq)"/>
</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:bestCellToTry" as="element()?">
<xsl:param name="pEmptyCells" as="element()*"/>
<xsl:param name="pallFillers" as="element()*"/>
<xsl:for-each-group select="$pEmptyCells"
group-by="count(f:cellFillers($pallFillers,.))">
<xsl:sort select="current-grouping-key()" order="ascending"/>
<xsl:if test="position() = 1">
<xsl:sequence select="current-group()[1]"
/>
</xsl:if>
</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:variable name="vreducedFilllers" as="element()*"
select="f:reduceAllFillers($pallFillers, $pBestCell,$vtheFiller)"/>
<xsl:variable name="vreducedFillers2" select=
"f:reduceFillersByRules($vreducedFilllers)"
/>
<xsl:variable name="vSolution" select=
"f:sudoku(($pFixedCells,$vtheFiller),$pEmptyCells[not(. is $pBestCell)],
$vreducedFillers2
)
"/>
<xsl:choose>
<xsl:when test="exists($vSolution)">
<xsl:sequence select="$vSolution"/>
</xsl:when>
<xsl:otherwise>
<xsl:sequence select=
"f:tryFillers($pFixedCells,$pEmptyCells, $pallFillers,
subsequence($pFillers,2),$pBestCell)"/>
</xsl:otherwise>
</xsl:choose>
</xsl:if>
</xsl:function>
<xsl:function name="f:reduceFillersByRules" as="element()*">
<xsl:param name="pFillers" as="element()*"/>
<!--f:reduceAllFillers($pallFillers, $pBestCell,$vtheFiller) -->
<xsl:variable name="vSingleValueFillers" as="element()*">
<xsl:for-each select="f:row(), f:column(), f:staticRegion()">
<xsl:variable name="vcurgroupFun" select="."/>
<xsl:for-each select="1 to 9">
<xsl:variable name="vthisGroupFillers"
select="f:apply($vcurgroupFun,$pFillers, .)"/>
<xsl:for-each-group select="$vthisGroupFillers"
group-by="@val"
>
<xsl:sort select="count(current-group())"/>
<xsl:if test="not(current-group()[2])">
<xsl:sequence select="current-group()[1]"/>
</xsl:if>
</xsl:for-each-group>
</xsl:for-each>
</xsl:for-each>
</xsl:variable>
<xsl:variable name="vreducedFillers2" as="element()*"
select=
"for $filler in $pFillers
return
if(not(exists($vSingleValueFillers
[not(. is $filler)
and
@row=$filler/@row
and
@col=$filler/@col
]
)
)
)
then $filler
else ()
"/>
<xsl:sequence select="$vreducedFillers2"/>
<!--
<xsl:variable name="vSingleFillers" as="element()*">
<xsl:for-each-group select="$vreducedFillers2"
group-by="concat(@row,@col)"
>
<xsl:sequence select=
"if(not(current-group()[2]))
then current-group()[1]
else ()
"/>
</xsl:for-each-group>
</xsl:variable>
<xsl:variable name="vreducedFillers1" as="element()*"
select=
"for $filler in $vreducedFillers2
return
if(not(exists($vSingleFillers
[not(. is $filler)
and
@val = $filler/@val
and
(@row=$filler/@row
or
@col=$filler/@col
or
( ((@row -1) idiv 3 eq ($filler/@row -1) idiv 3)
and
((@col -1) idiv 3 eq ($filler/@col -1) idiv 3)
)
)
]
)
)
)
then $filler
else ()
"
/>
<xsl:sequence select="$vreducedFillers1"/>
-->
<!--
<xsl:sequence select=
"if(count($vreducedFillers2) eq count($pFillers))
then
$vreducedFillers2
else
f:reduceFillersByRules($vreducedFillers2)
"
/>
-->
</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:variable name="vfunRow" as="element()">
<f:row/>
</xsl:variable>
<xsl:template match="f:row" mode="f:FXSL" as="element()*">
<xsl:param name="arg1" as="element()*"/>
<xsl:param name="arg2" as="xs:integer"/>
<xsl:sequence select="f:row($arg1,$arg2)"/>
</xsl:template>
<xsl:function name="f:row" as="element()">
<xsl:sequence select="$vfunRow"/>
</xsl:function>
<xsl:variable name="vfunColumn" as="element()">
<f:column/>
</xsl:variable>
<xsl:template match="f:column" mode="f:FXSL" as="element()*">
<xsl:param name="arg1" as="element()*"/>
<xsl:param name="arg2" as="xs:integer"/>
<xsl:sequence select="f:column($arg1,$arg2)"/>
</xsl:template>
<xsl:function name="f:column" as="element()">
<xsl:sequence select="$vfunColumn"/>
</xsl:function>
<xsl:variable name="vfunStatRegion" as="element()">
<f:staticRegion/>
</xsl:variable>
<xsl:template match="f:staticRegion" mode="f:FXSL" as="element()*">
<xsl:param name="arg1" as="element()*"/>
<xsl:param name="arg2" as="xs:integer"/>
<xsl:sequence select="f:staticRegion($arg1,$arg2)"/>
</xsl:template>
<xsl:function name="f:staticRegion" as="element()">
<xsl:sequence select="$vfunStatRegion"/>
</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:variable name="vRegdata" as="element()+">
<reg rstart="1" colstart="1"/>
<reg rstart="1" colstart="4"/>
<reg rstart="1" colstart="7"/>
<reg rstart="4" colstart="1"/>
<reg rstart="4" colstart="4"/>
<reg rstart="4" colstart="7"/>
<reg rstart="7" colstart="1"/>
<reg rstart="7" colstart="4"/>
<reg rstart="7" colstart="7"/>
</xsl:variable>
<xsl:function name="f:staticRegion" as="element()*">
<xsl:param name="pCells" as="element()*"/>
<xsl:param name="pRegNo" as="xs:integer"/>
<xsl:variable name="vregRowStart" as="xs:integer?"
select="xs:integer($vRegdata[$pRegNo]/@rstart)"/>
<xsl:variable name="vregColStart" as="xs:integer?"
select="xs:integer($vRegdata[$pRegNo]/@colstart)"/>
<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>
--
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
On 5/2/06, andrew welch <andrew.j.welch@xxxxxxxxx> wrote:
For those of you interested in this I've now finished performance
tuning my Sudoku solution.
I'm quite pleased with it - boards that were taking 15mins+ now take
less than a few seconds. The most pleasing aspect is the way it
selects the allowed values for a cell - it's much better at detecting
when there's only one possible value, and the way it works through the
board.
I'm also making much more use of subsequence() - several seconds were
shaved off after constructing new sequences from existings sequences
using this function.
I'm satisfied that it's complete now, but if anyone can improve it or
break it, please let me know
It's available here: http://ajwelch.blogspot.com/
cheers
andrew | |
| | ||||||||
| Company | Legal | Press | Partners | Careers | Sitemap | Contact Us | Altova Blog | Mobile | Full Site | |||
|
