xsl-list
[Top] [All Lists]

Re: [xsl] n-queens?

2012-04-23 11:54:17
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(_at_)lists(_dot_)mulberrytech(_dot_)com,                 
                                                                                
                                                                                
                                                               
  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(_at_)knihtisk(_dot_)org>


  To:         <xsl-list(_at_)lists(_dot_)mulberrytech(_dot_)com>,


  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(_at_)lists(_dot_)mulberrytech(_dot_)com
Cc: Ivan Shmakov
Subject: Re: [xsl] n-queens?

Michael Hopwood <michael(_at_)editeur(_dot_)org> 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 8×8 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 n×n 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

--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--




--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--





--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--





--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--


<Prev in Thread] Current Thread [Next in Thread>