[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: n-Queens Problem

• From: u123724 <u123724@gmail.com>
• To: "Costello, Roger L." <costello@mitre.org>
• Date: Sun, 2 Apr 2017 16:02:05 +0200

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@mitre.org> 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>
>
>

• Follow-Ups:
  • Re: n-Queens Problem
    • From: Rick Jelliffe <rjelliffe@allette.com.au>

• References:
  • n-Queens Problem
    • From: "Costello, Roger L." <costello@mitre.org>
  • Re: n-Queens Problem
    • From: David Carlisle <d.p.carlisle@gmail.com>
  • Re: n-Queens Problem
    • From: David Carlisle <d.p.carlisle@gmail.com>
  • RE: n-Queens Problem
    • From: "Costello, Roger L." <costello@mitre.org>