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

Re: n-Queens Problem

  • From: Rick Jelliffe <rjelliffe@allette.com.au>
  • To: u123724 <u123724@gmail.com>
  • Date: Mon, 3 Apr 2017 15:47:33 +1000

Re:  n-Queens Problem
Another approach, using David's markup, is to allow the rule/@context to do the work of the iteration. This way, you get a message on the queen in question, which is more useful for locating the problem, at the cost of probably re-visiting nodes, unless there is some memoization going on.

Also, I am using sch:report so that it matches the text, which is saying what should not be, rather asserting what should be. Note that (assuming it works...untested...) This only uses XSLT1 XPath, too.

<sch:schema xmlns:sch="http://purl.oclc.org/dsdl/schematron" 
<sch:pattern id="n-Queens-Problem">
<sch:rule context="queen">

<sch:report test="@column = following-sibling::queen/@column">
                There cannot be two queens in the same column.
<sch:report test="@row = following-sibling::queen/@row">
                There cannot be two queens on the same row.
<sch:report  test="following-sibling::queen [(@row - @column) = (current ()/@row - @current ()/@column) ]">
                There cannot be two queens on a (falling) diagonal.
<sch:report test="following-sibling::queen [(@row + @column) = (current ()/@row + @current ()/@column) ]">
                There cannot be two queens on a (rising) diagonal.


On 3 Apr 2017 00:02, "u123724" <u123724@gmail.com> wrote:
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>


XML-DEV is a publicly archived, unmoderated list hosted by OASIS
to support XML implementation and development. To minimize
spam in the archives, you must subscribe before posting.

[Un]Subscribe/change address: http://www.oasis-open.org/mlmanage/
Or unsubscribe: xml-dev-unsubscribe@lists.xml.org
subscribe: xml-dev-subscribe@lists.xml.org
List archive: http://lists.xml.org/archives/xml-dev/
List Guidelines: http://www.oasis-open.org/maillists/guidelines.php

[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.