Ian Jones pointed me to an article on javaworld about VTD-XML, which is apparently "A new option that overcomes the problems of DOM and SAX".
It all sounds promising, although the article is light on code examples and heavy on comparisons, so I'll reserve judgement until I've used it. It does seem to concentrate on speed without mentioning conformity, which is not a good sign.
Monday, March 27, 2006
Friday, March 24, 2006
Well when I said "blisteringly fast" I should have said "very fast, but give it a week or two and we'll get faster"...
I've since found a way of improving the performance of my solution... and I think Dimitre has improved his. Watch this space, because neither is quite ready yet. I'll stick my neck out and say once it's done, mine should solve any board pretty much instantly. (I'm going to regret saying that, because mine probably won't but Dimitre's will...)
I've since found a way of improving the performance of my solution... and I think Dimitre has improved his. Watch this space, because neither is quite ready yet. I'll stick my neck out and say once it's done, mine should solve any board pretty much instantly. (I'm going to regret saying that, because mine probably won't but Dimitre's will...)
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:
Dimitre's stylesheet:
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>
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.
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>
Wednesday, March 15, 2006
xq2xml
David Carlisle is currently undertaking a project to convert XQuery expressions into other languages, by first converting the query to XML and then on from there.
The "xq2xml" page can be found at http://monet.nag.co.uk/xq2xml/index.html
His notes on the differences between XQuery and XSLT can be found at http://monet.nag.co.uk/xq2xml/xq2xslnotes.html
It's all very interesting reading, but I kept asking myself "why?" so I mailed him asking if there's a real world application behind all this...
David's reply: "is 'teach myself xquery' a real world application?"
I guess the "because it's there" mentality applies to programming too :)
The "xq2xml" page can be found at http://monet.nag.co.uk/xq2xml/index.html
His notes on the differences between XQuery and XSLT can be found at http://monet.nag.co.uk/xq2xml/xq2xslnotes.html
It's all very interesting reading, but I kept asking myself "why?" so I mailed him asking if there's a real world application behind all this...
David's reply: "is 'teach myself xquery' a real world application?"
I guess the "because it's there" mentality applies to programming too :)
Tuesday, March 14, 2006
David Carlisle's XQuery conversion of the Sudoku stylesheet
After posting the Sudoku stylesheet to xsl-list, David Carlisle mailed me back off-list with the XQuery equivalent, and very fine it is too.
I did start doing some performance comparisons between this and the XSLT 2.0 version, but when the first few results were produced I remembered Saxon compiles much of it into the same internal represenation...
I did start doing some performance comparisons between this and the XSLT 2.0 version, but when the first few results were produced I remembered Saxon compiles much of it into the same internal represenation...
declare namespace fn = "sudoku";
declare variable $board as xs:integer+ := (
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);
declare variable $rowStarts as xs:integer+ := (1, 10, 19, 28, 37, 46, 55, 64,73);
declare variable $groups as xs:integer+ := (
1,1,1, 2,2,2, 3,3,3,
1,1,1, 2,2,2, 3,3,3,
1,1,1, 2,2,2, 3,3,3,
4,4,4, 5,5,5, 6,6,6,
4,4,4, 5,5,5, 6,6,6,
4,4,4, 5,5,5, 6,6,6,
7,7,7, 8,8,8, 9,9,9,
7,7,7, 8,8,8, 9,9,9,
7,7,7, 8,8,8, 9,9,9
);
declare function fn:getRow ($board as xs:integer+, $index as xs:integer) as xs:integer+ {
let $rowStart := floor(($index - 1) div 9) * 9
return
$board[position() > $rowStart and position() <= $rowStart + 9]
};
declare function fn:getCol ($board as xs:integer+, $index as xs:integer) as xs:integer+ {
let $gap := ($index - 1) mod 9,
$colIndexes := for $x in $rowStarts return $x + $gap
return
$board[position() = $colIndexes]};
declare function fn:getGroup ($board as xs:integer+, $index as xs:integer) as xs:integer+ {
let $group := $groups[$index]
return
$board[for $x in position() return $groups[$x]= $group]
};
declare function fn:getAllowedValues ($board as xs:integer+, $index as xs:integer) as xs:integer* {
let $existingValues := (fn:getRow($board,
$index), fn:getCol($board, $index), fn:getGroup($board, $index))
return
for $x in (1 to 9) return
if (not($x = $existingValues))
then $x
else ()
};
declare function fn:tryValues($board as xs:integer+,
$emptyCells as xs:integer+,
$possibleValues as xs:integer+) as xs:integer* {
let $index as xs:integer := $emptyCells[1],
$newBoard as xs:integer+ := ($board[position() <$index],
$possibleValues[1], $board[position() > $index]),
$result as xs:integer* := fn:populateValues($newBoard, $emptyCells[position() != 1])
return
if (empty($result)) then
if (count($possibleValues) > 1) then
fn:tryValues($board, $emptyCells, $possibleValues[position() != 1])
else
()
else
$result
};
declare function fn:populateValues($board as xs:integer+,
$emptyCells as xs:integer*) as xs:integer*{
if (not(empty($emptyCells)))
then
let $index as xs:integer :=$emptyCells[1],
$possibleValues as xs:integer* := distinct-values(fn:getAllowedValues($board, $index))
return
if (count($possibleValues) > 1)
then
fn:tryValues($board, $emptyCells, $possibleValues)
else if (count($possibleValues) = 1)
then
let $newBoard as xs:integer+ :=($board[position() <
$index], $possibleValues[1], $board[position() > $index])
return
fn:populateValues($newBoard, $emptyCells[position() != 1])
else ()
else
$board
};
declare function fn:solveSudoku ($startBoard as xs:integer+) as xs:integer+{
let $emptyCells as xs:integer* :=for $x in (1 to 81) return if
($startBoard[$x] = 0) then $x else (),
$endBoard as xs:integer* :=fn:populateValues($startBoard,$emptyCells)
return
if (empty($endBoard))
then
$startBoard
else
$endBoard};
declare function fn:drawResult ($board as xs:integer+) as element(){
<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>
{fn:drawBoard($board)}
</body>
</html>
};
declare function fn:drawBoard ($board as xs:integer+) as element(){
<table>
{ for $i in 1 to 9
return
<tr>
{for $j at $p in 1 to 9
let $pos := (($i - 1) * 9) + $j
return
<td class="{if ($p mod 3 = 1) then 'csep' else ('norm')}
{if ($i mod 3 = 1) then 'rsep' else ('norm')}">
{$board[$pos]}
</td>
}
</tr>
}
</table>
};
fn:drawResult(fn:solveSudoku($board))
Friday, March 10, 2006
A Sudoku solution in XSLT 2.0
Here's a stylesheet I've written to solve a Sudoku puzzle. It came about when some friends and I were talking about Sudoku over lunch, and one them pointed at me and said "aah I bet XSLT can't do that!" .... which laid down the challenge.
After studying Michael Kay's Knights Tour stylesheet (in the samples directory of the Saxon download) for some time I was able to get going on this. This uses the same recursive technique, trying a particular "route" and then backtracking to the point where a different route can be taken when the last one failed. It uses an intelligent brute force technique (if those aren't mutually exclusive...) - it finds all of the available values for a cell, and then tries each one in turn until the puzzle is solved.
Once the stylesheet was written, it was quite interesting to try out different approaches to get the best performance. For example, the same friend (who reckons he's some kind of Sudoku expert) says that once you have the center squares its just a matter of time before you solve the rest of the board. So instead of just processing the "empty" squares (the zero values here) in the order they appear from 1 to 81, I processed the center squares first followed by the rest. This led to quite an improvement in performance...
It didn't make much sense to sense to then process the empty cells in the top-left group as they aren't affect by the center group, so I modified it to process the center group, then the top-middle group, followed by the rest. This has given the best performance so far...
Anyway, here it is. There are some test boards at the bottom of the stylesheet so just change the parameter value in the main template to use one of them.
<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:param name="verbose" select="false()" as="xs:boolean"/>
<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() <= $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() < $index], $possibleValues[1], $board[position() > $index])" as="xs:integer+"/>
<xsl:if test="$verbose">
<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:if>
<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() < $index], $possibleValues[1], $board[position() > $index])" as="xs:integer+"/>
<xsl:if test="$verbose">
<xsl:message>Only one value
<xsl:value-of select="$possibleValues[1]"/> for index
<xsl:value-of select="$index"/>
</xsl:message>
</xsl:if>
<xsl:sequence select="fn:populateValues($newBoard, $emptyCells[position() != 1])"/>
</xsl:when>
<xsl:otherwise>
<xsl:if test="$verbose">
<xsl:message>! Cannot go any further !</xsl:message>
</xsl:if>
<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+"/>
<!-- First process the center cells, then the top, then the rest of the board.
This should give better performance than starting top-left and working from there. -->
<xsl:variable name="theRest" select="for $x in 1 to 81 return $x[not($x = $center)][not($x = $topGroup)]" as="xs:integer+"/>
<xsl:variable name="emptyCells" select="for $x in ($center, $topGroup, $theRest) 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 -->
<xsl:variable name="testBoard3" select="(
4,0,6, 7,8,0, 2,0,0,
0,5,7, 0,0,0, 0,0,0,
8,0,0, 0,0,0, 4,0,0,
0,0,0, 0,5,0, 0,9,0,
9,1,2, 0,0,0, 0,0,0,
0,4,0, 0,1,0, 0,0,3,
0,0,4, 3,0,0, 0,2,0,
7,0,3, 0,0,6, 0,0,0,
0,0,0, 5,0,7, 6,0,8
)" 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>
Kernow 1.2
I've released Kernow 1.2 which, after fixing a broken zip, is available from http://sourceforge.net/projects/easytransformer/
(It used to be called EasyTransformer, but since it nows supports XQuery and I really didn't like the name Easy.... EZ... eee zee... etc a name change was long overdue).
Kernow is an open source graphical front end for Saxon, the XSLT and XQuery processor. It's written in Java, with the Swing UI created using Matisse - the new UI editor in Netbeans 5. For me eclipse still wins on the IDE front (as it's just better for everyday usage), but Matisse is really special so it's worth putting up with Netbeans just for that.
Kernow basically gives you file choosers for the files involved in the transform, parameter and named template discovery, a caching entity resovler and improved directory transforms through compiling the stylesheet. It also stores all of the files involved and makes them selectable through combo boxes to reduce the amout of setup time when you get going. Hopefully it's useful to someone...
(It used to be called EasyTransformer, but since it nows supports XQuery and I really didn't like the name Easy.... EZ... eee zee... etc a name change was long overdue).
Kernow is an open source graphical front end for Saxon, the XSLT and XQuery processor. It's written in Java, with the Swing UI created using Matisse - the new UI editor in Netbeans 5. For me eclipse still wins on the IDE front (as it's just better for everyday usage), but Matisse is really special so it's worth putting up with Netbeans just for that.
Kernow basically gives you file choosers for the files involved in the transform, parameter and named template discovery, a caching entity resovler and improved directory transforms through compiling the stylesheet. It also stores all of the files involved and makes them selectable through combo boxes to reduce the amout of setup time when you get going. Hopefully it's useful to someone...
Subscribe to:
Posts (Atom)