Definition
- N-Queens – place n chess queens on an n-by-n board so that no two share a row, column, or diagonal.
- One queen per row – since each row must have exactly one queen, the decision is which column to choose for each row.
- Constraint sets – three sets (columns, row-col diagonals, row+col diagonals) provide O(1) conflict checks.
- Backtracking – add three keys on placement, recurse to the next row, remove three keys to try the next column.
- Base case – row index equals n means all rows have safe queens; count or record the configuration.
- Complexity – super-polynomial but far below n^n due to heavy pruning.
Imagine the National Bank of India must schedule n critical daily jobs on n servers so that no two jobs clash on the same resource line, where clash rules mirror a queen's reach: same column or either diagonal. A scheduler fills one job per row, skips clashing columns, and backs up whenever a row has no free spot. Every complete non-clashing schedule is one valid solution.
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 both diagonals. Since we place exactly one queen per row, row conflicts are automatically avoided. The challenge is column and diagonal conflicts.
This is LeetCode 51 (return all boards) and LeetCode 52 (return count only).
package com.bank.service;
// N=4 has 2 solutions:
// Solution 1: Solution 2:
// .Q.. ..Q.
// ...Q Q...
// Q... ...Q
// ..Q. .Q..
How does one-queen-per-row shrink the search?
The naive approach would try every cell on the board. But since each row must contain exactly one queen, you only need to choose a column for each row. That reduces the problem from n-squared choices to at most n choices per row, which is at most n^n branches before pruning.
How do the three constraint sets enable O(1) conflict checks?
- Maintain three
HashSetvalues: cols: occupied columns.diag1: occupiedrow - colvalues (down-right diagonals).diag2: occupiedrow + colvalues (down-left diagonals).
Cells on the same down-right diagonal share row - col. Cells on the same down-left diagonal share row + col. A cell at (r, c) is safe exactly when cols does not contain c, diag1 does not contain r - c, and diag2 does not contain r + c.
package com.bank.service;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class NQueensSolver {
public List<List<String>> solveNQueens(int n) {
List<List<String>> solutions = new ArrayList<>();
int[] queens = new int[n]; // queens[row] = col
Set<Integer> cols = new HashSet<>();
Set<Integer> diag1 = new HashSet<>();
Set<Integer> diag2 = new HashSet<>();
solve(n, 0, queens, cols, diag1, diag2, solutions);
return solutions;
}
private void solve(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));
return;
}
for (int col = 0; col < n; col++) {
if (cols.contains(col) || diag1.contains(row - col)
|| diag2.contains(row + col)) {
continue;
}
queens[row] = col;
cols.add(col);
diag1.add(row - col);
diag2.add(row + col);
solve(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) {
NQueensSolver solver = new NQueensSolver();
List<List<String>> solutions = solver.solveNQueens(4);
System.out.println("4-Queens: " + solutions.size() + " solutions");
for (List<String> sol : solutions) {
sol.forEach(System.out::println);
System.out.println();
}
}
}
4-Queens: 2 solutions
.Q..
...Q
Q...
..Q.
..Q.
Q...
...Q
.Q..
What about the bitmask optimization?
Replace the three sets with three integers. Use bitwise OR to mark conflicts and bitwise AND with complement to find free columns. The lowest set bit trick extracts one free column at a time.
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 d1, int d2) {
if (row == n) { count++; return; }
int free = ((1 << n) - 1) & ~(cols | d1 | d2);
while (free != 0) {
int bit = free & (-free);
free ^= bit;
solve(n, row + 1, cols | bit, (d1 | bit) << 1, (d2 | bit) >> 1);
}
}
public static void main(String[] args) {
NQueensBitmask solver = new NQueensBitmask();
for (int n = 4; n <= 12; n++) {
System.out.println("n=" + n + ": " + solver.totalNQueens(n) + " 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
n=11: 2680 solutions
n=12: 14200 solutions
How does symmetry reduce the search?
The board has vertical symmetry. If a queen is placed in the left half of the first row, the mirrored placement in the right half produces a symmetric solution. By only trying columns 0 to (n-1)/2 in row 0 and doubling the count (adjusting for the center column when n is odd), you nearly halve the search.
What are the edge cases?
- n = 1: one solution, a single queen on the only cell.
- n = 2 and n = 3: zero solutions; no valid placement exists.
- n = 8: the classic problem with 92 distinct solutions.
package com.bank.service;
public class NQueensEdgeCases {
public static void main(String[] args) {
NQueensSolver solver = new NQueensSolver();
System.out.println("n=1: " + solver.solveNQueens(1).size() + " solutions");
System.out.println("n=2: " + solver.solveNQueens(2).size() + " solutions");
System.out.println("n=3: " + solver.solveNQueens(3).size() + " solutions");
}
}
n=1: 1 solutions
n=2: 0 solutions
n=3: 0 solutions
What are common mistakes?
- Using O(n) board scanning for conflict checks instead of the O(1) sets.
- Forgetting to remove the three constraint keys on backtrack.
- Not recording the queen column in a way that allows board reconstruction at the base case.
// WRONG: O(n) scan per candidate column
boolean safe = true;
for (int prevRow = 0; prevRow < row; prevRow++) {
if (queens[prevRow] == col || Math.abs(queens[prevRow] - col) == row - prevRow) {
safe = false;
break;
}
}
// CORRECT: O(1) set check
if (!cols.contains(col) && !diag1.contains(row - col) && !diag2.contains(row + col)) {
// safe
}
What about the banking domain use case?
At the National Bank of India, the constraint scheduler assigns n critical jobs to n time-server slots where no two jobs can share a resource line modeled like a queen's reach. The three-set backtracking finds all valid assignments, and the bitmask version handles larger scheduling grids efficiently.
package com.bank.service;
public class ConstraintScheduler {
public static void main(String[] args) {
NQueensSolver solver = new NQueensSolver();
int n = 6; // 6 jobs, 6 server slots
int count = solver.solveNQueens(n).size();
System.out.println("Valid schedules for " + n + " jobs: " + count);
}
}
Valid schedules for 6 jobs: 4
What are common interview follow-up questions?
- How do you check diagonals in O(1)? (row - col and row + col sets.)
- What is the time complexity? (Super-polynomial but much less than n^n.)
- How many solutions for n = 8? (92.)
- Can you optimize further? (Symmetry halving, bitmask encoding.)
- How does this relate to Sudoku? (Same paradigm: constraint-satisfaction backtracking with set-based pruning.)
Visual Overview
N-Queens Backtracking (n=4)
Three constraint sets for O(1) checks:
┌─────────────────────────────────────┐
│ cols: {occupied columns} │
│ diag1: {row - col values} │
│ diag2: {row + col values} │
└─────────────────────────────────────┘
Row 0: try cols 0-3, place where sets allow
Row 1: try cols not in any of three sets
Row 2: same check
Row 3: same check -> base case, record
Solution 1: Solution 2:
. Q . . . . Q .
. . . Q Q . . .
Q . . . . . . Q
. . Q . . Q . .
Add 3 keys → recurse → remove 3 keys (backtrack)
Key Takeaway
The N-Queens problem places n queens on an n-by-n board so that no two share a row, column, or diagonal. The single most important insight is that exactly one queen goes in each row, so you just choose a safe column for each row and recurse. Three constraint sets (columns, row-col diagonals, row+col diagonals) make each safety check constant time.
Placing a queen adds three keys to the sets, recursing fills the next row, and backtracking removes the keys. When the row index reaches n, all rows are safely filled and one solution is recorded or counted. The pruning keeps the real search far below n^n, though it remains super-polynomial.
The bitmask optimization replaces the three sets with integers and uses bitwise operations to find free columns in a few instructions, which is much faster for larger n. Symmetry-based pruning nearly halves the first-row exploration.
At the National Bank of India, the constraint scheduler used this paradigm to assign critical jobs to non-conflicting server slots, modeling the clash rules as column and diagonal constraints. N-Queens is the textbook example of constraint-satisfaction backtracking, the same paradigm that powers Sudoku solvers and general CSP engines.
Remember one sentence: one queen per row, three constraint sets for O(1) checks, and backtrack when no column is safe.
---