# Chess combination

On the chess board 8x8, we have 8 Rooks that , each Rook don't atack the other. How many situation if we give out: a) 1 main diagonal b) 2 main diagonals That's mean we can't put the Rook to the cells of diagonal

-
I'm too young to understand the solution what you means . I need the solution with combination or conformable, a simple solution –  LevanDokite Sep 20 '12 at 7:19

In general, if you want to count the number of ways of placing $n$ non-attacking rooks on an $n \times n$ chessboard (with some squares that the rooks must avoid), you can do it by calculating the permanent of a $(0,1)$-matrix: we place a $1$ wherever a rook is allowed to go, and a $0$ wherever the rook is not allowed to go.

Calculating the permanent of $(0,1)$-matrices is a #P-complete problem. So we cannot, in general, expect a simple "one size fits all" formula for these problems.

Here's GAP code that solves the counting problem:

Permanent(
[[0,1,1,1,1,1,1,1],
[1,0,1,1,1,1,1,1],
[1,1,0,1,1,1,1,1],
[1,1,1,0,1,1,1,1],
[1,1,1,1,0,1,1,1],
[1,1,1,1,1,0,1,1],
[1,1,1,1,1,1,0,1],
[1,1,1,1,1,1,1,0]]
);


gives 14833 which is the number of derangements (as previously mentioned; see also Sloane's A000166). It is also the number of $2 \times 8$ Latin rectangles whose first row is $(0,1,\ldots,7)$. In this instance, there's fairly simple formulae (see the links).

For the second question:

Permanent(
[[0,1,1,1,1,1,1,0],
[1,0,1,1,1,1,0,1],
[1,1,0,1,1,0,1,1],
[1,1,1,0,0,1,1,1],
[1,1,1,0,0,1,1,1],
[1,1,0,1,1,0,1,1],
[1,0,1,1,1,1,0,1],
[0,1,1,1,1,1,1,0]]
);


yields 4752 possibilities. This is also the number of $3 \times 8$ Latin rectangles whose first row is $(0,1,\ldots,7)$ and second rows is $(7,6,\ldots,0)$.

-
4752 is also the number of ways to place 3 non-attacking knights on a $6\times6$ board, according to oeis.org/A172134. Coincidence, presumably. The entry directly relevant to this question is oeis.org/A003471 –  Gerry Myerson Sep 20 '12 at 1:14

For (a), you want to count the permutations $\pi$ of $[1 \ldots 8]$ such that have no fixed point, i.e. $\pi(i) \ne i$ for all $i$. These are also known as derangements. See http://en.wikipedia.org/wiki/Derangement

EDIT: For (b), see http://oeis.org/A003471

-