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
Chess combination
-
0I'm too young to understand the solution what you means . I need the solution with combination or conformable, a simple solution – 2012-09-20
2 Answers
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)$.
-
04752 is also the number of ways to place 3 non-attacking knights on a $6\times6$ board, according to http://oeis.org/A172134. Coincidence, presumably. The entry directly relevant to this question is http://oeis.org/A003471 – 2012-09-20
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