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/