[IanCal]

Are you calculating the total number of solutions, or just finding a solution? The latter has a closed form solution: https://gist.github.com/IanCal/1858601

That'll do ~N=1e6 in a second (I'm sure there are lots of optimisations that could be done in it though), or solutions for N=4 to N=1000 in less than 10.

The more complex problem is finding out how many solutions there are in total.

[djvu9]

Counting all the solutions. http://en.wikipedia.org/wiki/Eight_queens_puzzle#Counting_so...

[IanCal]

I can't edit this now, but I just realised it's 1e7, not 1e6 in 1s.