[XSL-LIST Mailing List Archive Home]
[By Thread]
[By Date]
Re: [xsl] Sudoku - A solution in XSLT 2
Subject: Re: [xsl] Sudoku - A solution in XSLT 2 From: andrew welch <andrew.j.welch@xxxxxxxxx> Date: Wed, 15 Feb 2006 22:18:02 +0000 |
It took a while but I've finally written a stylesheet that can solve a Sudoku puzzle... This stylesheet represents a 9x9 board as 81 integers of 1 to 9, with zeros for empty cells. A board can be passed to the stylesheet as a parameter - there's a default already and I've included some of my test cases at the bottom as variables (just change the argument in the solveSudoku() function in the main template to try them). It works by first narrowing down the possible values for a cell by checking the existing values in the row, column and group for that cell. It then tries each value in the cell until a solution is found (or all the values have been exhausted, in which case it reports a broken starting sudoku). It seems reasonably fast as it is, but I intend to add a few extra things to make it faster, such as functions that return the other rows and columns in the group for any index, which will reduce the possible values further. Any suggestions for improvements of the algorithm are welcome. Thanks to Mike Kay for his Knights Tour stylesheet which was the basis for solving this problem - a great bit of code. cheers andrew <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: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: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: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:message>Only one value <xsl:value-of select="$possibleValues[1]"/> for index <xsl:value-of select="$index"/></xsl:message> <xsl:sequence select="fn:populateValues($newBoard, $emptyCells[position() != 1])"/> </xsl:when> <xsl:otherwise> <xsl:message>! Cannot go any further !</xsl:message> <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+"/> <xsl:variable name="emptyCells" select="for $x in (1 to 81) 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, 18 existing numbers --> <xsl:variable name="testBoard3" select="( 0,0,7, 0,0,0, 0,0,8, 0,0,0, 0,9,5, 0,0,0, 0,0,2, 0,0,0, 0,4,0, 0,4,0, 0,0,0, 0,1,0, 5,3,0, 8,0,7, 0,2,6, 0,9,0, 0,0,0, 0,3,0, 0,1,0, 0,0,0, 4,0,0, 0,0,0, 6,2,0, 0,0,0, 3,0,0, 0,0,0, 5,0,0 )" 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>
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
RE: [xsl] Retrieving data from two , cknell | Thread | Re: [xsl] Sudoku - A solution in XS, Eric Bréchemier |
RE: [xsl] Retrieving data from two , Michael Kay | Date | Re: [xsl] Finding and processing in, David Carlisle |
Month |