A common coding problem that people learn to solve is the n-queens problem, the solution involves some backtracking and a clever use of arrays to store state.

What if we want to solve for a larger board, though? For N queens, there are N! ways of placing the queens (notice that an array of queens is enough to represent the state in 2d: each index represents the column, while the value at the index represents the row)

After about 11 or 12 queens, it starts to get pretty expensive to solve the N queens problem and it will take hours to solve a 20 or 30 queens solution.

That’s where min-conflicts comes to the rescue. The Min-Conflicts algorithm is a method of solving problems that runs much faster than backtracking can when the solution space is relatively dense. It works by placing the queens randomly and then finding the queen that is causing the most conflicts and sliding her to the square that minimizes the current number of conflicts. It does this over and over until the board is solved.

Strangely enough, someone on IRC asked how to solve the problem of N queens on a 999x999 board with an extra caveat: no three queens can be co-linear. I spent about two years, off and on, solving this problem and I’m still not completely satisfied with my answer. I use a version of min-conflicts / iterative repair to solve the problem, but it can take a while to solve a 999x999 board and no solution is guaranteed.

Without the co-linearity constraint it goes quite fast. But when accounting for co-linear queens (which reduces the solution density), it takes up to 2 hours.