> 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.

> 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) :-)

> 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

Let's step down the algorithm to point out the things we
have to do to work around the limitation I'm pointing.

When you come to the point where you have to use "brute force",
let's say your first emptyCells has (4, 7, 9) as possibleValues.

[...]
fn:populateValues
=> stack params : board
=> stack params : emptyCell
=> stack params : (4,7,9)
=> call fn:tryValues

Now tryValues will try first value (4) and call again
populateValues.
Let's says that it didn't work and you are in a dead end having
tried (4). So populteValues returns with the empty sequence.

You then enter the xsl:choose in your tryValues which calls
itself recursively.

[...]
fn:populateValues
=> stack params : board
=> stack params : emptyCell
=> stack params : (4,7,9)
=> call fn:tryValues
====> stack params : board
====> stack params : emptyCell
====> stack params : (7, 9)
====> call fn:tryValues

The first "try" was a dead end, at this point we know it, but
it is still stacked, and still taking stack/heap space.
The stack space used is useless as, when you will find the
solution, you'll just unstack because you have no other
instructions after your xsl:choose.
[I wonder if any XSL processor would be optimized enough to
free the heap at this point, assuming params go to heap and
it stack pointers. For the stack you are definitely stuck
at least with pointers to {invalid} heap and return address]

Here we don't really care, because we are speaking of stacking
3 sequences of integers, let's say around 1KB of data plus function
call overhead. But if we had bigger recursions this bad construct
will quickly lead to stack-overflow !

If you could have used a for-each, instead of a recurse 1 by 1,
it would have saved stack... and may be time (for your contest)
as stack/heaping sequences and calling is certainly longer
than a test.

While reading your program, I saw a few instructions I were not
familiar with (saxon extensions). Looking at their documentations,
I think I found a workaround to the "useless-stacking-syndrom".

saxon:assignable
saxon:assign

As the documentation says, these extensions "cheat" XSL.
But hey, when there are limitations and the only way is to
"cheat", we might just use them (reasonably)!

<!-- global variable to end recursion -->
<xsl:variable name="theEnd" select="false()" saxon:assignable="yes"/>

<xsl:function name="tryValues">
[snip params]

 <xsl:for-each select="$possibleValues>
   <xsl:if test="not($theEnd)">

   [snip your code]
   [... and no more need to recurse on tryvalues for possibleValues
    here, that's what the for-each does properly, with the
    intial test to stop the unnecessary recursions !]

   </xsl:if>
 </for:each>
</xsl:function>

In the function populateValues, when you found the solution,
you do a saxon:assign to theEnd and set it to true().

Like that you will save a few... nanoseconds !..
Your program will be a little bit easier to read (that's to
my point of view, it might be the contrary for other persons).
On the other hand, your program will now be saxon-dependant.
At the moment, the only saxon extensions you used are just
for optimisations and could be safely removed if you change
your XSL processor (although it will then be much slower).

So, Andrew, if the exact rules of your contest were to be
XSLT2.0-every-processor compliant you are stuck... but if you
were allowed to use whichever XSL processor you like, you might
get a try removing the "useless" recursion, although I'm quite
sure the time difference won't be noticeable at the precision
of your computer's clock !