Re: Sudoku stylesheet

On 2/13/06, Michael Kay <mike@xxxxxxxxxxxx> wrote:

The reason why this is so hard with XSLT is because you can't update
variables, which rules out Backtracking.

No: my knight's tour stylesheet does backtracking quite happily. The two
problems seem conceptually quite similar. The main difficulty in both cases
is that each "move" involves a small change to a fairly large data
structure, which can be quite inefficient since it's likely that the entire
structure will be copied. For this reason in the knight's tour the most
efficient solution was the one that represented the entire board as a single
string value, and I suspect this might also be the most efficient
representation of a SuDoKu board.

You need to have enough stack available to handle the maximum number of
moves recursively, but at 81 that shouldn't be too difficult.

Yes I thought of your Knights Tour stylesheet as I wrote that - the
crucial difference for me is that Backtracking involves unwinding the
stack and carrying on with a different value, whereas in XSLT you
can't unwind the stack - there is no *back* tracking as such - you
just carry on from the same point (which is why you need all that
stack).

I think I have my pedant hat on, with lots of split hairs hanging out
the back....