[djvu9]

I feel nowadays to meaningfully talk about performance of N-queens problem N should start with 18 instead of 8.. Here is a C++ solution with 40 lines of code and can solve 18-queens in less than a minute on a laptop:

https://gist.github.com/jdeng/7915749

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

[shoo]

N = 2 ^ 18 = 262144 queens in less than 6 seconds in a VM on a laptop

its in ~210 lines of C++:

https://bitbucket.org/rfc/dopt_nqueen/src/3e812164d97a8e91d4...

uses random local search approach, as described in russell and norvig (http://aima.cs.berkeley.edu/).

wrote this code during https://www.coursera.org/course/optimization

[IanCal]

Apologies, I'm posting this few times, but 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.

[shoo]

You're correct, i'm merely finding a single feasible solution. Cheers for the link