# Number of ways to place $4$ kings on an $n \times n$ chessboard

I have an $$n \times n$$ chessboard and $$4$$ kings on it. My goal is to count the number of arrangements where some of them are non-attacking or mutually attacking, for example:

1. 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)$$

1. 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:

1. 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

1. 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

1. 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}$$.
• When you put two kings just one next to the other (like the 00kk or 0kk0 cases in your question), then those kings can attack each other, so those cases are impossible. Am I right or am I missing some point here? Commented Jul 11 at 14:10
• A strategy for 2.: for each polyplet of size 4 (polyomino connected at edges or corners) (up to rotation and symmetry), count the number of translations of that polyplet in the chessboard (that will depends only on the dimension of the smallest rectangle inscribing the pattern) times the number of non-equivalent rotation/symmetry of the polyplet. There are 22 different polyplet, so its not that much labor. Commented Jul 11 at 16:35
• For 3., for each polyplet of size 3, sum the number of translations times free cells (assuming the cluster is not adjacent to the border). The number of free cells is computed by size of the board - 3 - number of square neighboring the polyplet. Find what to subtract to account for when the cluster is adjacent to the border, and to a corner. there is a bit of labor for each polyplet but there are only 5 polyplets of size 3. Commented Jul 11 at 16:35
• For 5., almost same as above, and the 4. can be deduced by the total amount of ways to place 4 kings Commented Jul 11 at 16:37
• You can use some programming to find the answer. Commented Jul 12 at 9:54

Here is a formula for case 2.

Strategy: for each polyplet of size 4 (polyomino connected at edges or corners) (up to rotation and symmetry), count the number of translations of that polyplet in the chessboard (that will depends only on the dimension of the smallest rectangle inscribing the pattern) times the number of non-equivalent rotation/symmetry of the polyplet.

For the polyplet ####, the bounding box is $$1\times 4$$, so there is $$(n-1+1)(n-4+1) = n(n-3)$$ placement possible. There are two non-equivalent transformations (under rotation and symmetry) of the polyplet.

We give for 21 remaining 4-polyplets the size of the bounding box and the number of non-equivalent transformation (see here for a list of the polyplets):

##       ##       ##       ###      ###      ###      ## #     ##       # #      #  #
##       # #       ##        #       #          #       #        ##      # #      ##
2x2,1    2x3,8    2x3,4    2x3,8    2x3,4    2x4,8    2x4,8    2x4,4    2x4,4    2x4,4

##       ##       ##       #         #       #        # #      ##       #        #
#        #       #        ##      # #       ##       #         #       ##       # #
#       #         #       #        #       #          #         #        #       #
3x3,4    3x3,8    3x3,8    3x3,4    3x3,1    3x3,4    3x3,4    3x4,8    3x4,4    3x4,8

#
#
#
#
4x4, 2


Recapping, we have:

$$1\times 4: 2$$ configurations

$$2\times 2: 1$$ configuration

$$2\times 3: 24$$ configurations

$$2\times 4: 28$$ configurations

$$3\times 3: 33$$ configurations

$$3\times 4: 20$$ configurations

$$4\times 4: 2$$ configurations

Thus, we get the total count (assuming $$n\geq 4$$): $$2n(n-3) + (n-1)(n-1) + 24(n-1)(n-2)+28(n-1)(n-3)+33(n-2)(n-2)+20(n-2)(n-3)+2(n-3)(n-3) = 110 n^2 - 436 n + 403$$ This matches the values you computed.

• Thanks, I also asked about a general formula for $k$ elements with case 2. restriction in this question Commented Jul 15 at 13:16
• Its easy to see that the coefficient in $n^2$ will follow oeis.org/A006770 (so you have the asymptotic behavior), however, I doubt we can find a closed form to express the other coefficients Commented Jul 15 at 15:28