Please inform. For which maximum number n of non-attacking queens (located on a flat board with dimensions n × n), at least one solution is known?
Yours sincerely, Alexander
2
-
1$\begingroup$ en.wikipedia.org/wiki/Eight_queens_puzzle. (But what happens for the case of a non "flat" board...?!?) $\endgroup$– Zach TeitlerCommented Nov 17, 2017 at 19:19
-
1$\begingroup$ The number of ways of placing $n$ non-attacking queens on an $n\times n$ chessboard is tabulated at oeis.org/A000170 $\endgroup$– Gerry MyersonCommented Nov 18, 2017 at 2:15
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
In 1874, Pauls published a proof that a solution exists for all $n$. His solution may be summarized as follows (this table is taken from Bell and Stevens, Discrete Math. 309 (2009), 1–31).
$n=6k$ or $n=6k+4$: $A_1 = \{(2i,i)\mid 1\le i\le n/2\}$, $A_2 = \{(2i-1,n/2+i)\mid 1\le i \le n/2\}$
$n=6k+1$ or $n=6k+5$: $B_1 = \{(n,1)\}$, $B_2 = (2i,i+1)\mid 1\le i\le (n-1)/2\}$, $B_3 = \{(2i-1,(n+1)/2 +i)\mid 1\le i\le (n-1)/2\}$.
$n=6k+2$: $C_1 = \{(4,1)\}$, $C_2 = \{(n,n/2-1)\}$, $C_3 = \{(2,n/2)\}$, $C_4 = \{(n-1,n/2+1)\}$, $C_5 = \{(1,n/2+2)\}$, $C_6 = \{(n-3,n)\}$, $C_7 = \{(n-2i,i+1)\mid 1\le i\le n/2-3\}$, $C_8 = \{(n-2i-3,n/2+i+2)\mid 1\le i\le n/2-3\}$.
$n=6k+3$: Put solution for $(n-1)\times(n-1)$ board in bottom left corner, add queen to top right.
answered Nov 17, 2017 at 19:13