Subject: Re: Can solve the N-queens - but can't count! From: "Oren Ben-Kiki" <oren@xxxxxxxxxxxxx> Date: Tue, 15 Jun 1999 15:36:25 +0200 |
Kay Michael <Michael.Kay@xxxxxxx> wrote: >I wrote: >> I've written an XSL stylesheet which solves the N queens >> problem (place N chess queens on an NxN square board so that no queen >> threatens another), just to see whether it can be done. > >Brilliant. For the record, it ran first time on SAXON 4.3, in 76 seconds >under the interpreter, and in 21 seconds when compiled. (Pentium II 233MHz, >Win NT 4.0, Sun JDK 1.2) The times I measured so far using XT, are: For 1 queen: 2.48 secs. (1 solution) For 4 queens: 2.60 secs. (2 solutions) For 8 queens: 13 secs. (92 solutions) For 12 queens: 130 minutes. (14200 solutions). For 14 queens: I gave up after 15 hours. I shudder to think of the stack depth in this one :-) Memory consumption was a steady 7-8M. These times are for using XT on a Pentium II 300, running NT 4.0 and Symantec Java 1.1.5 (with JIT). >> Granted that solving the N-queens problem isn't what XSL was >> designed for, but this problem is real. As things stand, one can only >count >> things if they (i) can appear inside a 'count' expression or (ii) if you >are >> willing to accept a nested template call for each increase in the count >(without >> exiting the nested template as long as you need the count!). > >Yes. Functional programming depends on very efficient recursion, and on some >unfamiliar ways of thinking. Actually, the problem is not the functional programming paradigm, just the current XSLT definition. The problem is the weakness of template "return values". It is possible to "return" multiple values from a template by packing them into a string with appropriate seperators, and break them into several variables in the caller. But the moment a template generates a result tree fragment, it is no longer possible for it to "return" anything else - and the fragment is a black box as far as the rest of the templates are concerned. >Those are the two reasons I added an assignment >statement to SAXON! I am not certain an assignment statement is necessary - or sufficient. A much better way (IMVHO) would be to allow applying match patterns to variables. That would remove the need to simulate lists/tuples/arrays/whatever using strings on the one hand, and resolve the problem of multiple fragment return values on the other hand. I also find it to be much more in tune with the "XML spirit" of things. I'm not certain what that would do to XSLT processor implementations, though. On the other hand, I'm all for the addition of a loop construct. Tail recursion is nice, but it only goes so far, and contorting the code to fit around it is not a fun game. The queens code would be more elegant if it could use loops - and probably more efficient, too. That could give SAXON an edge in the benchmark... Share & Enjoy, Oren Ben-Kiki XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
RE: Can solve the N-queens - but ca, Kay Michael | Thread | Re: Can solve the N-queens - but ca, Oren Ben-Kiki |
RE: understanding trees, Kay Michael | Date | apply-templates select question, Hunter, David |
Month |