[XSL-LIST Mailing List Archive Home]
[By Thread]
[By Date]
Can solve the N-queens - but can't count!
Subject: Can solve the N-queens - but can't count! From: "Oren Ben-Kiki" <oren@xxxxxxxxxxxxx> Date: Mon, 14 Jun 1999 20:33:58 +0200 |
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. I attach the stylesheet - it is "only" 165 lines long. The input is an XML document of the form: <BoardSize>8</BoardSize> And the output is an HTML document containing all valid chess boards (each a separate HTML table). This seems a silly thing to do, but I found it to be educational, since it uncovered an inherent problem in the XSL no-side-effects-ever approach. I can't count the resulting solutions! Actually, that's not exactly correct; I could do it if I was willing to accept exponentially large template "stack" depth. 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!). Another limitation, one which I managed to work around, was not being able to apply match pattern to tree-valued variables. Instead I used string operations, which is much less elegant. This stylesheet should be interesting for anyone doing XSL benchmarking, or trying to perform all sorts of optimizations on XSL stylesheets. Have fun, Oren Ben-Kiki
Attachment:
queens.xsl
Description: Binary data
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
RE: Node Set and Node List differen, Kay Michael | Thread | RE: Can solve the N-queens - but ca, Kay Michael |
Node Set and Node List differentiat, Gulzar, Nadir | Date | Re: Node Set and Node List differen, Norman Walsh |
Month |