Chess composer Max Bezzel published the eight queens puzzle in 1848. Two years later Franz Nauck published a solution to eight queens and proposed the puzzle N queens. Due to movement complexity of queens, the increased number of required computations as the size of the input increases(time complexity), and the sheer number of possible board states, N queens has been explored by mathematicians and programmers quite extensively. In regards to programming, N queens is useful for testing AI problem solving skills, as well as, a way to test ones ability at creating algorithms that have lower time complexities.
The worst case “brute force” solution for the N-queens puzzle has an O(n^n) time complexity. This means it will look through every position on an NxN board, N times, for N queens. It is by far the slowest and most impractical method. If you refactor and prevent it from checking queens occupying the same row as each other, it will still be brute force, but the possible board states drop from 16,777,216 to a little over 40,000 and has a time complexity of O(n!).
Backtracking is a recursive method which starts a queen at an edge and, ideally, saves the possible attack positions. Then another queen is placed at a safe position…repeat. However, if it is found that N number of queens cannot be placed on that board, it will backtrack and try another safe position. This is over 100 times as fast as brute force and has a time complexity of O(2^n). Some others are even faster. The systematic and greedy search(1000 x faster than the previous) and systematic random permutations(1000 x faster again) both have a O(n^k) or polynomial time complexity. Some algorithms are sub-linear O(n^(1.5)), and an Optimized smart random permutations algorithm(currently in development) is estimated to be linear O(n).
Being fairly new to the world of programming, I believe my first implementation of the N queens algorithm was O(n!). If you are also attempting this for the first time, or are attempting to create any program, just remember to get your MVP(Minimum Viable Product) first, and then concern yourself with time complexity. If you try to optimize and code at the same time, you are probably going to end up making life harder than it needs to be.
The first time I made a binary search tree, I got so caught up in keeping the time complexity at O(log n) that I ended up spending far more time than needed on getting the initial implementation to be functional. I am glad I gained insight on that before attempting N queens. My first N queens may not be pretty, but it is functional. The sample below is the majority of my MVP for my first attempt.
Who knows how far programmers will take N queens? Even now people are seeking linear solutions to this greater than century old puzzle. The practice of refactoring code to have less impact on a system reaches far beyond the bounds of this N queens algorithm, but it is a great look into just how many different paths we can take and still get the answers we seek.
