Mutually Attacking Knights

How many different ways can we place two identical knights on an \( n \times n \) chessboard so that they attack each other? Can we find a closed-form expression that gives this number? This is the problem we explore in this article.

Contents

• Introduction
• Counting Placements as the Board Grows
  • Type A Squares
  • Type B Squares
  • Type C Squares
  • Type D Squares
  • Closed Form Expression
• Counting Placements for Each Square
  • Attacking Degrees of Squares
  • From Attacking Degrees to Counting Placements
  • Closed Form Expression
• Counting Placements From Minimal Attack Sections
  • Minimal Attack Sections
  • Closed Form Expression
• References

Introduction

A knight moves two squares in one direction, then one square perpendicular to it, forming an L-shaped path. If a piece occupies the destination square, the knight captures it. If two knights are placed such that each can capture the other in a single move, then we say the knights attack each other. We want to determine the number of ways to place two identical knights on an \( n \times n \) chessboard so that they attack each other.

The above illustration shows just one of several ways two knights can attack each other on a \( 3 \times 3 \) board. There are, in fact, a total of eight such placements, shown below.

Let \( f(n) \) denote the number of ways we can place two identical knights on an \( n \times n \) chessboard such that they attack each other, where \( n \ge 1. \)

A \( 1 \times 1 \) board has room for only one knight, so we define \( f(1) = 0. \) On a \( 2 \times 2 \) board, a knight cannot move two squares in any direction, and therefore cannot attack. Therefore, \( f(2) = 0. \) To summarise, \[ f(1) = f(2) = 0. \] From the illustration above, we see that \( f(3) = 8. \) We want to find a closed-form expression for \( f(n). \)

We will analyse this problem from various perspectives. We begin with a couple of needlessly complicated approaches, followed by a simple and elegant solution. While I personally enjoy these long-winded explorations, if you prefer a more direct solution, please skip ahead to Counting Placements From Minimal Attack Sections.

Before we proceed, let us introduce the term mutually attacking knight placement to mean a placement of two knights on the chessboard such that they attack each other. Unless stated otherwise, the two knights are identical. This term will serve as a convenient shorthand for referring to such placements.

Counting Placements as the Board Grows

We now turn to the needlessly complicated solution promised in the previous section. We analyse the new mutually attacking knight placements introduced when an existing board is enlarged by adding a row and a column.

Let us define \[ \Delta f(n) = f(n) - f(n - 1) \] for \( n \ge 2, \) so that \( \Delta f(n) \) denotes the new mutually attacking knight placements introduced when an \( (n - 1) \times (n - 1) \) board is expanded to size \( n \times n \) by adding one row and one column.

For brevity, we will avoid restating the process of enlarging an \( (n - 1) \times (n - 1) \) board to an \( n \times n \) board by adding one row and one column whenever we refer to new placements. Instead, we use the term new placements on an \( n \times n \) board to refer to \( \Delta f(n). \) It is to be understood that these new placements are the mutually attacking knight placements introduced by enlarging the board from size \( (n - 1) \times (n - 1) \) to \( n \times n. \)

Without loss of generality, suppose the new row and column are added to the bottom and right, respectively. We already know that \begin{align*} \Delta f(2) & = f(2) - f(1) = 0 - 0 = 0, \\ \Delta f(3) & = f(3) - f(2) = 8 - 0 = 8. \\ \end{align*} We will now find \( \Delta f(n) \) for \( n \ge 4. \) To do this, we first categorise the newly added squares due to board expansion, into four types, as illustrated below.

Here is a brief description of each square type:

• Type A squares are the three new corner squares.
• Type B squares are the two new squares adjacent to type A squares at the top and left edges.
• Type C squares are the new squares that are not adjacent to any type A square. If the new board has dimensions \( n \times n, \) where \( n \ge 4, \) then there are exactly \( 2n - 8 \) squares of type C.
• Type D squares are the two new squares adjacent to the bottom-right type A square.

We now calculate how many new mutually attacking knight placements are introduced by these additional squares as the board expands. We proceed with a case-by-case analysis for each square type.

Type A Squares

There are three squares of type A. If we place one knight on a type A square, there are two positions for the second knight such that the two knights attack each other.

Since there are three such squares, we get a total of \( 3 \times 2 = 6 \) new mutually attacking knight placements.

Type B Squares

There are two squares of type B. If we place one knight on a type B square, there are three positions for the second knight such that the two knights attack each other.

Since there are two such squares, we get a total of \( 2 \times 3 = 6 \) new mutually attacking knight placements.

Type C Squares

