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

Re: n-Queens Problem

• From: David Carlisle <d.p.carlisle@gmail.com>
• To: "Costello, Roger L." <costello@mitre.org>
• Date: Sat, 1 Apr 2017 23:49:27 +0100

If you use an easier markup, for example

<n-queens>
 <q c="1" r="3"/>
 <q c="2" r="1"/>
 <q c="3" r="4"/>
 <q c="4" r="2"/>
</n-queens>


which denotes your board with 4 queens in the specified row and
column, then I think the following single xpath works for any size
board and evaluates to true if  every column has a queen, every row
has a queen and the number of distinct  falling and rising diagonals
with a queen equals the number of queens.

<xsl:stylesheet version="2.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">

 <xsl:template match="n-queens">
  <xsl:sequence select="
  (every $c in 1 to count(q) satisfies exists(q[@c=$c])) and
  (every $r in 1 to count(q) satisfies  exists(q[@r=$r])) and
  count(q)=count(distinct-values(q/(number(@r) - number(@c)))) and
  count(q)=count(distinct-values(q/(number(@r) + number(@c))))
   "/>
 </xsl:template>
</xsl:stylesheet>


you could easily make that into a schematron assertion.


On 1 April 2017 at 23:19, David Carlisle <d.p.carlisle@gmail.com> wrote:
>
>>     <column1><row>3</row></column1>
>
> why the horrible asymmetry in the markup, with the column number in the
> element name and the row number in element content?
> That defeats most ways of shortening the schema by exploiting the symmetry
> in the problem.
>
> David

• Follow-Ups:
  • RE: n-Queens Problem
    • From: "Costello, Roger L." <costello@mitre.org>
  • Re: n-Queens Problem
    • From: Thomas Passin <list1@tompassin.net>

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