Subject: Re: [xsl] [XSL] Accessing part of the result tree illustrated with "The Sudoku solver" example. From: "Andrew Welch" <andrew.j.welch@xxxxxxxxx> Date: Tue, 4 Sep 2007 09:26:18 +0100 |
On 9/4/07, Alain <alainb06@xxxxxxx> wrote: > I think there's a "missing feature" in XSL (or I just haven't found it) > when you do recursing programs, but I would appreciate your point of > view of experts and W3C members. [snip] > Well, don't tell me it is a bad algorithm, I know it ! It is just "brute > force". We recurse on the empty elements and try every possible value > that fits in that element up to the point where all the elements have a > value matching the Sudoku rules (or no solution if your initial input is > incorrect). > > Abel, you were right, it is so graceful ending a recursion without a bad > looking xsl:if (prioritized template do the job) :-) [snip] > You had the "fun" part, now comes the question. > > > A naive reader might say this algorithm is cool because it gives a > solution. Although depending on the initial values you enter and the > speed of your computer it might run from a few seconds to many minutes. > > But experts as you are, you would have noticed that there is a major > BUG: even when we have found the solution, the recursion continues!.. > So you can get "lucky" and find a solution in the first seconds, then > run for many minutes uselessly just terminating the recursion. Have a look at: http://andrewjwelch.com/code/xslt/sudoku/sudoku-solver.html This is the sudoku solver I wrote in XSLT 2.0. It uses the various techniques humans use to solve the puzzle before resorting to brute force - even on the hardest puzzles there's usually only a choice of two values at that point. On my machine in can solves all puzzles in under a second, which was the long term goal when Dimitre and I started competing [1] (as you probably know basic backtracking solutions can be extremely fast for one puzzle, and unbelievably slow for another) Anyway, the end of the recursion in my solution is when either the board has no empty cells left (it's solved) or the are no possible values left for a given cell. [1] http://ajwelch.blogspot.com/2007/06/sukoku-solver-much-improved.html -- Andrew Welch http://andrewjwelch.com Kernow: http://kernowforsaxon.sf.net/
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
[xsl] [XSL] Accessing part of the r, Alain | Thread | RE: [xsl] [XSL] Accessing part of t, Michael Kay |
Re: [xsl]Putting Mouseover Javascri, Ronan Klyne | Date | Re: [xsl]Putting Mouseover Javascri, David Carlisle |
Month |