Non-Attacking Black and White Knights

Intuition

We need ordered placements of a black knight and a white knight that do not attack each other. Knight attacks are symmetric, but fixing which piece is black lets us count valid white positions independently for every cell. For a black knight at (i, j), any white square must avoid the black cell itself and all in-bounds knight-move attack squares.

Algorithm

1Let totalCell = n * m.
2For each cell (i, j) in the board:
3 Enumerate the 8 standard knight offsets.
4 Count how many of those attack cells stay inside the board.
5 Add (totalCell - attackCount - 1) to the answer.
6Return the accumulated total.

Example Walkthrough

Input: n = 2, m = 2

1.Board has 4 cells. Corner cells attack 2 squares; non-corner interior behavior depends on board size.
2.At corner (0,0): 2 valid attack cells in bounds, so white choices = 4 - 2 - 1 = 1.
3.Repeat for all 4 cells and sum the valid white placements.
4.Each non-attacking ordered pair is counted exactly once by the cell chosen as black.

Output: 12

Common Pitfalls

•Subtract 1 for the black knight cell itself in addition to its attack squares.
•Only count attack destinations that lie inside the n x m grid.
•Do not double-count unordered pairs unless the problem statement asks for ordered placements.

Non-Attacking Black and White Knights.java

Java

// Approach: For each cell as the black knight, count in-bounds knight-attack squares and add
// (n*m - attackCount - 1) valid white placements. Summing over all black positions counts every
// non-attacking ordered pair once.
// Time: O(n * m) Space: O(1)

class Solution {

    public int numOfWays(int n, int m) {
        int totalCell = n * m;
        int ways = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int[][] attackingCells = {{i - 1, j + 2}, {i + 1, j + 2}, {i + 2, j + 1}, {i + 2, j - 1}, {i + 1, j - 2}, {i - 1, j - 2}, {i - 2, j + 1}, {i - 2, j - 1}};
                int countValidCell = 0;

                for (int[] cell : attackingCells) {
                    int r = cell[0];
                    int c = cell[1];
                    if (r >= 0 && r < n && c >= 0 && c < m) {
                        countValidCell++;
                    }
                }
                ways += (totalCell - countValidCell - 1);
            }
        }
        
        return ways;
    }
}

Was this solution helpful?