(NOTE: I've improved on this version
here)
I finally got around to finishing the Sudoku solver after several weeks of other things getting the way.
I've improved the heuristics that check for the allowed values for a given cell. It now checks the row and column "friends" - the other rows and columns in a group (eg columns 1 and 2 when the cell is in column 3, or columns 1 and 3 when the cell is in 2). This is quite straightforward for a human and is done almost without noticing, but its reasonably involved to code.
The other change was to recursively insert all the values into cells with only one possible value, and then re-evaluate the allowed values with those cells inserted. This takes care of the situation where there are initially two possible values, but after inserting a definite value elsewhere there is only one possible values left.
Ultimately all this reduces the number of times the transform has to guess - on certain boards it would take a long time to solve purely because it was guessing wrongly early on, and then have to go through all the permutations before working its way back to that early point and trying the next number. Now there should be the maximum number of values in place before it has to guess (if at all) so that it doesn't waste time backtracking.
Here it is. To try it out run it using Saxon with "-it main" set, or run it against a dummy input XML. The are a few sample boards included, to try them out change the main template to point the variable containing the board, or cut and paste it's contents into the param at the top of the stylesheet.
If you find a board that this stylesheet can't process quickly, please let me know.
<xsl:stylesheet version="2.0"
xmlns:xs="http://www.w3.org/2001/XMLSchema"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:saxon="http://saxon.sf.net/"
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:getRowStart" as="xs:integer+" saxon:memo-function="yes">
<xsl:param name="index" as="xs:integer+"/>
<xsl:sequence select="xs:integer(floor(($index - 1) div 9) * 9) + 1"/>
</xsl:function>
<xsl:function name="fn:getRowNumber" as="xs:integer+" saxon:memo-function="yes">
<xsl:param name="index" as="xs:integer+"/>
<xsl:sequence select="(($index - 1) idiv 9) + 1"/>
</xsl:function>
<xsl:function name="fn:getColNumber" as="xs:integer+" saxon:memo-function="yes">
<xsl:param name="index" as="xs:integer+"/>
<xsl:sequence select="(($index - 1) mod 9) + 1"/>
</xsl:function>
<xsl:function name="fn:getRow" as="xs:integer+">
<xsl:param name="board" as="xs:integer+"/>
<xsl:param name="index" as="xs:integer+"/>
<xsl:sequence select="subsequence($board, fn:getRowStart($index), 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" as="xs:integer"/>
<xsl:variable name="colIndexes" select="for $x in $rowStarts return $x + $gap" as="xs:integer+"/>
<xsl:sequence select="for $x in $colIndexes return $board[$x]"/>
</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="for $x in $topLeftGroup return $board[$x]"/>
</xsl:when>
<xsl:when test="$index = $topGroup">
<xsl:sequence select="for $x in $topGroup return $board[$x]"/>
</xsl:when>
<xsl:when test="$index = $topRightGroup">
<xsl:sequence select="for $x in $topRightGroup return $board[$x]"/>
</xsl:when>
<xsl:when test="$index = $midLeftGroup">
<xsl:sequence select="for $x in $midLeftGroup return $board[$x]"/>
</xsl:when>
<xsl:when test="$index = $center">
<xsl:sequence select="for $x in $center return $board[$x]"/>
</xsl:when>
<xsl:when test="$index = $midRightGroup">
<xsl:sequence select="for $x in $midRightGroup return $board[$x]"/>
</xsl:when>
<xsl:when test="$index = $bottomLeftGroup">
<xsl:sequence select="for $x in $bottomLeftGroup return $board[$x]"/>
</xsl:when>
<xsl:when test="$index = $bottomGroup">
<xsl:sequence select="for $x in $bottomGroup return $board[$x]"/>
</xsl:when>
<xsl:when test="$index = $bottomRightGroup">
<xsl:sequence select="for $x in $bottomRightGroup return $board[$x]"/>
</xsl:when>
</xsl:choose>
</xsl:function>
<xsl:function name="fn:getOtherValuesInTriple" as="xs:integer+" saxon:memo-function="yes">
<xsl:param name="num" as="xs:integer"/>
<xsl:sequence select="(xs:integer(((($num -1) idiv 3) * 3) + 1) to xs:integer(((($num - 1) idiv 3) * 3) + 3))[. != $num]"/>
</xsl:function>
<xsl:function name="fn:getRowFriends" as="xs:integer+">
<xsl:param name="board" as="xs:integer+"/>
<xsl:param name="index" as="xs:integer+"/>
<xsl:sequence select="for $x in fn:getOtherValuesInTriple($index) return $board[$x]"/>
</xsl:function>
<xsl:function name="fn:getColFriends" as="xs:integer+">
<xsl:param name="board" as="xs:integer+"/>
<xsl:param name="index" as="xs:integer+"/>
<xsl:sequence select="for $x in fn:getOtherValuesInTriple(fn:getRowNumber($index))
return
$board[(($x * 9) - 8) + (($index - 1) mod 9)]"/>
</xsl:function>
<xsl:function name="fn:reducePossibleValues" as="xs:integer*">
<xsl:param name="board" as="xs:integer+"/>
<xsl:param name="index" as="xs:integer+"/>
<xsl:param name="possibleValues" as="xs:integer+"/>
<xsl:variable name="rowFriends" select="fn:getRowFriends($board, $index)" as="xs:integer+"/>
<xsl:variable name="colFriends" select="fn:getColFriends($board, $index)" as="xs:integer+"/>
<xsl:variable name="otherRow1" select="fn:getRow($board, 9 * fn:getOtherValuesInTriple(fn:getRowNumber($index))[1])" as="xs:integer+"/>
<xsl:variable name="otherRow2" select="fn:getRow($board, 9 * fn:getOtherValuesInTriple(fn:getRowNumber($index))[2])" as="xs:integer+"/>
<xsl:variable name="otherCol1" select="fn:getCol($board, fn:getOtherValuesInTriple($index)[1])" as="xs:integer+"/>
<xsl:variable name="otherCol2" select="fn:getCol($board, fn:getOtherValuesInTriple($index)[2])" as="xs:integer+"/>
<xsl:variable name="reducedValues" as="xs:integer*">
<xsl:for-each select="$possibleValues">
<xsl:if test=". = $otherCol1 and . = $otherCol2">
<xsl:choose>
<xsl:when test="not($colFriends = 0)">
<xsl:sequence select="."/>
</xsl:when>
<xsl:when test="$colFriends != 0">
<xsl:choose>
<xsl:when test="$colFriends[1] = 0">
<xsl:if test=". = $otherRow1">
<xsl:sequence select="."/>
</xsl:if>
</xsl:when>
<xsl:when test="$colFriends[2] = 0">
<xsl:if test=". = $otherRow2">
<xsl:sequence select="."/>
</xsl:if>
</xsl:when>
</xsl:choose>
</xsl:when>
</xsl:choose>
</xsl:if>
<xsl:if test=". = $otherRow1 and . = $otherRow2">
<xsl:choose>
<xsl:when test="not($rowFriends = 0)">
<xsl:sequence select="."/>
</xsl:when>
<xsl:when test="$rowFriends != 0">
<xsl:choose>
<xsl:when test="$rowFriends[1] = 0">
<xsl:if test=". = $otherCol1">
<xsl:sequence select="."/>
</xsl:if>
</xsl:when>
<xsl:when test="$rowFriends[2] = 0">
<xsl:if test=". = $otherCol2">
<xsl:sequence select="."/>
</xsl:if>
</xsl:when>
</xsl:choose>
</xsl:when>
</xsl:choose>
</xsl:if>
</xsl:for-each>
</xsl:variable>
<xsl:sequence select="if (count($reducedValues) = 1) then $reducedValues else $possibleValues"/>
</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="possibleValues" select="(1 to 9)[not(. = (fn:getRow($board, $index), fn:getCol($board, $index), fn:getGroup($board, $index)))]" as="xs:integer*"/>
<xsl:choose>
<xsl:when test="count($possibleValues) > 1">
<xsl:variable name="reducedValues" select="fn:reducePossibleValues($board, $index, $possibleValues)" as="xs:integer*"/>
<xsl:sequence select="$reducedValues"/>
</xsl:when>
<xsl:otherwise>
<xsl:sequence select="$possibleValues"/>
</xsl:otherwise>
</xsl:choose>
</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="(subsequence($board, 1, $index - 1), $possibleValues[1], subsequence($board, $index + 1))" as="xs:integer+"/>
<xsl:if test="$verbose">
<xsl:message>
<xsl:value-of select="concat('Trying ', $possibleValues[1], ' out of a possible ', string-join(for $i in $possibleValues return xs:string($i), ' '), ' at index ', $index)"/>
</xsl:message>
</xsl:if>
<xsl:variable name="result" select="fn:populateValues($newBoard, subsequence($emptyCells, 2))" as="xs:integer*"/>
<xsl:sequence select="if (empty($result)) then
if (count($possibleValues) > 1) then
fn:tryValues($board, $emptyCells, subsequence($possibleValues, 2))
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="empty($emptyCells)">
<xsl:message>Done!</xsl:message>
<xsl:sequence select="$board"/>
</xsl:when>
<xsl:otherwise>
<xsl:variable name="index" select="$emptyCells[1]" as="xs:integer"/>
<xsl:variable name="possibleValues" select="fn:getAllowedValues($board, $index)" as="xs:integer*"/>
<xsl:choose>
<xsl:when test="count($possibleValues) = 0">
<xsl:if test="$verbose">
<xsl:message>! Cannot go any further !</xsl:message>
</xsl:if>
<xsl:sequence select="()"/>
</xsl:when>
<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="(subsequence($board, 1, $index - 1), $possibleValues[1], subsequence($board, $index + 1))" as="xs:integer+"/>
<xsl:if test="$verbose">
<xsl:message>
<xsl:value-of>
<xsl:text>Only one value </xsl:text>
<xsl:value-of select="$possibleValues[1]"/>
<xsl:text> for index </xsl:text>
<xsl:value-of select="$index"/>
</xsl:value-of>
</xsl:message>
</xsl:if>
<xsl:sequence select="fn:populateValues($newBoard, subsequence($emptyCells, 2))"/>
</xsl:when>
</xsl:choose>
</xsl:otherwise>
</xsl:choose>
</xsl:function>
<xsl:function name="fn:populateSingleValueCells" as="xs:integer+">
<xsl:param name="board" as="xs:integer+"/>
<xsl:param name="emptyCellsXML" as="element()*"/>
<xsl:for-each select="1 to 81">
<xsl:variable name="pos" select="." as="xs:integer"/>
<xsl:choose>
<xsl:when test="$emptyCellsXML[@index = $pos]/@possibleValues = 1">
<xsl:sequence select="$emptyCellsXML[@index = $pos]/@values"/>
</xsl:when>
<xsl:otherwise>
<xsl:sequence select="$board[$pos]"/>
</xsl:otherwise>
</xsl:choose>
</xsl:for-each>
</xsl:function>
<xsl:function name="fn:populateSingleValueCells" as="xs:integer+">
<xsl:param name="board" as="xs:integer+"/>
<xsl:variable name="emptyCells" select="for $x in (1 to 81) return $x[$board[$x] = 0]" as="xs:integer*"/>
<xsl:variable name="emptyCellsXML" as="element()*">
<xsl:for-each select="$emptyCells">
<xsl:variable name="allowedValues" select="fn:getAllowedValues($board, .)" as="xs:integer*"/>
<cell index="{.}" possibleValues="{count($allowedValues)}" values="{$allowedValues}"/>
</xsl:for-each>
</xsl:variable>
<xsl:choose>
<xsl:when test="$emptyCellsXML/@possibleValues = 1">
<xsl:variable name="newBoard" select="fn:populateSingleValueCells($board, $emptyCellsXML)" as="xs:integer+"/>
<xsl:sequence select="fn:populateSingleValueCells($newBoard)"/>
</xsl:when>
<xsl:otherwise>
<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+"/>
<xsl:variable name="board" select="fn:populateSingleValueCells($startBoard)" as="xs:integer+"/>
<xsl:variable name="emptyCells" select="for $x in (1 to 81) return $x[$board[$x] = 0]" as="xs:integer*"/>
<xsl:variable name="emptyCellsXML" as="element()*">
<xsl:for-each select="$emptyCells">
<xsl:variable name="allowedValues" select="fn:getAllowedValues($board, .)" as="xs:integer*"/>
<cell index="{.}" possibleValues="{count($allowedValues)}" values="{$allowedValues}"/>
</xsl:for-each>
</xsl:variable>
<xsl:variable name="emptyCellsOrdered" as="xs:integer*">
<xsl:for-each select="$emptyCellsXML">
<xsl:sort select="@possibleValues" data-type="number" order="ascending"/>
<xsl:sequence select="@index"/>
</xsl:for-each>
</xsl:variable>
<xsl:variable name="endBoard" select="fn:populateValues($board, $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="/tt" name="maintt">
<div>
<xsl:variable name="emptyCellsXML" as="element()*">
<xsl:for-each select="for $x in (1 to 81) return $x[$board[$x] = 0]">
<cell index="{.}" possibleValues="{count(fn:getAllowedValues($board, .))}" values="{fn:getAllowedValues($board, .)}"/>
</xsl:for-each>
</xsl:variable>
<xsl:for-each select="$emptyCellsXML">
<xsl:sort select="@possibleValues" data-type="number" order="ascending"/>
<xsl:copy-of select="."/>
</xsl:for-each>
</div>
</xsl:template>
<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>
<xsl:template name="drawBasicBoard">
<xsl:param name="board" as="xs:integer+"/>
<xsl:for-each select="1 to 9">
<xsl:variable name="i" select="."/>
<xsl:for-each select="1 to 9">
<xsl:variable name="pos" select="(($i - 1) * 9) + ."/>
<xsl:value-of select="$board[$pos]"/>
<xsl:value-of select="if ($pos mod 3 = 0) then ', ' else ', '"/>
</xsl:for-each>
<xsl:value-of select="if ($i mod 3 = 0) then '
' else '
'"/>
</xsl:for-each>
</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+"/>
<!-- Fiendish board -->
<xsl:variable name="testBoard4" select="(
0,0,0, 0,0,5, 0,0,0,
0,0,0, 0,2,0, 9,0,0,
0,8,4, 9,0,0, 7,0,0,
2,0,0, 0,9,0, 4,0,0,
0,3,0, 6,0,2, 0,8,0,
0,0,7, 0,3,0, 0,0,6,
0,0,2, 0,0,9, 8,1,0,
0,0,6, 0,4,0, 0,0,0,
0,0,0, 5,0,0, 0,0,0
)" as="xs:integer+"/>
<!-- Fiendish 2 board -->
<xsl:variable name="testBoard5" select="(
0,0,0, 0,0,5, 1,0,0,
0,3,5, 0,0,0, 0,4,0,
8,0,0, 4,0,0, 0,2,0,
9,0,0, 0,3,0, 5,0,0,
0,0,0, 2,0,8, 0,0,0,
0,0,7, 0,9,0, 0,0,8,
0,5,0, 0,0,9, 0,0,2,
0,4,0, 0,0,0, 9,8,0,
0,0,1, 7,0,0, 0,0,0
)" as="xs:integer+"/>
<xsl:variable name="testBoard_Fiendish_060323" select="(
5,3,0, 0,9,0, 0,0,6,
0,0,0, 1,5,0, 0,0,3,
0,0,2, 0,0,0, 8,0,0,
0,0,0, 0,0,0, 0,8,0,
1,7,0, 0,4,0, 0,2,9,
0,9,0, 0,0,0, 0,0,0,
0,0,6, 0,0,0, 3,0,0,
4,0,0, 0,1,2, 0,0,0,
3,0,0, 0,6,0, 0,5,4
)" as="xs:integer+"/>
<!-- Fiendish 060403-->
<xsl:variable name="testBoard38" select="(
5,0,0, 0,0,1, 0,0,2,
0,6,0, 0,7,0, 0,0,0,
0,0,0, 6,0,0, 8,0,0,
0,0,3, 0,0,5, 0,0,8,
0,9,0, 0,1,0, 0,2,0,
2,0,0, 3,0,0, 7,0,0,
0,0,1, 0,0,2, 0,0,0,
0,0,0, 0,6,0, 0,9,0,
8,0,0, 7,0,0, 0,0,5
)" 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>
