Re: [xsl] Sudoku stylesheet

Subject: Re: [xsl] Sudoku stylesheet
From: Andrew Franz <afranz0@xxxxxxxxxxxxxxxx>
Date: Tue, 14 Feb 2006 08:14:08 +1100
andrew welch wrote:

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

Both are NP-complete problems ( and should be vulnerable to the same type of solution. I would say that the biggest problem is data/representation.

(I have partially solved it with Excel/VBA using a procedural algorithm)

Current Thread