Given an n × m chessboard, we need to place one black knight and one white knight such that they do not attack each other. The goal is to count the number of valid arrangements.
A knight in chess moves in an L-shape:
Two knights attack each other if one can reach the other in a single knight move.
Understanding the Problem
Since the knights are of different colors, placing the black knight on square A and the white knight on square B is different from placing the black knight on B and the white knight on A.
Therefore, we must count ordered placements.
Step 1: Count All Possible Placements
A chessboard contains:
The black knight can be placed on any square:
After placing the black knight, the white knight can be placed on any remaining square:
Thus, the total number of placements is:
n × m × (n × m − 1)
This count includes both attacking and non-attacking configurations.
Step 2: Count Attacking Configurations
Instead of directly counting non-attacking arrangements, it is easier to subtract the attacking arrangements from the total.
A knight attacks another knight only when both lie inside a:
2 × 3 rectangle
3 × 2 rectangle
Consider a 2 × 3 rectangle:
* * *
* * *
Inside this rectangle, there are exactly 4 attacking knight pairs.
The number of 2 × 3 rectangles on the board is:
(n − 1) × (m − 2)
So, attacking pairs contributed by these rectangles:
4 × (n − 1) × (m − 2)
Similarly, for 3 × 2 rectangles:
The number of such rectangles is:
(n − 2) × (m − 1)
They contribute:
4 × (n − 2) × (m − 1)
Therefore, the total attacking arrangements are:
4 × ((n − 1) × (m − 2) + (n − 2) × (m − 1))
Step 3: Compute the Answer
The required number of non-attacking placements is:
Total Placements − Attacking Placements
Hence:
n × m × (n × m − 1)
− 4 × ((n − 1) × (m − 2) + (n − 2) × (m − 1))
Algorithm
Calculate the total number of placements.
Calculate attacking configurations using the rectangle formula.
Subtract attacking configurations from the total.
Return the result.
Java Solution
class Solution {
public int numOfWays(int n, int m) {
int totalWays = n * m * (n * m - 1);
int attackingPairs = 0;
if (n >= 2 && m >= 3) {
attackingPairs += 4 * (n - 1) * (m - 2);
}
if (n >= 3 && m >= 2) {
attackingPairs += 4 * (n - 2) * (m - 1);
}
return totalWays - attackingPairs;
}
}
Example 1
Input
n = 2, m = 2
Calculation
Total placements:
4 × 3 = 12
There are no possible knight attacks.
Output
12
Example 2
Input
n = 2, m = 3
Calculation
Total placements:
6 × 5 = 30
Attacking placements:
4 × (1 × 1) = 4
Answer:
30 − 4 = 26
Output
26
Complexity Analysis
Time Complexity
O(1)
Only a few arithmetic operations are performed.
Space Complexity
O(1)
No extra space is used.
Key Insight
The trick is realizing that every knight attack occurs within a 2 × 3 or 3 × 2 rectangle, and each such rectangle contributes exactly 4 attacking arrangements. Once these attacking configurations are counted, the answer can be obtained by subtracting them from the total number of possible placements.
Summary
To count valid placements of one black knight and one white knight on an n × m chessboard, first calculate all possible ordered placements. Then count the attacking arrangements by observing that every knight attack occurs inside a 2 × 3 or 3 × 2 rectangle. Subtracting these attacking configurations from the total placements gives the number of non-attacking arrangements in constant time and constant space.