[XSL-LIST Mailing List Archive Home] [By Thread] [By Date]

Re: [xsl] n-queens?


Subject: Re: [xsl] n-queens?
From: "Mark" <mark@xxxxxxxxxxxx>
Date: Mon, 23 Apr 2012 10:04:36 -0700

Very good!

-----Original Message----- From: Hermann Stamm-Wilbrandt
Sent: Monday, April 23, 2012 9:53 AM
To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
Subject: Re: [xsl] n-queens?


So for the first problem the count of all positions with 5, 6 and 7
queens
threatening all fields seem to be what you are interested in, right?

I went ahead and modified n-queens.xsl.xml to solve exactly this problem.

This is the output of  8-queens-maximal.text.xsl.xml:
-----------------------------------------------------
maximal positions                       10188
8-queens solutions                      92
"less than 8"-queens maximal positions  10096
5-queens maximal positions              728
6-queens maximal positions              6912
7-queens maximal positions              2456


Some facts on running this on Thinkpad W520 with 64bit Linux: 1) Opening 8-queens-maximal.text.xsl.xml in a freshly started Firefox (10) just takes 8sec(!) and uses 738MB of resident memory.

Opening 8-queens-maximal.text.xsl.xml in a freshly started Chrome (18)
just takes 5sec(!) and uses 4MB(!!) of resident memory.

2)
The saved file HTML page for 8-queens-maximal.xsl.xml is of size 52.8GB(!).

3)
Just loading 8-queens-maximal.xsl.xml.html into a freshly started Firefox
takes 2:03min and uses 1.8GB of resident memory.

Just loading 8-queens-maximal.xsl.xml.html into a freshly started Chrome
takes 29sec and uses 1.0GB of resident memory.

4)
Opening 8-queens-maximal.xsl.xml in a freshly started Firefox
takes 2:31min and uses 3.2GB of resident memory.

Opening 8-queens-maximal.xsl.xml in a freshly started Google Chrome 18
takes 43sec and uses 1.1GB of resident memory.


These are the links: http://stamm-wilbrandt.de/en/xsl-list/n-queens/8-queens-maximal.text.xsl.xml.html http://stamm-wilbrandt.de/en/xsl-list/n-queens/8-queens-maximal.text.xsl.xml http://stamm-wilbrandt.de/en/xsl-list/n-queens/8-queens-maximal.xsl.xml http://stamm-wilbrandt.de/en/xsl-list/n-queens/8-queens-maximal.zip


And this is what you get in the 554KB .zip file:


$ unzip -l 8-queens-maximal.zip
Archive:  8-queens-maximal.zip
 Length      Date    Time    Name
---------  ---------- -----   ----
   10082  04-23-2012 17:55   8-queens-maximal.text.xsl.xml
     392  04-23-2012 18:07   8-queens-maximal.text.xsl.xml.html
   10056  04-23-2012 18:00   8-queens-maximal.xsl.xml
       0  04-23-2012 18:35   8-queens-maximal.xsl.xml_files/
55334374  04-23-2012 18:36   8-queens-maximal.xsl.xml.html
      97  04-23-2012 18:35   8-queens-maximal.xsl.xml_files/b.gif
     345  04-23-2012 18:35   8-queens-maximal.xsl.xml_files/bqb.gif
     545  04-23-2012 18:35   8-queens-maximal.xsl.xml_files/bqw.gif
      96  04-23-2012 18:35   8-queens-maximal.xsl.xml_files/w.gif
---------                     -------
55355987                     9 files
$


Mit besten Gruessen / Best wishes,


Hermann Stamm-Wilbrandt
Level 3 support for XML Compiler team and Fixpack team lead
WebSphere DataPower SOA Appliances
https://www.ibm.com/developerworks/mydeveloperworks/blogs/HermannSW/
----------------------------------------------------------------------
IBM Deutschland Research & Development GmbH
Vorsitzende des Aufsichtsrats: Martina Koederitz
Geschaeftsfuehrung: Dirk Wittkopp
Sitz der Gesellschaft: Boeblingen
Registergericht: Amtsgericht Stuttgart, HRB 243294



From: Hermann Stamm-Wilbrandt/Germany/IBM@IBMDE

To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx,

Date: 04/23/2012 10:35 AM

Subject: Re: [xsl] n-queens?






This puzzle, although interesting, is commonly given to beginning
programming students.

Yes, but I posted here because of "XSLT 1.0 + exslt:node-set()" solution
and the two questions I have (Muenchian grouping / functional style).

I remember facing it myself. One I have never seen solved
are the number of boards where less than eight queens is the maximum.

Please be more precise on what you count as "a board".
Does the board contain less than 8 queens for your problem?
Or does the board always contain 8 queens, some threatening another?

In the latter case the answer is:
(64 choose 8) - 92 = 4426165368


Long ago I posted some queen-puzzles on a (German language) chess forum. Here you can see a position with 5 queens threatening all fields: http://www.schachmatt.de/69-schachraetsel/2764-3xdamen-uberdeckung.html#post22269


It is not possible to threaten all fields with only 4 queens. So for the first problem the count of all positions with 5, 6 and 7 queens threatening all fields seem to be what you are interested in, right?


Mit besten Gruessen / Best wishes,


Hermann Stamm-Wilbrandt
Level 3 support for XML Compiler team and Fixpack team lead
WebSphere DataPower SOA Appliances
https://www.ibm.com/developerworks/mydeveloperworks/blogs/HermannSW/
----------------------------------------------------------------------
IBM Deutschland Research & Development GmbH
Vorsitzende des Aufsichtsrats: Martina Koederitz
Geschaeftsfuehrung: Dirk Wittkopp
Sitz der Gesellschaft: Boeblingen
Registergericht: Amtsgericht Stuttgart, HRB 243294



From: "Mark" <mark@xxxxxxxxxxxx>


To: <xsl-list@xxxxxxxxxxxxxxxxxxxxxx>,



Date: 04/21/2012 08:25 PM



Subject: Re: [xsl] n-queens?








This puzzle, although interesting, is commonly given to beginning
programming students. I remember facing it myself. One I have never seen
solved are the number of boards where less than eight queens is the
maximum.
Mark

-----Original Message-----
From: Ivan Shmakov
Sent: Saturday, April 21, 2012 8:26 AM
To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
Cc: Ivan Shmakov
Subject: Re: [xsl] n-queens?

Michael Hopwood <michael@xxxxxxxxxxx> writes:

I'm no chess OR maths expert but - surely they are not actually chess
queens if any two of the same colour can threaten each other?  The
puzzle using actual chess queens, at least one of which is of the
other colour, would look quite different...

AIUI, for the purposes of this puzzle, /each/ of the queens is assumed to be of its own distinct colour.

--cut: http://en.wikipedia.org/wiki/Eight_queens_puzzle --
   The eight queens puzzle is the problem of placing eight chess queens
   on an 8W8 chessboard so that no two queens attack each other.  Thus,
   a solution requires that no two queens share the same row, column,
   or diagonal.  The eight queens puzzle is an example of the more
   general n-queens problem of placing n queens on an nWn chessboard,
   where solutions exist for all natural numbers n with the exception
   of 2 and 3.
--cut: http://en.wikipedia.org/wiki/Eight_queens_puzzle --

--
FSF associate member #7257


Current Thread
Keywords
xml