DSA/CSES 2Knights

Non-Attacking Knights on a k×k Board

Problem. For every board size $k = 1, 2, \dots, n$ , count the number of ways to place two knights on a $k \times k$ chessboard so that they do not attack each other.

The core is instead of calculating the possible combinations of placements which is confusing we can do total_possibilities - attacking_squares

Step 1: Total ways to place two knights, ignoring attacks

A $k \times k$ board has $k^{2}$ squares. Placing two (identical, unlabeled) knights on two different squares is just "choose 2 squares out of $k^{2}$ ":

$(\binom{k^{2}}{2}) = \frac{k^{2} (k^{2} - 1)}{2}$

This is the total number of placements before removing the ones where the knights attack each other.

Step 2: Counting the attacking pairs

A knight standing at square $(x, y)$ attacks any square that is offset by one of these 8 vectors:

Offset (dx, dy)
(1, 2)	(1, −2)	(−1, 2)	(−1, −2)
(2, 1)	(2, −1)	(−2, 1)	(−2, −1)

Notice: in every one of these 8 vectors, the two numbers $| d x |$ and $| d y |$ are just 1 and 2 in some order, with some sign.

How many placements exist for one fixed offset (dx, dy)?

For the pair of squares $(x, y)$ and $(x + d x, y + d y)$ to both lie on the board, $x$ has $k - | d x |$ valid choices, and $y$ has $k - | d y |$ valid choices. So the count is:

$(k - | d x |) (k - | d y |)$

Since ${| d x |, | d y |} = {1, 2}$ for all 8 vectors, this is always:

$(k - 1) (k - 2)$

(No need to clamp negative values to zero — if $k = 1$ , the factor $(k - 1) = 0$ already kills the product; if $k = 2$ , the factor $(k - 2) = 0$ does the same. The algebra takes care of small boards automatically.)

Summing over all 8 offsets gives the total number of ordered attacking pairs (i.e., "knight A attacks square B" counted separately from "knight B attacks square A"):

$8 (k - 1) (k - 2)$

But an unordered pair of squares gets counted twice this way (once in each direction), so the number of unordered attacking pairs is:

$E (k) = \frac{8 (k - 1) (k - 2)}{2} = 4 (k - 1) (k - 2)$

Step 3: Subtract to get non-attacking pairs

$Answer (k) = (\binom{k^{2}}{2}) - E (k) = \frac{k^{2} (k^{2} - 1)}{2} - 4 (k - 1) (k - 2)$

Step 4: Simplify into one closed-form polynomial

Expand each piece separately.

First term: $\frac{k^{2} (k^{2} - 1)}{2} = \frac{k^{4} - k^{2}}{2}$

Second term: $4 (k - 1) (k - 2) = 4 (k^{2} - 3 k + 2) = 4 k^{2} - 12 k + 8$

Put both over a common denominator of 2:

$Answer (k) = \frac{k^{4} - k^{2}}{2} - \frac{8 k^{2} - 24 k + 16}{2} = \frac{k^{4} - k^{2} - 8 k^{2} + 24 k - 16}{2}$

Combine like terms ( $- k^{2} - 8 k^{2} = - 9 k^{2}$ ):

$Answer (k) = \frac{k^{4} - 9 k^{2} + 24 k - 16}{2}$

Step 5: Sanity check against the example

k	Answer(k)
1	0
2	6
3	28
4	96
5	252
6	550
7	1056
8	1848

Matches the sample output exactly.

Intuition for k=1 and k=2: On a 1×1 board there's only one square, so you can't even place two knights (0 ways). On a 2×2 board, $(\binom{4}{2}) = 6$ pairs exist, and a knight move needs at least a 3-wide gap in one direction, so none of them attack — all 6 count.

Step 6: Implementation

Since the formula is closed-form, each answer is $O (1)$ to compute, so the whole solution is $O (n)$ — trivially fast for $n \leq 10000$ .

def f(k):
    return (pow(k, 4) - 9 * pow(k, 2) + 24 * k - 16) // 2

n = int(input())

for i in range(1, n + 1):
    print(f(i))

Note: the division by 2 is safe as integer division (//) because $k^{4} - 9 k^{2} + 24 k - 16$ is always even — this follows directly from the derivation, since it came from summing two integer-valued combinatorial counts ( $(\binom{k^{2}}{2})$ and $E (k)$ ) that are each themselves always integers, and their difference stays an integer after the $\times 2$ common denominator was cleared.