Subject: Re: [xsl] Sudoku stylesheet|
From: andrew welch <andrew.j.welch@xxxxxxxxx>
Date: Thu, 16 Feb 2006 11:57:47 +0000
On 2/13/06, andrew welch <andrew.j.welch@xxxxxxxxx> 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). Hmmm thinking about it I'm wrong to say that. The call stack really does unwind - even for recursive named templates the stack can unwind.