N-Queens Problem Using Backtracking
The Puzzle
Place n queens on an n × n chessboard so that no two queens attack each other. A queen attacks along its row, its column, and both diagonals.
One valid layout for n = 4:
c0 c1 c2 c3
r0 . Q . .
r1 . . . Q
r2 Q . . .
r3 . . Q .
Queens at (0,1) (1,3) (2,0) (3,2)
- all rows different ✓
- all columns different ✓
- no shared diagonal ✓
Typical tasks: list every valid board, count them, or find any one.
Shrinking the Search Before Writing Code
NAIVE: choose n squares out of n² C(64, 8) ≈ 4.4 billion for n = 8
ROW RULE: exactly one queen per row
→ each row just picks a column 8^8 ≈ 16.8 million
COLUMN RULE: columns must differ too
→ each row picks an unused column 8! = 40,320
DIAGONAL CHECK while placing
→ the real search for n = 8 about 2,000 placements tried
So the decision tree is: level = row, branches = columns, prune any square attacked by a queen in an earlier row.
Checking Attacks in O(1)
Instead of scanning the board, keep three boolean arrays:
cols[c] → column c already has a queen
diag1[r - c] → a "\" diagonal is taken (r - c is constant along it)
diag2[r + c] → a "/" diagonal is taken (r + c is constant along it)
For n = 4, the value of r - c on each square:
c0 c1 c2 c3
r0 0 -1 -2 -3
r1 1 0 -1 -2
r2 2 1 0 -1
r3 3 2 1 0 ← each "\" diagonal has one value
r - c ranges over -(n-1) .. n-1 → store at index r - c + n - 1
r + c ranges over 0 .. 2n-2 → store at index r + c
A square (r, c) is safe ⇔ !cols[c] && !diag1[r-c+n-1] && !diag2[r+c]
The Search
place(r):
if r == n: record the board; return
for c in 0 .. n-1:
if square (r, c) is attacked: continue ← prune
mark cols[c], diag1[r-c+n-1], diag2[r+c] ← choose
place(r + 1) ← explore
unmark the same three entries ← un-choose
Tracing n = 4
r0: try c0 → Q at (0,0)
r1: c0 col ✗, c1 diag ✗, c2 ok → Q at (1,2)
r2: c0 col ✗, c1 diag ✗, c2 col ✗, c3 diag ✗ → dead end, undo (1,2)
r1: c3 ok → Q at (1,3)
r2: c0 col ✗, c1 ok → Q at (2,1)
r3: c0 col ✗, c1 col ✗, c2 diag ✗, c3 col ✗ → dead end, undo (2,1)
r2: c2 diag ✗, c3 col ✗ → dead end, undo (1,3)
r1: no columns left → undo (0,0)
r0: try c1 → Q at (0,1)
r1: c0 diag ✗, c1 col ✗, c2 diag ✗, c3 ok → Q at (1,3)
r2: c0 ok → Q at (2,0)
r3: c0 col ✗, c1 col ✗, c2 ok → Q at (3,2) → SOLUTION [1, 3, 0, 2]
r0: try c2 → mirror image of c1 → SOLUTION [2, 0, 3, 1]
r0: try c3 → mirror image of c0 → no solution
Total for n = 4: 2 solutions
Code: Boolean Arrays + Bitmask Counter
The first function lists every board and is easy to read. The second counts solutions using three integers as bitsets — the fastest common form.
import java.util.ArrayList;
import java.util.List;
public class NQueens {
static int n;
static int[] queenCol; // queenCol[r] = column of the queen in row r
static boolean[] cols, diag1, diag2;
static List<int[]> solutions;
static void place(int r) {
if (r == n) { solutions.add(queenCol.clone()); return; }
for (int c = 0; c < n; c++) {
if (cols[c] || diag1[r - c + n - 1] || diag2[r + c]) continue; // attacked
cols[c] = diag1[r - c + n - 1] = diag2[r + c] = true; // choose
queenCol[r] = c;
place(r + 1); // explore
cols[c] = diag1[r - c + n - 1] = diag2[r + c] = false; // un-choose
}
}
static List<int[]> solve(int size) {
n = size;
queenCol = new int[n];
cols = new boolean[n];
diag1 = new boolean[2 * n - 1];
diag2 = new boolean[2 * n - 1];
solutions = new ArrayList<>();
place(0);
return solutions;
}
// Bitmask counter: bits set in cols/d1/d2 are attacked columns for this row
static int count(int size, int row, int colMask, int d1, int d2) {
if (row == size) return 1;
int all = (1 << size) - 1;
int free = all & ~(colMask | d1 | d2);
int total = 0;
while (free != 0) {
int bit = free & -free; // lowest free column
free ^= bit;
total += count(size, row + 1, colMask | bit, (d1 | bit) << 1, (d2 | bit) >> 1);
}
return total;
}
public static void main(String[] args) {
List<int[]> six = solve(6);
int[] first = six.get(0);
System.out.println("First 6-queens board:");
for (int r = 0; r < 6; r++) {
StringBuilder row = new StringBuilder();
for (int c = 0; c < 6; c++) row.append(c == first[r] ? "Q " : ". ");
System.out.println(row.toString().trim());
}
System.out.print("n=4 boards as columns:");
for (int[] s : solve(4)) System.out.print(" " + java.util.Arrays.toString(s));
System.out.println();
StringBuilder counts = new StringBuilder("counts n=1..8:");
for (int k = 1; k <= 8; k++) counts.append(" ").append(count(k, 0, 0, 0, 0));
System.out.println(counts);
}
}Output:
First 6-queens board:
. Q . . . .
. . . Q . .
. . . . . Q
Q . . . . .
. . Q . . .
. . . . Q .
n=4 boards as columns: [1, 3, 0, 2] [2, 0, 3, 1]
counts n=1..8: 1 0 0 2 10 4 40 92
Note n = 2 and n = 3 have no solutions, and n = 6 has fewer solutions (4) than n = 5 (10). The counts do not grow smoothly.
How the Bitmask Version Works
Each row needs to know which columns are attacked from above. Three integers carry that information downward: colMask: bit c set → column c is taken d1: bit c set → a "\" diagonal reaches column c in THIS row d2: bit c set → a "/" diagonal reaches column c in THIS row Moving to the next row, "\" diagonals shift one column right (<< 1) and "/" diagonals shift one column left (>> 1). Bits pushed past the board edge are masked off by ((1 << n) - 1). free = all & ~(colMask | d1 | d2) → columns still safe in this row bit = free & -free → pick the lowest safe column
No arrays, no undo step — each recursive call receives new integers, so there is nothing to restore.
Complexity
TIME: O(n!) upper bound — row r has at most n - r unused columns.
Diagonal pruning makes the real number far smaller:
n = 8 tries about 2,000 placements, not 40,320.
Printing each board costs O(n²) extra per solution.
SPACE: O(n) — the call stack (n frames), queenCol, cols,
and the two diagonal arrays (2n - 1 each).
The bitmask version needs only O(n) stack and three ints per frame.
Variations
COUNT ONLY → bitmask counter, no board storage
FIND ANY ONE → return true as soon as row == n; stop the loop
SYMMETRY SPEED-UP → try only columns 0 .. n/2 - 1 in row 0 and double
the count (handle the middle column separately when n is odd)
PRE-PLACED QUEENS → mark their column/diagonals before searching and skip
their rows
OTHER PIECES → rooks (columns only → n! boards),
knights or kings need neighbourhood checks instead
The same "level = row, check constraints with sets" idea solves many scheduling and placement puzzles: assign each class to a time slot, each task to a worker, each region to a colour.
Common Mistakes
Using r - c directly as an index. It is negative for squares to the upper-right of the main diagonal. Shift it by n − 1.
Sizing the diagonal arrays as n. There are 2n − 1 diagonals in each direction.
Forgetting to unmark all three arrays. Unmarking only cols[c] leaves stale diagonals that wrongly block later placements — you will silently miss solutions.
Storing queenCol without copying. Every stored solution then shows the final contents of the shared array.
Checking the whole board on every placement. Correct but O(n) or O(n²) per check instead of O(1).
Interview Questions
Q: Why is checking only columns and diagonals enough — what about rows?
Rows are handled by the structure of the search itself. Each recursion level places exactly one queen in its own row and then moves to the next row, so two queens can never share a row.
Q: How would you modify the solution to return as soon as one board is found?
Make place return a boolean. When r == n, return true. In the loop, if the recursive call returns true, return true immediately without undoing the marks (or undo them if the caller needs the arrays clean). If the loop ends, return false.
Q: Explain the bitmask shifts for the diagonals.
A queen at column c in row r attacks column c + 1 in row r + 1 along one diagonal and column c − 1 along the other. Shifting the diagonal mask left by one moves every attacked "" diagonal one column right for the next row; shifting the other mask right by one does the same for "/" diagonals. Masking with (1 << n) − 1 discards bits that slid off the board.
Summary
- ›One queen per row turns the puzzle into "choose a column for each row".
- ›Track attacks with cols[c], diag1[r − c + n − 1], diag2[r + c] for O(1) checks.
- ›Mark three entries when placing, unmark the same three when backtracking.
- ›The bitmask version passes attack sets as integers — no undo, very fast counting.
- ›Solutions for n = 1…8: 1, 0, 0, 2, 10, 4, 40, 92.
Next, Sudoku Solver applies the same "track constraints in sets" idea to a 9 × 9 grid — with rows, columns, and 3 × 3 boxes all to satisfy at once.
Why does the standard solution place exactly one queen per row?