Re: [xsl] Sudoku stylesheet

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

Current Thread