Re: Sudoku stylesheet

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.