Re: [xsl] n-queens?

[Hermann Stamm-Wilbrandt <STAMMW@xxxxxxxxxx>]

> 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#post2
2269


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