Editing Eight queens puzzle (section)

==Exercise in algorithm design==
{{original research section|date=December 2024}}
Finding all solutions to the eight queens puzzle is a good example of a simple but nontrivial problem. For this reason, it is often used as an example problem for various programming techniques, including nontraditional approaches such as [[constraint programming]], [[logic programming]] or [[genetic algorithm]]s. Most often, it is used as an example of a problem that can be solved with a [[recursion|recursive]] [[algorithm]], by phrasing the ''n'' queens problem inductively in terms of adding a single queen to any solution to the problem of placing ''n''−1 queens on an ''n''×''n'' chessboard. The [[mathematical induction|induction]] bottoms out with the solution to the 'problem' of placing 0 queens on the chessboard, which is the empty chessboard.

This technique can be used in a way that is much more efficient than the naïve [[brute-force search]] algorithm, which considers all 64<sup>8</sup>&nbsp;=&nbsp;2<sup>48</sup>&nbsp;= 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!&nbsp;= 178,462,987,637,760 possible placements) or in mutually attacking positions. This very poor algorithm will, among other things, produce the same results over and over again in all the different [[permutation]]s of the assignments of the eight queens, as well as repeating the same computations over and over again for the different sub-sets of each solution. A better brute-force algorithm places a single queen on each row, leading to only 8<sup>8</sup>&nbsp;=&nbsp;2<sup>24</sup>&nbsp;= 16,777,216 blind placements.

It is possible to do much better than this.
One algorithm solves the eight [[Rook (chess)|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.
Then it rejects those boards with diagonal attacking positions.

[[Image:Eight-queens-animation.gif|thumb|This animation illustrates [[backtracking]] to solve the problem. A queen is placed in a column that is known not to cause conflict. If a column is not found the program returns to the last good state and then tries a different column.]]
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.
A further improvement, which examines only 5,508 possible queen
placements, is to combine the permutation based method with the early
pruning method: the permutations are generated depth-first, and
the search space is pruned if the [[partial permutation]] produces a
diagonal attack.
[[Constraint programming]] can also be very effective on this problem.

[[File:8queensminconflict.gif|thumbnail|right|[[Min-conflicts algorithm|min-conflicts]] solution to 8 queens]]
An alternative to exhaustive search is an 'iterative repair' algorithm, which typically starts with all queens on the board, for example with one queen per column.<ref>[http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=4DC9292839FE7B1AFABA1EDB8183242C?doi=10.1.1.57.4685&rep=rep1&type=pdf A Polynomial Time Algorithm for the N-Queen Problem] by Rok Sosic and Jun Gu, 1990.  Describes run time for up to 500,000 Queens which was the max they could run due to memory constraints.</ref> It then counts the number of conflicts (attacks), and uses a heuristic to determine how to improve the placement of the queens. The '[[Min-conflicts algorithm|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.<ref>{{Cite journal |last1=Minton |first1=Steven |last2=Johnston |first2=Mark D. |last3=Philips |first3=Andrew B. |last4=Laird |first4=Philip |date=1992-12-01 |title=Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems |url=https://dx.doi.org/10.1016/0004-3702%2892%2990007-K |journal=Artificial Intelligence |language=en |volume=58 |issue=1 |pages=161–205 |doi=10.1016/0004-3702(92)90007-K |s2cid=14830518 |issn=0004-3702|hdl=2060/19930006097 |hdl-access=free }}</ref><ref>{{Cite journal |last1=Sosic |first1=R. |last2=Gu |first2=Jun |date=October 1994 |title=Efficient local search with conflict minimization: a case study of the n-queens problem |url=https://ieeexplore.ieee.org/document/317698 |journal=IEEE Transactions on Knowledge and Data Engineering |volume=6 |issue=5 |pages=661–668 |doi=10.1109/69.317698 |issn=1558-2191}}</ref>

Unlike the backtracking search outlined above, iterative repair does not guarantee a solution: like all [[greedy algorithm|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.

As an alternative to backtracking, solutions can be counted by recursively enumerating valid partial solutions, one row at a time. Rather than constructing entire board positions, blocked diagonals and columns are tracked with bitwise operations. This does not allow the recovery of individual solutions.<ref>{{cite journal|last1=Qiu|first1=Zongyan|title=Bit-vector encoding of n-queen problem|journal=ACM SIGPLAN Notices|date=February 2002|volume=37|issue=2|pages=68–70|doi=10.1145/568600.568613}}</ref><ref>{{cite tech report|first=Martin|last=Richards|title=Backtracking Algorithms in MCPL using Bit Patterns and Recursion|institution=University of Cambridge Computer Laboratory|number=UCAM-CL-TR-433|date=1997|url=http://www.cl.cam.ac.uk/~mr10/backtrk.pdf}}</ref>