20080919, 06:39  #1 
Oct 2007
linköping, sweden
2^{2}×5 Posts 
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.? 
20080919, 09:24  #2  
Banned
"Luigi"
Aug 2002
Team Italia
3·1,619 Posts 
Quote:
There are lots of programs who deaal with it (one is attached). Try google Jeff Somers too. Luigi 

20080919, 10:42  #3  
Mar 2004
3×127 Posts 
Quote:
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 

20080924, 11:54  #4 
Oct 2007
linköping, sweden
2^{2}×5 Posts 
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. 
20080924, 16:34  #5 
Oct 2007
linköping, sweden
2^{2}×5 Posts 
Don't know really what I meant to say in the last sentence. There are 8 solutions.
Last fiddled with by Peter Hackman on 20080924 at 16:34 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
The Eight Queens problem  Godzilla  Combinatorics & Combinatorial Number Theory  3  20171226 15:10 
back to the drawing board?!  isaac  Lounge  7  20141016 20:10 
New board doesn't fit 1U case  patrik  Hardware  2  20040526 14:14 
This board is ahead of its time  GP2  Lounge  11  20031028 02:36 
Board colors  Prime Monster  Lounge  38  20030523 19:14 