N queens on an N/N board.

[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.?

[ET_]

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

[biwema]

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

[Peter Hackman]

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]

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