Definition
- N-Queens – place n chess queens on an n-by-n board so that no two share a row, column, or diagonal.
- Row-by-row backtracking – fill one row at a time, trying each column and placing a queen only where no conflict exists.
- Constraint sets – three sets track occupied columns, occupied
row - coldiagonals, and occupiedrow + coldiagonals for O(1) conflict checks. - Backtracking – place a queen (add three keys), recurse to the next row, then remove the three keys to try the next column.
- Complexity – far below n^n due to pruning, but still super-polynomial.
Imagine the National Bank of India must place n audit checkpoints on an n-by-n scheduling grid where no two checkpoints may share a column or a diagonal time slot. A scheduler fills one row at a time, placing a checkpoint only in a safe column, and backs up whenever a row has no safe spot.
Understanding the Concepts
What is the N-Queens problem?
Place n queens on an n-by-n chessboard so that no two queens attack each other. Queens attack along rows, columns, and diagonals. Since we place exactly one queen per row, the row conflict is automatically avoided. The challenge is avoiding column and diagonal conflicts.
This is LeetCode 51 (N-Queens) and 52 (N-Queens II for count only).
package com.bank.service;
// 4-Queens: one valid solution
// . Q . .
// . . . Q
// Q . . .
// . . Q .
How do the three constraint sets work?
- For O(1) conflict detection, maintain three
HashSetvalues: cols: which columns are occupied.diag1: whichrow - colvalues are occupied (down-right diagonal).diag2: whichrow + colvalues are occupied (down-left diagonal).
Cells on the same down-right diagonal share the same row - col value. Cells on the same down-left diagonal share the same row + col value. A cell at (r, c) is safe exactly when cols, diag1, and diag2 do not contain c, r-c, and r+c respectively.
package com.bank.service;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class NQueens {
private int count = 0;
public List<List<String>> solveNQueens(int n) {
List<List<String>> solutions = new ArrayList<>();
Set<Integer> cols = new HashSet<>();
Set<Integer> diag1 = new HashSet<>(); // row - col
Set<Integer> diag2 = new HashSet<>(); // row + col
int[] queens = new int[n]; // queens[row] = col
backtrack(n, 0, queens, cols, diag1, diag2, solutions);
return solutions;
}
private void backtrack(int n, int row, int[] queens,
Set<Integer> cols, Set<Integer> diag1,
Set<Integer> diag2,
List<List<String>> solutions) {
if (row == n) {
solutions.add(buildBoard(queens, n));
count++;
return;
}
for (int col = 0; col < n; col++) {
if (cols.contains(col) || diag1.contains(row - col)
|| diag2.contains(row + col)) {
continue; // conflict
}
queens[row] = col;
cols.add(col);
diag1.add(row - col);
diag2.add(row + col);
backtrack(n, row + 1, queens, cols, diag1, diag2, solutions);
cols.remove(col);
diag1.remove(row - col);
diag2.remove(row + col);
}
}
private List<String> buildBoard(int[] queens, int n) {
List<String> board = new ArrayList<>();
for (int row = 0; row < n; row++) {
char[] line = new char[n];
java.util.Arrays.fill(line, '.');
line[queens[row]] = 'Q';
board.add(new String(line));
}
return board;
}
public static void main(String[] args) {
NQueens solver = new NQueens();
List<List<String>> solutions = solver.solveNQueens(4);
System.out.println("4-Queens solutions: " + solutions.size());
for (List<String> sol : solutions) {
sol.forEach(System.out::println);
System.out.println();
}
}
}
4-Queens solutions: 2
.Q..
...Q
Q...
..Q.
..Q.
Q...
...Q
.Q..
Why does row-minus-col identify a diagonal?
All cells on the same down-right diagonal have the same value of row - col. For example, (0,0), (1,1), (2,2) all have row-col = 0. Similarly, (0,1), (1,2), (2,3) all have row-col = -1. This arithmetic identity lets you check diagonal conflicts with a single set lookup.
All cells on the same down-left diagonal have the same value of row + col. For example, (0,2), (1,1), (2,0) all have row+col = 2.
package com.bank.service;
public class DiagonalIdentity {
public static void main(String[] args) {
// Down-right diagonal (row - col is constant)
System.out.println("(0,0): " + (0-0)); // 0
System.out.println("(1,1): " + (1-1)); // 0
System.out.println("(2,2): " + (2-2)); // 0
// Down-left diagonal (row + col is constant)
System.out.println("(0,2): " + (0+2)); // 2
System.out.println("(1,1): " + (1+1)); // 2
System.out.println("(2,0): " + (2+0)); // 2
}
}
(0,0): 0
(1,1): 0
(2,2): 0
(0,2): 2
(1,1): 2
(2,0): 2
What about the bitmask optimization?
The bitmask version replaces the three sets with three integers, using bit manipulation to find free columns in just a few instructions. This is much faster for large n.
package com.bank.service;
public class NQueensBitmask {
private int count = 0;
public int totalNQueens(int n) {
count = 0;
solve(n, 0, 0, 0, 0);
return count;
}
private void solve(int n, int row, int cols, int diag1, int diag2) {
if (row == n) {
count++;
return;
}
int available = ((1 << n) - 1) & ~(cols | diag1 | diag2);
while (available != 0) {
int bit = available & (-available); // lowest set bit
available ^= bit;
solve(n, row + 1,
cols | bit,
(diag1 | bit) << 1,
(diag2 | bit) >> 1);
}
}
public static void main(String[] args) {
NQueensBitmask solver = new NQueensBitmask();
for (int n = 1; n <= 10; n++) {
System.out.println("n=" + n + ": " + solver.totalNQueens(n) + " solutions");
}
}
}
n=1: 1 solutions
n=2: 0 solutions
n=3: 0 solutions
n=4: 2 solutions
n=5: 10 solutions
n=6: 4 solutions
n=7: 40 solutions
n=8: 92 solutions
n=9: 352 solutions
n=10: 724 solutions
What are the edge cases?
- n = 1: one solution, a single queen on the only cell.
- n = 2 and n = 3: no solutions exist because there is no way to place queens without conflicts.
- n = 8: the classic problem with 92 solutions.
- Large n: the solution count grows but the search time grows super-polynomially.
What are common mistakes?
- Scanning the entire board for conflicts instead of using the three sets, which is O(n) per check instead of O(1).
- Forgetting to remove the constraint keys on backtrack.
- Not recording the column placement in a way that allows building the board at the base case.
// WRONG: O(n) conflict check by scanning placed queens
for (int prevRow = 0; prevRow < row; prevRow++) {
if (queens[prevRow] == col || /* diagonal check */) {
// slow, repeated for every candidate
}
}
// CORRECT: O(1) conflict check with three sets
if (cols.contains(col) || diag1.contains(row - col)
|| diag2.contains(row + col)) {
continue;
}
What about the banking domain use case?
At the National Bank of India, compliance needs to assign n non-conflicting audit checkpoints to an n-by-n schedule grid where no two checkpoints share a column (same auditor) or a diagonal (same time-distance). The row-by-row backtracking with constant-time conflict sets finds all valid assignments.
package com.bank.service;
public class AuditScheduler {
public static void main(String[] args) {
NQueens solver = new NQueens();
int n = 5;
int solutions = solver.solveNQueens(n).size();
System.out.println("Valid audit schedules for " + n + " checkpoints: " + solutions);
}
}
Valid audit schedules for 5 checkpoints: 10
What are common interview follow-up questions?
- What is the time complexity? (Super-polynomial but much less than n^n due to pruning.)
- How do you detect diagonal conflicts in O(1)? (row-col and row+col sets.)
- Can you optimize using symmetry? (Yes, only try the first half of columns in row 0 and mirror.)
- What is the bitmask approach? (Three integers replace the three sets; bitwise ops find free columns.)
- How many solutions for n=8? (92.)
Visual Overview
N-Queens Backtracking (n=4)
Row 0: try col 0,1,2,3
Row 1: try cols not in {col, diag1, diag2}
Row 2: same constraint check
Row 3: same constraint check -> if all placed, record
Constraint sets for O(1) check:
┌────────────────────────────────────────┐
│ cols: which columns are taken │
│ diag1: which (row - col) are taken │
│ diag2: which (row + col) are taken │
└────────────────────────────────────────┘
Solution 1: Solution 2:
. Q . . . . Q .
. . . Q Q . . .
Q . . . . . . Q
. . Q . . Q . .
Key Takeaway
N-Queens is the classic constraint-satisfaction backtracking problem. You place one queen per row and for each row try every column, placing a queen only where it does not conflict with any already-placed queen. The key to fast conflict detection is tracking three sets: occupied columns, one diagonal family keyed by row - col, and the other keyed by row + col. A cell is safe when all three lookups miss.
Placing a queen adds three keys to the sets, recursing fills the next row, and backtracking removes the keys. Reaching row n means all queens are safely placed and you record the configuration. The pruning from the three sets keeps the real search far below the naive n^n bound.
The bitmask optimization replaces the three sets with three integers and uses bitwise operations to find free columns in just a few instructions, which is much faster for large n. Symmetry-based pruning can nearly halve the work by only exploring the first half of columns in the first row.
At the National Bank of India, compliance used this pattern to assign n audit checkpoints to a scheduling grid where no two could share a column or diagonal, finding all valid arrangements efficiently with constant-time conflict checks.
Remember one sentence: one queen per row, three constraint sets for O(1) diagonal checks, and backtrack when a row has no safe column.
---