Eight queens puzzle
In the modern era, it is often used as an example problem for various computer programming techniques.
Although the exact number of solutions is only known for n ≤ 27, the asymptotic growth rate of the number of solutions is approximately (0.143 n)n. Chess composer Max Bezzel published the eight queens puzzle in 1848.
Since then, many mathematicians, including Carl Friedrich Gauss, have worked on both the eight queens puzzle and its generalized n-queens version.
In 1972, Edsger Dijkstra used this problem to illustrate the power of what he called structured programming.
He published a highly detailed description of a depth-first backtracking algorithm.
Solution 10 has the additional property that no three queens are in a straight line.
Brute-force algorithms to count the number of solutions are computationally manageable for n = 8, but would be intractable for problems of n ≥ 20, as 20!
The number of placements in which furthermore no three queens lie on any straight line is known for
Finding all solutions to the eight queens puzzle is a good example of a simple but nontrivial problem.
This technique can be used in a way that is much more efficient than the naïve brute-force search algorithm, which considers all 648 = 248 = 281,474,976,710,656 possible blind placements of eight queens, and then filters these to remove all placements that place two queens either on the same square (leaving only 64!/56!
A better brute-force algorithm places a single queen on each row, leading to only 88 = 224 = 16,777,216 blind placements.
One algorithm solves the eight rooks puzzle by generating the permutations of the numbers 1 through 8 (of which there are 8!
= 40,320), and uses the elements of each permutation as indices to place a queen on each row.
The backtracking depth-first search program, a slight improvement on the permutation method, constructs the search tree by considering one row of the board at a time, eliminating most nonsolution board positions at a very early stage in their construction.
Because it rejects rook and diagonal attacks even on incomplete boards, it examines only 15,720 possible queen placements.
[21] It then counts the number of conflicts (attacks), and uses a heuristic to determine how to improve the placement of the queens.
The 'minimum-conflicts' heuristic – moving the piece with the largest number of conflicts to the square in the same column where the number of conflicts is smallest – is particularly effective: it easily finds a solution to even the 1,000,000 queens problem.
[22][23] Unlike the backtracking search outlined above, iterative repair does not guarantee a solution: like all greedy procedures, it may get stuck on a local optimum.
(In such a case, the algorithm may be restarted with a different initial configuration.)
On the other hand, it can solve problem sizes that are several orders of magnitude beyond the scope of a depth-first search.
Rather than constructing entire board positions, blocked diagonals and columns are tracked with bitwise operations.
By using a coroutine in the form of a generator function, both versions of the original can be unified to compute either one or all of the solutions.
