Subject: [xsl] A new Sudoku xslt implementation (Was: Re: [xsl] Sudoku - A solution in XSLT 2) From: "Dimitre Novatchev" <dnovatchev@xxxxxxxxx> Date: Sat, 11 Mar 2006 14:09:12 +1100 |
Yesterday I bought for my daughter the book "IQ Sudoku" by Yukio Suzuki, http://www.amazon.co.uk/exec/obidos/ASIN/0572032552/203-2606325-8114308 and for the first time was interested in this type of puzzle. After four hours of fiddling around I came up with a new xslt Sudoku implementation. The code is provided at the end of my post. Here's a short comparison between the implementation of Andrew Welch (AW) and this one, performed on 6 differnt board configurations (5 from AW's xslt implementation plus the first one from the book of Suzuki). The two xslt transformations were run using Saxon 8.7 on my laptop (Intel Pentium M, 2.13GHz, 2GB). Time is in milliseconds. Board AW DN =========================================== SuperEasy1, 375, 29MB 94, 13.9MB Suzuki AW Easy1 3250, 27MB 360, 4MB AW Easy2 328, 17.7MB 344, 61MB AW Hard 6031, 56MB 16853, 63MB AW Extr. Hard 103303, 3.7MB 10734, 32.6MB AW Fail. 500, 28MB 94, 13.9MB It seems likely that both implementations could be further improved considering what was done better and how in the other implementation. Here's the code I came up with (160 lines vs 214 AW) (no efforts on optimization were made): <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> The input accepted by my implementation is slightly different than the one used by Andrew Welch. Below is the Suzuki Supereasy 1 board: <board> <row>0,1,6,7,0,3,4,2,0</row> <row>5,0,3,8,0,9,6,0,1</row> <row>7,4,0,0,0,0,0,3,5</row> <row>4,5,0,0,0,0,0,8,6</row> <row>0,0,0,0,0,0,0,0,0</row> <row>3,7,0,0,0,0,0,9,2</row> <row>6,8,0,0,0,0,0,1,9</row> <row>2,0,4,1,0,6,3,0,7</row> <row>0,3,5,9,0,2,8,6,0</row> </board> -- Cheers, Dimitre Novatchev --------------------------------------- A writer is a person for whom writing is more difficult than it is for other people. On 2/16/06, andrew welch <andrew.j.welch@xxxxxxxxx> wrote: > 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] Numbering and adding comm, Michael Kay | Thread | Re: [xsl] A new Sudoku xslt impleme, andrew welch |
Re: Re: [xsl] Multiple select listb, mfreeman | Date | [xsl] check this out..., Robina Brintha |
Month |