A couple years ago, I finally solved the n-queens problem with no co-linear queens, but the solution took between 1 - 2 hours for a 999x999 board and wasn’t guaranteed to find a solution.
This week, I revisited the problem with the goal to make the solver run in under 10 minutes. I started by re-working the python solution and profiling it. Within a couple days, I was able to reduce the runtime using a few optimizations:
- Change from using an array of placed elements to a set()
- Use an O(N) solution for counting conflicts for a given queen
- Reduce the calls to check_colinearity by as much as possible
With these optimizations, I was able to solve the problem within 10 - 15 minutes and when lucky, it went down to 8 minutes.
Wanting to do better, I decided to re-write the solution into a compiled language. Having written my own CPY transpiler, I decided to port the code to CPY. It took about a day to re-write from scratch and in the process, I was able to reduce the run-time to below 5 minutes.
The optimizations included:
- re-writing in okp, which is technically just C++
- keeping a data structure to keep track of conflict counts in O(1) time
- further reducing the amount of calls for checking co-linearity
- switching to gp_hash_table instead of unordered_map
- only checking queens that are in danger on each iteration
The solution is about 300 lines of code and the solver runs in 2 - 5 minutes, with an average case of 3 minutes. My next goal (if possible) will to be to reduce the runtime to below 2 minutes.