9
$\begingroup$

What are the number of ways two knights can be placed on a k×k chessboard so that they do not attack each other?

For k from 1 to 8, the answer is given below. How do I find a general formula?
0
6
28
96
252
550
1056
1848

Edit:

Here's my approach after @Peter 's help, I came to a conclusion that number of ways such that they attack is equal to two times the number of possible ways I can put an "L" shape on the board. (2 times because knights can swap positions), am I right? I don't know how do I more forward from here.

I tried finding number of ways to place L by this recursive formula: F[n][n]=4+F[i][i-3]+F[i-2][3]; But it's not working.

$\endgroup$
3
  • 1
    $\begingroup$ Probably, it is easier to determine the number of ways to place them that they attack each other. This has then only to be subtracted from $\frac{k^2(k^2-1)}{2}$ $\endgroup$ – Peter Jun 18 '19 at 10:44
  • $\begingroup$ Yes, That helped, So I came to a conclusion that number of ways such that they attack is equal to two times the number of possible ways I can put an "L" shape on the board. (2 times because knights can swap positions), am I right? I don't know how do I more forward from here. $\endgroup$ – Het Jun 18 '19 at 11:07
  • $\begingroup$ Maybe I can use recursion... @Peter $\endgroup$ – Het Jun 18 '19 at 11:24
18
$\begingroup$

Note that when we have two knights threatening each other, it actually forms either a $2\times3$ or $3 \times 2$ board. And for each of $2 \times 3$ and $3 \times 2$ boards, there are $2$ ways of placing two knights so that they threaten each other. So, what we should do is to count how many $2 \times 3$ and $3 \times 2$ squares on $n\times n$ board. For general $n$, the answer is $$(n-1)(n-2)+(n-2)(n-1) = 2(n-1)(n-2)$$ And for each $2\times3$ and $3\times2$ board, there are $2$ ways of placing the knights so that they threaten each other. Therefore, in total there are $$2\cdot2(n-1)(n-2)=4(n-1)(n-2)$$ ways of placing two knights so that they threaten each other. So what you are looking for is $$\frac{n^2(n^2-1)}{2}-4(n-1)(n-2)$$ It is also worth mentioning that we are not over-counting because whenever we place two knights so that they threaten each other, either a $2 \times 3$ or $3 \times 2$ board must contain both of the knights.

$\endgroup$
5
  • $\begingroup$ How did you count 2x3 and 3x2 boards? $\endgroup$ – Het Jun 18 '19 at 12:04
  • 2
    $\begingroup$ Since we have a square board, once we count number of $2 \times 3$ boards, number of $3 \times 2$ boards have the same number by symmetry. After that, in order to count number of $3 \times 2$ boards, you can basically start from top left and shift $1$ square to right and find how many times you can shift it to the right. And shifting it to bottom and finding how many times you can shift it to bottom and multiplying them will give you the answer since we are actually finding how many rows of $3$ adjacent squares are there and how many columns of $2$ adjacent squares are there. $\endgroup$ – ArsenBerk Jun 18 '19 at 12:11
  • $\begingroup$ Aren't there 4 ways to place 2 knights on 2x3 or 3x2 board? since both knight can swap positions. $\endgroup$ – Het Jun 18 '19 at 12:23
  • 2
    $\begingroup$ I think knights are to be considered identical in this case. So swapping positions will give the same placement. $\endgroup$ – ArsenBerk Jun 18 '19 at 12:28
  • $\begingroup$ Can you come up with a recursive solution to this problem? $\endgroup$ – vishal mishra Dec 20 '20 at 6:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.