We have given an integer n, we need to find the number of ways two knights can be placed on an n×n chessboard so that they do not attack each other.
I tried the simulation strategy but it is too costly as n can be of 10000. BY googling I got this formula
$ a = n * n * (n * n - 1) / 2$
$ b = 2 * (n - 2) * (2 * (n - 4) + 6)$
$ ans = a - b $
can anyone explain this formula I can't get my head through it?
On
Place the first knight anywhere. How many fields can it attack?
Depending on where you placed it, it can attack at least two fields and at most eight. Try to count the cases where it is less than eight, as these are the exceptional ones (placed at the border of the field, in the corner, etc.).
Now say there are $A_8$ ways to place the knight so that it can attack eight fields. Then the other one can be placed on any of the remaining $n^2 - 8$ fields, so this will contribute $A_8(n^2-8)$ to the total number of ways. Do the same for $A_2,...$ and you are done; the rest is simplifying terms.
Note that I assumed two distinguishable knights, e.g. black and white. If you can't distinguish them, you need to divide your final result by two.
The number of ways to put two knights on an $n\times n$ chessboard, with no other conditions, is $$\binom{n^2}2=\frac{n^2(n^2-1)}2=a.$$ The number of ways to put two knights on an $n\times n$ chessboard so that they do attack each other is $$4(n-1)(n-2)=b$$ as shown in the answer to this question. Namely, a pair of mutually attacking knights determines a $2\times3$ or $3\times2$ rectangle, there are $(n-1)(n-2)+(n-2)(n-1)$ such rectangles on the board, and there are two ways to place the knights in each rectangle.
The number of ways to put two knights on an $n\times n$ chessboard so that they don't attack each other is then $$\binom{n^2}2-4(n-1)(n-2)=a-b.$$
More generally, the number of ways to put two knights on an $m\times n$ chessboard so that they don't attack each other is $$\binom{mn}2-2[(m-1)(n-2)+(m-2)(n-1)].$$