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
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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:
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:
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)$.
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