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.

{{ toc }}

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

Two knights attacking 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.

All \( 8 \) ways two identical knights can attack each other on a \( 3 \times 3 \) board.

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.

|  |  |  |  | A
|  |  |  |  | B
|  |  |  |  | C
|  |  |  |  | C
|  |  |  |  | D
A | B | C | C | D | A

New squares, labelled by type, as the board size increases from \( 5 \times 5 \) to \( 6 \times 6 \)

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.

|  | ✗ |  |
|  |  | ✗ |

Knights on type A squares, with squares attacked by the top knight marked with crosses

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.

|  | ✗ |  |
|  | ✗ |  |
|  |  | ✗ |

Knights on type B squares, with squares attacked by the top knight marked with crosses

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.

|  |  | A
|  |  | B
|  |  | D
A | B | D | A

A \( 4 \times 4 \) board has no type C squares.

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 \).

|  |  |  | A
|  |  |  | B
|  |  |  | C
|  |  |  | D
A | B | C | D | A

A \( 5 \times 5 \) board has one type C square.

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.

|  |  | ✗ |
|  | ✗ |  |
|  | ✗ |  |
|  |  | ✗ |

Knights on type C squares, with squares attacked by the top knight marked with crosses

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.

|  |  | ✗ |
|  | ✗ |  |
|  | ✗ |  |

Knights on type D squares, with squares attacked by the top knight marked with crosses

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.

Placements already counted while analysing placements involving a knight on a type B square of the \( 4 \times 4 \) board

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 \).

Placements already counted while analysing placements involving a knight on a type C square of an \( n \times n \) board, where \( n \ge 5 \)

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.

|  |  | ✗ |
|  | ✗ |  |

Knights on type D squares, with squares attacked by the top knight that yield new mutually attacking knight placements marked with crosses

### 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 \).

|  | ✗ |
| ✗ |  |

The attacking degree of a corner square is \( 2 \) since a knight can attack two squares from it

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.

0

0 | 0
0 | 0

Attacking degrees of all squares are zero on \( 1 \times 1 \) and \( 2 \times 2 \) boards

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.

2 | 2 | 2
2 | 0 | 2
2 | 2 | 2

Attacking degrees of all squares on a \( 3 \times 3 \) board

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.

2 | 3 | 3 | 2
3 | 4 | 4 | 3
3 | 4 | 4 | 3
2 | 3 | 3 | 2

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.

2 | 3 | 4 | 4 | 3 | 2
3 | 4 | 6 | 6 | 4 | 3
4 | 6 | 8 | 8 | 6 | 4
4 | 6 | 8 | 8 | 6 | 4
3 | 4 | 6 | 6 | 4 | 3
2 | 3 | 4 | 4 | 3 | 2

Attacking degrees of all squares on 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 \). It is \( 16 \) if \( n = 3 \). 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.

Two mutually attacking knight placements on a \( 2 \times 3 \) section of a board

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

Two mutually attacking knight placements on a \( 3 \times 2 \) section of a board

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. Weisstein
- OEIS Entry A033996 by N. J. A. Sloane
- OEIS Entry A172132 by Vaclav Kotesovec