[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

Re:  n-Queens Problem
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>

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]


Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
First Name
Last Name
Subscribe in XML format
RSS 2.0
Atom 0.3

Stylus Studio has published XML-DEV in RSS and ATOM formats, enabling users to easily subcribe to the list from their preferred news reader application.

Stylus Studio Sponsored Links are added links designed to provide related and additional information to the visitors of this website. they were not included by the author in the initial post. To view the content without the Sponsor Links please click here.

Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.