Two Knights

Explanation

In this problem, we are given a number n and we need to find the number of ways 2 knights can be placed on a k x k chessboard such that they do not attack each other. Here, k lies from 1 to n.

Now, let's try to solve this problem for a 8 x 8 chessboard first, then we'll generalize the solution.

• If the first knight is placed on a corner, there are 2 positions at which the other knight cannot be placed.
• If it is placed adjacent to a corner, there are 3 positions at which the other knight cannot be placed.
  ... for the rest of the pattern please check the image below.

So here the total number of possibilities will be:

For 8 x 8 grid, n will be 8.

• For the 2 cells: 4 * (n ** 2 - 3)
• For the 3 cells: 8 * (n ** 2 - 4)
• For the 4 cells: 4 * (n - 3) * (n ** 2 - 5)
• For the 6 cells: 4 * (n - 4) * (n ** 2 - 7)
• For the rest of the cells: ((n - 4) ** 2) * (n ** 2 - 9)

The total number will be the summation of all these divided by 2. Because we are counting each possibility twice.

Code

n = int(input())

for i in range(1, n + 1):
    ans = 0

    ans += 4 * (i ** 2 - 3)
    ans += 8 * (i ** 2 - 4)
    ans += 4 * (i - 3) * (i ** 2 - 5)
    ans += 4 * (i - 4) * (i ** 2 - 7)
    ans += ((i - 4) ** 2) * (i ** 2 - 9)

    print(ans // 2)