# Queens in the chess board

A curious question.

a) How many different ways exists to put "n" queens on a chessboard and they all can't capture the others?

b)If you put one queen in the chess board knowing that exist one other queen there, what is the probability that the new can't be captured?

-
Perhaps you would like to say what progress you have made so far, and what exactly is causing you problems? –  Old John Nov 4 '12 at 18:19
I could not develop almost nothing because the diagonals, they are variables and left me not knowing what to do. –  John Smith Nov 4 '12 at 18:21
(a) is the eight queens puzzle. –  Brian M. Scott Nov 4 '12 at 18:21
For part (b) you could examine what happens when the first queen has been placed on different "types" of initial square depending on the number of other squares that the initial queen attacks. It looks like a lot of separate cases need to be considered, unless someone finds a neat solution. –  Old John Nov 4 '12 at 18:24
@JohnSmith: if you read the Wikipedia article, you'll see that it mentions not just $n = 8$, but does consider all $n$ in general. In particular, the section about the number of solutions is en.wikipedia.org/wiki/Eight_queens_puzzle#Counting_solutions and it mentions that there is no known formula for the exact number of solutions. (The numbers are OEIS sequence A000170.) Your question (b) seems a separate question altogether. –  ShreevatsaR Nov 4 '12 at 18:26

This Python code from the wikipedia page of the eight queens problem mentioned in the comments above will give solutions for all n, but the algorithm is "intractable for n >= 20". A recode in Haskell would solve the problem of dealing with large numbers and would be significantly faster but still would quickly reach an upper limit.

from itertools import permutations

n = 8
cols = range(n)
for vec in permutations(cols):
if (n == len(set(vec[i] + i for i in cols))
== len(set(vec[i] - i for i in cols))):
print vec


This sequence shows the number of solutions for $n \in [1,26]$. For larger numbers the wikipedia page contains an "Exercise in algorithm design" section that should yield speedups, but perhaps none too significant (else the AES sequence would have more solutions).

Part $b$ might be analyzed as follows. Note that any rook on any square has access to $n - 1 + n - 1 = 2n - 1$ spaces (not including the space it is on). The bishop's movement is more difficult to analyze, but given coordinates $(x, y) \in [1,n] \times [1,n]$ there should emerge a movement pattern after a few examples (a proof of which should be pretty clear): concentric movement squares each increase in movement range by $2$ squares as they move in, with the outermost having range $n - 1$. Putting this together a queen at square $(x, y)$ in an $n$-sized grid, WLOG taking $x,y <= \frac{n}{2}$ (because of the concentric squares) has movement range $(2n - 2) + (n - 1) + (min(x, y) - 1) * 2$. From here on it's simple probability. Good luck on part $a$.

Edit: taking the minimum of x and y yields which concentric square it is in, exactly, which was the reason for taking $(x, y)$ in the lower left quadrant. For a sketch of the proof of why the concentric squares trick works, a bishop in the $(1,1)$ (lower left) position has $n - 1$ moves, so moving it out along the main diagonal increases its movement range by one in the top-left, bottom-right, and bottom-left diagonals (respective to the knight) and decreases its range by one in the top-right direction (as we moved it in that direction). This gives a net gain of two movement squares. Repeated application works until we reach the innermost concentric square, where the process begins to reverse. This only considered squares on the corners but squares on the edges work in exactly the same way and a quick example will convince you that the movement range of a bishop on the edge of the board is indeed $n - 1$.

-
People will usually read the answer first and then the comments, so adding a correction in a comment isn't likely to significantly reduce their confusion by this error; it would be much preferable to edit the answer accordingly. –  joriki Nov 4 '12 at 20:09
@joriki, Thanks, done. –  Julien Clancy Nov 4 '12 at 20:22

Before we get to the enumeration problem, we should probably consider the existence problem. This was studied by:

E.J. Hoffman, J.C. Loessi and R.C. Moore, Constructions for the Solution of the m Queens Problem, Mathematics Magazine (1969), 66-72. (pdf)

They found:

Theorem: For all $n \geq 4$ there exists a solution to the $n$-queens problem

Their proof goes as follows:

For $n=2m$ where $m \not\equiv 1 \pmod 3$ they gave the construction, e.g.:

.Q........
...Q......
.....Q....
.......Q..
.........Q
Q.........
..Q.......
....Q.....
......Q...
........Q.


(Hopefully here, and with the subsequent constructions, it's clear from the picture how this generalises; if not, the full details are in the above paper.)

For $n=2m$ where $m \not\equiv 0 \pmod 3$ they gave, e.g.:

......Q.......
........Q.....
..........Q...
............Q.
Q.............
..Q...........
....Q.........
.........Q....
...........Q..
.............Q
.Q............
...Q..........
.....Q........
.......Q......


Finally, for odd $n$, we just take one of the above constructions for $n-1$, add a new row (at the bottom) and column (on the right hand size) and place the new queen in the bottom-right. E.g.

......Q........
........Q......
..........Q....
............Q..
Q..............
..Q............
....Q..........
.........Q.....
...........Q...
.............Q.
.Q.............
...Q...........
.....Q.........
.......Q.......
..............Q

-