mersenneforum.org > Math N queens on an N/N board.
 Register FAQ Search Today's Posts Mark Forums Read

 2008-09-19, 06:39 #1 Peter Hackman     Oct 2007 linköping, sweden 22×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.?
2008-09-19, 09:24   #2
ET_
Banned

"Luigi"
Aug 2002
Team Italia

3·5·17·19 Posts

Quote:
 Originally Posted by Peter Hackman 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
 queens.zip (58.5 KB, 177 views)

2008-09-19, 10:42   #3
biwema

Mar 2004

17D16 Posts

Quote:
 Originally Posted by Peter Hackman 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

 2008-09-24, 11:54 #4 Peter Hackman     Oct 2007 linköping, sweden 22×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.
 2008-09-24, 16:34 #5 Peter Hackman     Oct 2007 linköping, sweden 101002 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 2008-09-24 at 16:34

 Similar Threads Thread Thread Starter Forum Replies Last Post Godzilla Combinatorics & Combinatorial Number Theory 3 2017-12-26 15:10 isaac Lounge 7 2014-10-16 20:10 patrik Hardware 2 2004-05-26 14:14 GP2 Lounge 11 2003-10-28 02:36 Prime Monster Lounge 38 2003-05-23 19:14

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

Sun May 29 12:10:08 UTC 2022 up 45 days, 10:11, 0 users, load averages: 1.53, 1.30, 1.33