6 ms·
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 a
by djvu9 13y ago
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 https://gist.github.com/jdeng/7915749
- shoo 13y agoN = 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/3e812164d97a8e91d4d29a007c9060f6c080efab/jungle.cpp?at=master https://bitbucket.org/rfc/dopt_nqueen/src/3e812164d97a8e91d4... uses random local search approach, as described in russell and norvig (http://aima.cs.berkeley.edu/ http://aima.cs.berkeley.edu/). wrote this code during https://www.coursera.org/course/optimization https://www.coursera.org/course/optimization
- IanCal 13y agoApologies, 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 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 13y agoYou're correct, i'm merely finding a single feasible solution. Cheers for the link
- IanCal 13y agoAre 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 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.