mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2008-09-19, 06:39   #1
Peter Hackman
 
Peter Hackman's Avatar
 
Oct 2007
linköping, sweden

1416 Posts
Default N queens on an N/N board.

I recently ran a simple program for the N queens problem. 12 queens took minutes, 13 queens took hours, and beyond that I need a couple of friends.
Finding the number of orbits under the full symmetry group then took
no time to speak of, of course.

Just curious whether there is any math in this problem.
For instance, in all the cases known to me (a few more are listed on Wikipedia) it seems that the number of orbits is little more than 1/8 of the number of solutions, and that the quotient gets closer to 1/8 the larger N is. In other words, symmetric solutions are rare. In fact beyond 4 it seemed that no solution possessed more than one symmetry, i.e. solutions symmetric under a
90 degrees rotation do not exist or are at least rare. That even looks like a provable fact.

How much is known regarding asymptotics, existence and/or number of symmetric solutions, etc.?
Peter Hackman is offline   Reply With Quote
Old 2008-09-19, 09:24   #2
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

25×149 Posts
Default

Quote:
Originally Posted by Peter Hackman View Post
I recently ran a simple program for the N queens problem. 12 queens took minutes, 13 queens took hours, and beyond that I need a couple of friends.
Finding the number of orbits under the full symmetry group then took
no time to speak of, of course.

Just curious whether there is any math in this problem.
For instance, in all the cases known to me (a few more are listed on Wikipedia) it seems that the number of orbits is little more than 1/8 of the number of solutions, and that the quotient gets closer to 1/8 the larger N is. In other words, symmetric solutions are rare. In fact beyond 4 it seemed that no solution possessed more than one symmetry, i.e. solutions symmetric under a
90 degrees rotation do not exist or are at least rare. That even looks like a provable fact.

How much is known regarding asymptotics, existence and/or number of symmetric solutions, etc.?
It was one of the problems taught on Algorithms+data structures=prorgams" by Niklaus Wirth when I first saw it.

There are lots of programs who deaal with it (one is attached). Try google Jeff Somers too.

Luigi
Attached Files
File Type: zip queens.zip (58.5 KB, 79 views)
ET_ is online now   Reply With Quote
Old 2008-09-19, 10:42   #3
biwema
 
biwema's Avatar
 
Mar 2004

3×127 Posts
Default

Quote:
Originally Posted by Peter Hackman View Post
How much is known regarding asymptotics, existence and/or number of symmetric solutions, etc.?
Maybe have a look there:

http://www.distributedcomputing.info...s.html#nqueens

http://nqueens.ing.udec.cl/nqueens.php
http://en.wikipedia.org/wiki/N_queens
http://mathworld.wolfram.com/QueensProblem.html
biwema is offline   Reply With Quote
Old 2008-09-24, 11:54   #4
Peter Hackman
 
Peter Hackman's Avatar
 
Oct 2007
linköping, sweden

22×5 Posts
Default

Thanks for the links. Seems I will have to check the references more colsely to find out about the math side of it. The programming part sems to be amply documented. The (naive) Python routine given in Wikipedia is almost the same as mine, but, I believe, a hair slower. I can solve N=12 in 40 seconds, and N=14 in 40 minutes; N=15 requires more storage than I can handle.

I suppose the backtracking idea is superior in dealing with the number of solutions only, as you needn't store the solutions. But that belongs in another forum.

As for symmetries, the first case after N=4, exhibiting 90 degrees symmetries, seems to be N=12 where they come in 8 inverse pairs.
Peter Hackman is offline   Reply With Quote
Old 2008-09-24, 16:34   #5
Peter Hackman
 
Peter Hackman's Avatar
 
Oct 2007
linköping, sweden

101002 Posts
Default

Don't know really what I meant to say in the last sentence. There are 8 solutions.

Last fiddled with by Peter Hackman on 2008-09-24 at 16:34
Peter Hackman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
The Eight Queens problem Godzilla Combinatorics & Combinatorial Number Theory 3 2017-12-26 15:10
back to the drawing board?! isaac Lounge 7 2014-10-16 20:10
New board doesn't fit 1U case patrik Hardware 2 2004-05-26 14:14
This board is ahead of its time GP2 Lounge 11 2003-10-28 02:36
Board colors Prime Monster Lounge 38 2003-05-23 19:14

All times are UTC. The time now is 12:28.

Wed Oct 28 12:28:29 UTC 2020 up 48 days, 9:39, 1 user, load averages: 1.81, 1.77, 1.68

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.