The Two Knights Problem (Implemented in C++)

The two knights problem is a general mathematical challenge, where we have to find the total number of ways to place two knights on an nxn chessboard such that they do not attack each other. This is more of a mathematical problem than an algorithmic one. So first let us try to understand the theory and formulate the way to find the required number.

The Approach for Two Knights Problem

Firstly, the main idea that comes to mind is to take cases and solve the problem. Just look at an example, say a 4×4 chessboard.

The knights in the corner can attack only two other squares, and there are 4 corners. So, the total number of squares taken is 4.2= 8 in total for the corner squares.

Similarly, based on their positions we can create cases and use if-else to implement them. But we are not going to look at that approach here as it is a more crude way of solving the problem without finding out the patterns. Also, it takes a long time to formulate the cases. Let us look at a much easier way to solve it.

The Formula

Let us try to derive a formula to solve this so that we need not even use a loop or an if condition, but just apply the formula to get the solution. Note that the only variable here is the dimension of the chessboard. So our formula is going to be based on that only.

Firstly we will proceed like how we introduced in the above crude approach. That is, by taking the total number of squares available for the two knights and then subtracting the squares where they attack each other.

The total number of squares available to the first knight will obviously be all the squares on the board, that is, n*n. Let us call this number k1, meaning the number of squares available for knight 1. S0, k1 = n*n

Now, for the second knight, the number of squares will be 1 less than the number of squares for the first knight as that square is occupied, which is n*n -1. So, k2= n*n -1.

So, the total number of ways to place two knights on a chessboard of size nxn, without worrying about the knights attacking each other is, k1*k2, or k1*(k1-1).

But, note that the knights are identical, so according to the rules of permutations, we will consider the positions to be the same, even if the knights exchange their positions. So, the number of ways to place will be halved as the knights are identical.

Finally, the total number of ways to place two knights will be, k1*(k1-1)/2, where k1= n*n.

Now, we have to subtract the number of places where the knights attack each other from this number. Let us see that clearly below.

Pictorial representation of blocks for two knights

We know that the knight’s attack is an L-shaped path, that is 3 squares in 1 direction and 1 square in another. So, their attack range is in a 2×3 or 3×2 portion of the chessboard.

        2×3 block

   3×2 block

In a 2×3 block, where the knight is placed on the first column it can attack one square as shown. Also, there can another knight that can be placed on the first column attacking the diagonally opposite square as shown in the second picture. The same applies to a 3×2 block, just that it is seen horizontally. So each block has two squares that can be attacked by a knight.

Note: The knights placed in the attacking squares can also attack the knights in the first column, but as we have seen above, as the knights are identical we take both the cases as the same.

Now each 2×3 block has two attacking squares and each 3×2 has 2 attacking squares.

Block Arrangement

Now our job is simple, we just need to see how many blocks can be placed in the given chessboard and multiply it by the number of attacked squares in each block. Note that the blocks can overlap each other as we are considering only the first column of each block.

Take a 2×3 block first.

First, let us see how many blocks are possible in the horizontal direction. As we are overlapping the blocks, the number of blocks will be the number of columns possible to cover with the blocks. We cannot include the last column as the first column of a block as the length of the column is 2. So we can have n-1 blocks that are possible in the horizontal direction.

In the vertical direction, since we are considering the first and the third row,  we can keep track of the possible positions of the third row. It starts at the 2nd square and goes till the end square. So, we can say that the block has n-2 possibilities in the vertical direction.

So total number of positions available for the 2×3 block is (n-1)*(n-2).

For the 3×2 blocks too, the result is very similar. We can have only 2 attacks per block as the block size remains the same, only that it is rotated horizontally. In the horizontal direction, it has size 2 so we have n-2 possibilities and in the vertical direction it is n-1 possibilities. So for this type of block too, we get (n-1)*(n-2).

Formula

So, the total number of blocks is number of 2×3 blocks + number of 3×2 blocks. That is, (n-1)*(n-2)+ (n-1)*(n-2) = 2*(n-1)(n-2).

Now, the number of attacks for each block is 2. So, the total number of attacks will be 2 * number of blocks = 2 * 2(n-1)(n-2) = 4(n-1)(n-2).

Note: We actually need not reduce for n<=2 as there won’t be any cases where the knights attack each other. But the formula takes care of it as if we have n=1,2 the reduction number becomes 0.

This is the formula we need. Now the job is very simple as we just have to substitute this formula in the code.

Implementation in C++

Let us see the C++ code below for the above implementation of the formula.

#include<bits/stdc++.h> 
using namespace std; 
int main()
{ int n,k1,k2,ktot,red; 
  cin>>n; 
  k1=n*n;              // number of ways to place first knights
  k2=k1-1;             // number of ways to place second knights 
  ktot=k1*k2/2;        // total number of ways to place 2 knights
  red=4*(n-1)*(n-2);   // total number of attacked places to be reduced
  cout<<ktot-red;      // total number of places not attacked
  return 0; 
}

Sample output

8
1848

As you can see, the size of the code is really small, this is because we have simplified the problem entirely using the pattern and generated a formula. This is also the most time-efficient solution possible. If we use the case method we will be trying various cases and the code will be really long. So to solve any algorithmic problem efficiently we must make use of such patterns to simplify the solutions.

Leave a Reply

Your email address will not be published. Required fields are marked *