The number of type C squares depends on the board size. When we increase the size of a board from \( (n - 1) \times (n - 1) \) to \( n \times n, \) where \( n \ge 4, \) we add \( n^2 - (n - 1)^2 = 2n - 1 \) new squares. Among these, \( 3 \) are of type A, \( 2 \) are of type B, and \( 2 \) are of type D. That gives us a total of \( 7 \) squares of type A, B, or D. The remaining \( 2n - 1 - 7 = 2n - 8 \) squares are therefore of type C. Note that when the board size increases from \( 3 \times 3 \) to \( 4 \times 4, \) there are \( 2 \times 4 - 8 = 0 \) squares of type C.

However, for a board of size \( 5 \times 5 \) or greater, there is a positive number of type C squares since \( 2n - 8 \gt 0 \) if and only if \( n \gt 4. \)

If we place one knight on a type C square, there are four positions for the second knight such that the two knights attack each other.

Since there are \( 2n - 8 \) such squares, we get a total of \( 4(2n - 8) = 8(n - 4) \) new mutually attacking knight placements.

Type D Squares

There are two squares of type D. As with type B squares, placing one knight on a type D square yields three positions for the second knight such that the two knights attack each other. This gives \( 2 \times 3 = 6 \) potentially new placements.

However, unlike type B squares, not all of these placements are new. The two placements where one knight is on the right edge and the other on the bottom edge were already counted in a previous subsection.

For example, when we increase the board size from \( 3 \times 3 \) to \( 4 \times 4, \) both the placements described in the previous paragraph appear while analysing the placements with a knight on a type B square. More generally, for any board of size \( n \times n \) with \( n \ge 5, \) these placements occur while analysing the placements with a knight on a type C square. Therefore the total number of new mutually attacking knight placements is \( 2 \times 3 - 2 = 4. \)

Another way to describe this result is to observe that when one knight is placed on a type D square, only two positions for the second knight yield new mutually attacking knight placements. Since there are two type \( D \) squares, we get a total of \( 2 \times 2 = 4 \) new mutually attacking knight placements.

Closed Form Expression

If we add the number of new mutually attacking knight placements found in each of the cases above, we get \[ \Delta f(n) = 6 + 6 + 8(n - 4) + 4 = 8(n - 2) \] new mutually attacking knight placements as the board size increases from \( (n - 1) \times (n - 1) \) to \( n \times n, \) where \( n \ge 4. \) We already know that \( \Delta f(2) = 0 \) and \( \Delta f(3) = 8. \) Surprisingly, the above formula produces the correct values for those cases as well. Therefore, we can generalise this result as \[ \Delta f(n) = 8(n - 2) \] for all \( n \ge 2. \) We can now calculate \( f(n) \) for \( n \ge 1 \) as follows: \begin{align*} f(n) & = \sum_{k = 1}^n f(k) - \sum_{k = 1}^{n - 1} f(k) \\ & = \sum_{k = 1}^n f(k) - \sum_{k = 2}^n f(k - 1) \\ & = f(1) + \sum_{k = 2}^n (f(k) - f(k - 1)) \\ & = f(1) + \sum_{k = 2}^n \Delta f(k) \\ & = 0 + \sum_{k = 2}^n 8(k - 2) \\ & = 8 \sum_{k = 0}^{n - 2} k \\ & = \frac{8(n - 2)(n - 1)}{2} \\ & = 4(n - 1)(n - 2). \end{align*} To summarise, we now have a closed form expression for \( f(n). \) For all \( n \ge 1, \) we have \[ f(n) = 4(n - 1)(n - 2). \]

Counting Placements for Each Square

The previous section took a long-winded path to arrive at a closed form expression for \( f(n). \) In this section, we will reach the same result that is still a bit drawn out, but not quite as much as before.

This time, instead of looking only at the new squares created when the board grows, we consider every square on the board. To make the counting easier, we no longer treat the knights as identical. We first work with two distinct knights, count the mutually attacking knight placements, and then divide the total by \( 2 \) to get the result for identical knights.

Attacking Degrees of Squares

Here, we introduce the term attacking degree of a square to mean the number of squares a knight can move to from that square in a single move. In other words, the attacking degree of a square is the number of squares that would be attacked if a knight were placed on it. For example, the corner squares have an attacking degree of \( 2. \)

Let us now label each square with its attacking degree. A \( 1 \times 1 \) board has only one square of attacking degree \( 0 \) since a knight placed on it has nothing to attack. Similarly, each square of a \( 2 \times 2 \) board has attacking degree \( 0 \) too.

On a \( 3 \times 3 \) board, all squares have attacking degree \( 2 \) except the centre square, whose attacking degree is \( 0. \) In other words, placing a knight on any square other than the middle one gives exactly two possible positions for the other knight so that they attack each other.

