Queens in the chess board

Question

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?

Answer 1

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$.

Answer 2

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