Subject: Re: [xsl] Sudoku stylesheet|
From: andrew welch <andrew.j.welch@xxxxxxxxx>
Date: Mon, 13 Feb 2006 15:58:00 +0000
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....