Cart
[Home] [By Thread] [By Date] [Recent Entries]
A solution to the N-queens problem in XSLT was discussed on this
mailing list as early as 1999 ("Can solve the N-queens - but can't count!"
cf. https://www.oxygenxml.com/archives/xsl-list/199906/msg00289.html)
in the context of XSLT language design.
Now and then, the question for document query and validation languages
was to strike a balance between decidability, complexity (Big-O)
and power. Traditionally, it was consensus that schema languages
shouldn't be undecidable. That is, the problem to determine if there is a
document that satisfies all the constraints the validation language
can express should be solvable, and moreover should be solvable in
time and space bounded by a polynomial in terms of the input problem's
eg. symbol length.
So while being able to check the N-queens constraints is nice, it hints at
the fact that Schematron is leaning on the "too powerful to be useful" side
of things as a validation language. But note that already XML Schema is
undecidable because of eg. interaction with identity constraints and
occurence indicators if I recall correctly; http://www.unidex.com/scp/
links to these results and also contains a proof of Schematron
undecidablity. Notably, only DTDs (and possibly Relax NG) are considered
decidable according to it.
On Sun, Apr 2, 2017 at 3:12 PM, Costello, Roger L. <costello@m...> wrote:
> David Carlisle wrote a very cool:
>
>
>
> … solution that works for
> any size chessboard …
>
>
>
> Thank you David!
>
>
>
> Here is how David models the chessboard:
>
>
>
> <n-queens>
> <queen column="1" row="3"/>
> <queen column="2" row="1"/>
> <queen column="3" row="4"/>
> <queen column="4" row="2"/>
> </n-queens>
>
>
>
> And here is his (mind-blowing) Schematron schema:
>
>
>
> <sch:schema xmlns:sch="http://purl.oclc.org/dsdl/schematron"
> queryBinding="xslt2">
>
> <sch:pattern id="n-Queens-Problem">
>
> <sch:rule context="n-queens">
> <sch:assert test="every $c in 1 to count(queen) satisfies
> exists(queen[@column=$c])">
> There cannot be two queens in the same column.
> </sch:assert>
> <sch:assert test="every $r in 1 to count(queen) satisfies
> exists(queen[@row=$r])">
> There cannot be two queens on the same row.
> </sch:assert>
> <sch:assert
> test="count(queen)=count(distinct-values(queen/(number(@row) -
> number(@column))))">
> There cannot be two queens on a (falling) diagonal.
> </sch:assert>
> <sch:assert
> test="count(queen)=count(distinct-values(queen/(number(@row) +
> number(@column))))">
> There cannot be two queens on a (rising) diagonal.
> </sch:assert>
> </sch:rule>
> </sch:pattern>
>
> </sch:schema>
>
>
[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] |