With eight such squares, we get \( 8 \times 2 = 16 \) mutually attacking knight placements when the two knights are distinct. If we divide this number by \( 2, \) we get \( 8 \) which is indeed the number of mutually attacking knight placements on a \( 3 \times 3 \) board when the two knights are identical. This matches the earlier result \( f(3) = 8. \)

From Attacking Degrees to Counting Placements

Let \( g(n) \) be the number of mutually attacking knight placements on an \( n \times n \) board when the knights are distinct. Then \( g(n) \) is simply the sum of the attacking degrees of all squares on the board. As before, let \( f(n) \) denote the number of mutually attacking knight placements on an \( n \times n \) board when the two knights are identical. We will now show that \( f(n) = g(n)/2. \)

Label all squares of the \( n \times n \) board as \( S_1, S_2, \dots, S_{n^2} \) in any fixed order. Label the two distinct knights as \( N_1 \) and \( N_2. \) We represent each mutually attacking knight placement as an ordered pair \( (S_i, S_j) \) if \( N_1 \) is on \( S_i \) and \( N_2 \) is on \( S_j, \) with the two knights attacking each other. Here \( 1 \le i, j \le n^2 \) and \( i \ne j. \)

Let \( M \) be the set of all mutually attacking knight placements for distinct knights on an \( n \times n \) board. Then \[ g(n) = \lvert M \rvert. \] If \( (S_i, S_j) \) is a mutually attacking knight placement of the distinct knights \( N_1 \) and \( N_2 \) for some \( i \) and \( j \) with \( 1 \le i, j \le n^2 \) and \( i \ne j, \) then \( (S_j, S_i) \) is also a mutually attacking knight placement, since swapping the positions of the two mutually attacking knights still yields a valid mutually attacking placement. Therefore \[ (S_i, S_j) \in M \iff (S_j, S_i) \in M. \] Each ordered placement \( (S_i, S_j) \) in \( M \) is thus paired with the ordered placement \( (S_j, S_i). \) When the knights are identical, the two arrangements are indistinguishable and count as one placement. Hence, the number of mutually attacking placements for identical knights is exactly half of the number for distinct knights, i.e., \[ f(n) = \frac{g(n)}{2}. \] The next subsection focuses on calculating \( g(n), \) from which \( f(n) \) follows immediately by the above formula.

Closed Form Expression

As noted in the previous section, the number of mutually attacking knight placements for two distinct knights on an \( n \times n \) board is simply the sum of attacking degrees of all squares on the board. If we label each square as discussed in the previous section and use the notation \( \deg(S_i) \) for the attacking degree of the square labelled \( S_i, \) where \( 1 \le i \le n^2, \) then \[ g(n) = \sum_{i=1}^{n^2} \deg(S_i). \] Recall that the attacking degree of a square is the number of squares a knight could attack if it were placed there. Earlier, we saw that on a \( 3 \times 3 \) board, all squares except the centre one have attacking degree \( 2, \) which gives \( g(3) = 8 \times 2 = 16 \) and \( f(3) = g(3)/2 = 8. \) Let us now write down the attacking degrees of all squares on a \( 4 \times 4 \) board.

From the above illustration we get \begin{align*} g(4) & = 4 \times 2 + 8 \times 3 + 4 \times 4 = 48, \\ f(4) & = g(4)/2 = 24. \end{align*} A more general pattern emerges if we consider a larger board, such as a \( 6 \times 6 \) board.

