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.