I have a $n\times n$ chessboard and 4 kings inside it. My goal is to count the number of arrangements where some of them are non-attacking or mutually attacking, for example:
- In the case where the $4$ kings are non-attacking, there exists a formula that counts the total arrangements with the corresponding restriction:
$\frac{1}{24} \left(n^8-54 n^6+72 n^5+995 n^4-2472 n^3-5094 n^2+21480 n-17112\right)$
- However, the problem arises when I try to count the arrangements where the 4 kings form a cluster:
00k0
00k0
00k0
00k0
0000
kk00
0kk0
0000
0000
0kk0
000k
00k0
As you can see, there are some cases where all 4 kings are adjacent, forming a cluster. Thus, my goal is to calculate in how many arrangements this condition is satisfied.
Also, there are 3 more cases I would like to count:
- A cluster of 3 kings (3 adjacent kings) and another king who is non-attacking to any of the cluster pieces:
0k00
00kk
0000
0k00
00k0
0k00
k00k
0000
- Two clusters formed by 2 attacking kings: (Note that both clusters must be non-adjacent, since it would form a cluster of size 4, and would have to be counted in case 2)
0kk0
0000
0k00
00k0
k000
k000
00kk
0000
- A 2-king cluster and 2 clusters of 1 king. This case can be derived with the solution of all the above cases and the total amount of ways to place 4 kings on the chessboard, which is $\binom{n^2}{4}$.