Subject: Re: [xsl] Sudoku stylesheet From: Andrew Franz <afranz0@xxxxxxxxxxxxxxxx> Date: Tue, 14 Feb 2006 08:14:08 +1100 |
On 2/13/06, Michael Kay <mike@xxxxxxxxxxxx> wrote:Both are NP-complete problems (http://en.wikipedia.org/wiki/Mathematics_of_Sudoku) and should be vulnerable to the same type of solution. I would say that the biggest problem is data/representation.
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....
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Sudoku stylesheet, andrew welch | Thread | Re: [xsl] Sudoku stylesheet, andrew welch |
Re: [xsl] Stumped on XPath, Spencer Tickner | Date | Re: [xsl] Stumped on XPath, Spencer Tickner |
Month |