Editing Eight queens puzzle (section)

==Existence of solutions==

Brute-force algorithms to count the number of solutions are computationally manageable for {{math|1=''n''&nbsp;=&nbsp;8}}, but would be intractable for problems of {{math|1=''n''&nbsp;≥&nbsp;20}}, as 20! = 2.433 × 10<sup>18</sup>.  If the goal is to find a single solution, one can show solutions exist for all ''n'' ≥ 4 with no search whatsoever.<ref name=bernhardsson>{{cite journal |author=Bo Bernhardsson |date=1991 |title=Explicit Solutions to the N-Queens Problem for All N |journal=ACM SIGART Bulletin |volume=2 |issue=2 |pages=7 |doi=10.1145/122319.122322|s2cid=10644706 }}</ref><ref>{{Cite journal |last1=Hoffman |first1=E. J. |last2=Loessi |first2=J. C. |last3=Moore |first3=R. C. |date=1969-03-01 |title=Constructions for the Solution of the m Queens Problem |url=http://www.jstor.org/stable/2689192 |journal=Mathematics Magazine |language=en |volume=42 |issue=2 |pages=66 |doi=10.2307/2689192|jstor=2689192 }} {{Webarchive|url=https://web.archive.org/web/20161108102345/http://penguin.ewu.edu/~trolfe/QueenLasVegas/Hoffman.pdf|date=8 November 2016}}</ref>
These solutions exhibit stair-stepped patterns, as in the following examples for ''n'' = 8, 9 and 10:
{{col-begin-fixed}}
{{col-break}}
{{Chess diagram small
| tleft
|
|__|__|__|ql|__|__|__|__
|__|__|__|__|__|__|ql|__
|__|__|ql|__|__|__|__|__
|__|__|__|__|__|__|__|ql
|__|ql|__|__|__|__|__|__
|__|__|__|__|ql|__|__|__
|ql|__|__|__|__|__|__|__
|__|__|__|__|__|ql|__|__
| Staircase solution for 8 queens
}}
{{col-break}}
{{Chess diagram 9x9 small
| tleft
|
|__|__|__|__|__|__|ql|__|__
|__|__|ql|__|__|__|__|__|__
|__|__|__|__|__|ql|__|__|__
|__|ql|__|__|__|__|__|__|__
|__|__|__|__|ql|__|__|__|__
|ql|__|__|__|__|__|__|__|__
|__|__|__|__|__|__|__|__|ql
|__|__|__|ql|__|__|__|__|__
|__|__|__|__|__|__|__|ql|__
| Staircase solution for 9 queens
}}
{{col-break}}
{{Chess diagram 10x10 small
| tleft
|
|__|__|__|__|ql|__|__|__|__|__
|__|__|__|__|__|__|__|__|__|ql
|__|__|__|ql|__|__|__|__|__|__
|__|__|__|__|__|__|__|__|ql|__
|__|__|ql|__|__|__|__|__|__|__
|__|__|__|__|__|__|__|ql|__|__
|__|ql|__|__|__|__|__|__|__|__
|__|__|__|__|__|__|ql|__|__|__
|ql|__|__|__|__|__|__|__|__|__
|__|__|__|__|__|ql|__|__|__|__
| Staircase solution for 10 queens
}}
{{col-end}}

The examples above can be obtained with the following formulas.<ref name=bernhardsson /> Let (''i'', ''j'') be the square in column ''i'' and row ''j'' on the ''n'' × ''n'' chessboard, ''k'' an integer.

One approach<ref name=bernhardsson /> is

# If the remainder from dividing ''n'' by 6 is not 2 or 3 then the list is simply all even numbers followed by all odd numbers not greater than ''n''.
# Otherwise, write separate lists of even and odd numbers (2, 4, 6, 8 – 1, 3, 5, 7).
# If the remainder is 2, swap 1 and 3 in odd list and move 5 to the end ('''3, 1''', 7, '''5''').
# If the remainder is 3, move 2 to the end of even list and 1,3 to the end of odd list (4, 6, 8, '''2''' – 5, 7, 9, '''1, 3''').
# Append odd list to the even list and place queens in the rows given by these numbers, from left to right (a2, b4, c6, d8, e3, f1, g7, h5).

For {{math|1=''n''&nbsp;=&nbsp;8}} this results in fundamental solution 1 above. A few more examples follow.
* 14 queens (remainder 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
* 15 queens (remainder 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
* 20 queens (remainder 2): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 9, 11, 13, 15, 17, 19, 5.