From this illustration, we get \begin{align*} g(6) & = 4 \times 2 + 8 \times 3 + 12 \times 4 + 8 \times 6 + 4 \times 8 = 160. \\ f(6) & = g(6)/2 = 80. \end{align*} Let us find a general formula now for \( n \ge 4. \) We introduce one more notation. Let \( D_k(n) \) denote the sum of the attacking degrees of all squares of attacking degree \( k \) on an \( n \times n \) board, i.e., \[ D_k(n) = \sum_{\mathclap{\deg(S_i) = k}} \deg(S_i). \] Since the only attacking degrees the squares can have are \( 2, 3, 4, 6 \) and \( 8, \) the sum of the attacking degrees of all squares can be written as \[ g(n) = D_2(n) + D_3(n) + D_4(n) + D_6(n) + D_8(n). \] There are exactly four squares of attacking degree \( 2. \) These are the corner ones. Therefore, \[ D_2(n) = 4 \times 2 = 8. \] The eight squares adjacent to the corner squares have attacking degree \( 3. \) Therefore, \[ D_3(n) = 8 \times 3 = 24. \] Let us define an inner corner square as one that shares a corner with a corner square but not an edge with it. There are four inner corner squares and each has attacking degree \( 4. \) Further, each row and column on the outer edge contains \( n - 4 \) additional squares with attacking degree \( 4. \) Therefore, \[ D_4(n) = (4 + 4(n - 4))(4) = 16(n - 3). \] Consider a row or column that contains two inner corner squares of attacking degree \( 4. \) All \( n - 4 \) squares between the inner corner squares have attacking degree \( 6. \) There are two such rows and two such columns. Therefore, \[ D_6(n) = 4(n - 4)(6) = 24(n - 4). \] We have counted the attacking degrees of all squares in the first two columns and rows as well as the last two columns and rows. We are left with \( (n - 4)^2 \) squares in the middle, and they all have attacking degree \( 8. \) Therefore, \[ D_8(n) = 8(n - 4)^2. \] Therefore, \begin{align*} g(n) & = D_2(n) + D_3(n) + D_4(n) + D_6(n) + D_8(n) \\ & = 8 + 24 + 16(n - 3) + 24(n - 4) + 8(n - 4)^2 \\ & = 8(n - 1)(n - 2). \end{align*} Even though we assumed \( n \ge 4 \) while obtaining the above formula, remarkably, it gives us the correct values for \( n = 1, 2 \) and \( 3. \) The number of mutually attacking knight placements for distinct knights on an \( n \times n \) board is \( 0 \) if \( n = 1 \) or \( 2, \) and \( 16 \) if \( n = 3, \) and indeed the above formula gives us \[ g(1) = g(2) = 0, \quad g(3) = 16. \] Therefore, we can now generalise the above result as \[ g(n) = 8(n - 1)(n - 2) \] for all \( n \ge 1. \) Therefore, for all \( n \ge 1, \) \[ f(n) = \frac{g(n)}{2} = 4(n - 1)(n - 2). \]

Counting Placements From Minimal Attack Sections

Finally, in this section, we take a look at a simple and elegant solution that arrives at the closed-form solution in a more direct manner. The analysis begins by looking at the smallest section of the board where two knights can attack each other.

Minimal Attack Sections

Consider a \( 2 \times 3 \) section of a board of size \( 3 \times 3 \) or larger. Such a section has exactly two mutually attacking knight placements.

Similarly, a \( 3 \times 2 \) section of a board also has exactly two mutually attacking knight placements.

We call these \( 2 \times 3 \) and \( 3 \times 2 \) sections the minimal attack sections of a board, since no smaller section can contain a mutually attacking knight placement.

Two distinct \( 2 \times 3 \) sections can share at most a \( 1 \times 3 \) section, which is smaller than a minimal attack section. Consequently, no mutually attacking knight placement can be common to two distinct \( 2 \times 3 \) sections of a board.

Similarly, two distinct \( 3 \times 2 \) sections can share at most a \( 3 \times 1 \) section, again too small to contain a minimal attack section. Therefore, they share no mutually attacking knight placement.

A \( 2 \times 3 \) section and a \( 3 \times 2 \) section can share at most a \( 2 \times 2 \) section, which is still smaller than a minimal attack section, so they share no mutually attacking knight placement either.

To summarise, any two minimal attack sections of the board yield distinct pairs of mutually attacking knight placements. The total number of such placements is therefore exactly twice the number of minimal attack sections on the board.

Closed Form Expression

In an \( n \times n \) board where \( n \ge 3, \) the left edge of a \( 2 \times 3 \) section can be placed in any one of the first \( n - 2 \) columns of the board. Similarly, the top edge of such a section can be placed in any one of the first \( n - 1 \) rows of the board. Therefore, the total number of distinct \( 2 \times 3 \) sections on the board is \( (n - 2)(n - 1). \)

By similar reasoning, the number of distinct \( 3 \times 2 \) sections on an \( n \times n \) board, where \( n \ge 3, \) is also \( (n - 1)(n - 2). \)

Let \( h(n) \) be the total number of minimal attack sections we can find on an \( n \times n \) board where \( n \ge 1. \) From the discussion in the previous two paragraphs, we know that \( h(n) = 2(n - 1)(n - 2) \) for \( n \ge 3. \) Further, this formula for \( h(n) \) works for \( n = 1 \) and \( n = 2 \) as well since \( h(1) = h(2) = 0 \) and indeed a \( 1 \times 1 \) board or a \( 2 \times 2 \) board is too small to contain any minimal attack sections. Therefore, for all \( n \ge 1, \) we get \[ h(n) = 2(n - 1)(n - 2). \] Since each minimal attack section yields two mutually attacking knight placements, the total number of mutually attacking knight placements on an \( n \times n \) board is \[ f(n) = 2h(n) = 4(n - 1)(n - 2) \] for all \( n \ge 1. \)

References

• Two Knights from the CSES Problem Set
• Knight Graph by Eric W. by Weisstein
• OEIS Entry A033996 by N. J. A. Sloane
• OEIS Entry A172132 by Vaclav Kotesovec