These are the notes for DSA episode 33, a classic hard backtracking problem. Place n queens on an n x n chessboard so that no two attack each other, and return every such board. The obvious way puts one queen in every row, tries every column for every row and checks the finished board: it is correct for n = 4 and n = 8, but for n = 10 it builds 10^10 boards and hits the time limit. The fix is to check each square while placing (backtracking with pruning), with three boolean arrays that answer "is this square attacked?" in O(1): one for columns, one for the r + c diagonals and one for the r - c + n - 1 diagonals. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.
The problem, in real life
An exam hall has a 4 x 4 grid of benches, and only 4 students are writing today. A student can peek at any paper in the same row, the same column, or along either diagonal: exactly the eight directions a chess queen attacks in. The invigilator wants to seat the 4 students so that nobody can copy from anybody. How many safe seatings are there, and which are they? And for an 8 x 8 hall with 8 students, or 10 x 10 with 10?
| In the exam hall | In the code |
|---|---|
| The grid of benches | the board, char[][] b (n x n) |
| A student | a queen, 'Q' |
| An empty bench | '.' |
| "Can see along a row, column, diagonal" | a queen attacks along a row, column, diagonal |
| Seating the students one row at a time | place(n, r, ...) fills row r |
| "This bench is in someone's line of sight" | col[c] \|\| d1[r + c] \|\| d2[r - c + n - 1] |
Problem statement
N-Queens (LeetCode 51). Given an integer n, return all distinct ways to place n queens on an n x n board so that no two queens attack each other. Each board is a list of n strings, with 'Q' for a queen and '.' for an empty square. N-Queens II (LeetCode 52) asks only for the number of boards.
n = 4 → [[.Q.., ...Q, Q..., ..Q.], [..Q., Q..., ...Q, .Q..]]
n = 1 → [[Q]]
n = 2 → [] n = 3 → [] n = 8 → 92 boards
Constraints on LeetCode: 1 ≤ n ≤ 9. In the video we push to n = 13.
The number of boards for n = 1, 2, 3, ... is 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712. It does not grow smoothly: 6 has fewer boards than 5.
Brute force: try every board, check at the end
Two queens in the same row always attack each other, so every row holds exactly one queen. A board is therefore just an array q, where q[row] is the column of that row's queen. The obvious way tries every column for every row, and checks each finished board pair by pair. Two queens in rows i < j clash if they share a column (q[i] == q[j]) or a diagonal: on a diagonal, the column distance equals the row distance (|q[i] - q[j]| == j - i).
import java.util.*;
public class Main {
static int count = 0;
static void brute(int n, int row, int[] q) {
if (row == n) {
if (valid(q)) count++;
return;
}
for (int c = 0; c < n; c++) {
q[row] = c;
brute(n, row + 1, q);
}
}
static boolean valid(int[] q) {
for (int i = 0; i < q.length; i++)
for (int j = i + 1; j < q.length; j++)
if (q[i] == q[j] || Math.abs(q[i] - q[j]) == j - i)
return false;
return true;
}
public static void main(String[] args) {
for (int n : new int[]{4, 8}) {
count = 0;
brute(n, 0, new int[n]);
System.out.println("n = " + n + ": " + count + " ways");
}
}
}
Real output:
n = 4: 2 ways
n = 8: 92 ways
Correct. Now n = 10:
import java.util.*;
public class Main {
static int count = 0;
static void brute(int n, int row, int[] q) {
if (row == n) {
if (valid(q)) count++;
return;
}
for (int c = 0; c < n; c++) {
q[row] = c;
brute(n, row + 1, q);
}
}
static boolean valid(int[] q) {
for (int i = 0; i < q.length; i++)
for (int j = i + 1; j < q.length; j++)
if (q[i] == q[j] || Math.abs(q[i] - q[j]) == j - i)
return false;
return true;
}
public static void main(String[] args) {
int n = 10;
long t0 = System.nanoTime();
brute(n, 0, new int[n]);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println(count + " ways, " + ms + " ms");
}
}
Real result: Time Limit Exceeded. (On my machine n = 9 already took about 2.5 seconds.)
Why the brute force fails
| n | Boards built (n^n) | Answers |
|---|---|---|
| 4 | 256 | 2 |
| 8 | 1,67,77,216 (1.7 crore) | 92 |
| 10 | 10,000,000,000 (1,000 crore) | 724 |
It finishes every board before checking anything. The very first boards have row 0 and row 1 both in column 0, which already clash, yet for n = 10 the brute force still fills rows 2 to 9 on top of them: 10^8 complete boards that were doomed from row 1. Each check then costs O(n²) pairs. The question is: can we notice a clash the moment it happens?
The key insight: check while placing
Still fill the board row by row, still try each column, but check the square before placing the queen:
- To fill row
r, try each columnc. - If square
(r, c)is attacked by a queen already placed, skip it now. - If it is safe: place the queen, recurse into row
r + 1, then remove the queen and try the next column (choose → explore → un-choose). - If
r == n, every row has a safe queen: save the board.
This is pruning: skipping one bad square in row 1 skips every board that would have been built on top of it. For n = 4 the whole search makes only 17 calls, compared with 256 boards.
The search on a 4 x 4 board:
| Step | What happens |
|---|---|
| Row 0 → column 0 | free |
| Row 1 | column 0 (same column) and column 1 (diagonal) skipped; column 2 placed |
| Row 2 | all 4 squares attacked: dead end, return and un-place row 1 |
| Row 1 → column 3, row 2 → column 1 | |
| Row 3 | all 4 squares attacked again; a queen in the corner has no answer |
| Row 0 → column 1 | row 1 → 3, row 2 → 0, row 3 → 2: first answer .Q.. / ...Q / Q... / ..Q. |
| Continue | the mirror image ..Q. / Q... / ...Q / .Q.. is the second answer |
O(1) attack checks: numbering the diagonals
Checking every queen above a square costs O(n). Instead, keep three boolean arrays:
| Array | Size | Meaning | Why it works |
|---|---|---|---|
col[c] |
n |
is column c taken? |
— |
d1[r + c] |
2n - 1 |
is this ↙ diagonal taken? | going down one row and left one column keeps r + c the same; it ranges 0 .. 2n - 2 |
d2[r - c + n - 1] |
2n - 1 |
is this ↘ diagonal taken? | going down one and right one keeps r - c the same; it ranges -(n - 1) .. n - 1, so add n - 1 to start at 0 |
For n = 4: squares (0,3) (1,2) (2,1) (3,0) all have r + c = 3; squares (0,1) (1,2) (2,3) all have r - c = -1, which becomes index 2 after adding n - 1 = 3. The top-right corner (0,3) has r - c = -3: without the shift that is a negative index and a crash.
The whole check is one line:
if (col[c] || d1[r + c] || d2[r - c + n - 1]) continue;
The optimal solution in Java
import java.util.*;
public class Main {
static void place(int n, int r, char[][] b, boolean[] col, boolean[] d1,
boolean[] d2, List<List<String>> res) {
if (r == n) {
List<String> board = new ArrayList<>();
for (char[] row : b) board.add(new String(row));
res.add(board);
return;
}
for (int c = 0; c < n; c++) {
if (col[c] || d1[r + c] || d2[r - c + n - 1]) continue;
b[r][c] = 'Q';
col[c] = d1[r + c] = d2[r - c + n - 1] = true;
place(n, r + 1, b, col, d1, d2, res);
b[r][c] = '.';
col[c] = d1[r + c] = d2[r - c + n - 1] = false;
}
}
static List<List<String>> solveNQueens(int n) {
char[][] b = new char[n][n];
for (char[] row : b) Arrays.fill(row, '.');
List<List<String>> res = new ArrayList<>();
place(n, 0, b, new boolean[n], new boolean[2 * n - 1],
new boolean[2 * n - 1], res);
return res;
}
public static void main(String[] args) {
System.out.println(solveNQueens(4));
System.out.println(solveNQueens(1));
System.out.println(solveNQueens(2));
System.out.println(solveNQueens(3));
System.out.println(solveNQueens(8).size());
}
}
Real output:
[[.Q.., ...Q, Q..., ..Q.], [..Q., Q..., ...Q, .Q..]]
[[Q]]
[]
[]
92
The bigger boards that timed out before:
import java.util.*;
public class Main {
static void place(int n, int r, char[][] b, boolean[] col, boolean[] d1,
boolean[] d2, List<List<String>> res) {
if (r == n) {
List<String> board = new ArrayList<>();
for (char[] row : b) board.add(new String(row));
res.add(board);
return;
}
for (int c = 0; c < n; c++) {
if (col[c] || d1[r + c] || d2[r - c + n - 1]) continue;
b[r][c] = 'Q';
col[c] = d1[r + c] = d2[r - c + n - 1] = true;
place(n, r + 1, b, col, d1, d2, res);
b[r][c] = '.';
col[c] = d1[r + c] = d2[r - c + n - 1] = false;
}
}
static List<List<String>> solveNQueens(int n) {
char[][] b = new char[n][n];
for (char[] row : b) Arrays.fill(row, '.');
List<List<String>> res = new ArrayList<>();
place(n, 0, b, new boolean[n], new boolean[2 * n - 1],
new boolean[2 * n - 1], res);
return res;
}
public static void main(String[] args) {
for (int n : new int[]{10, 12, 13}) {
long t0 = System.nanoTime();
int k = solveNQueens(n).size();
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("n = " + n + ": " + k + " ways, " + ms + " ms");
}
}
}
Real output (times vary a little between runs):
n = 10: 724 ways, 6 ms
n = 12: 14200 ways, 198 ms
n = 13: 73712 ways, 470 ms
For n = 10 the search makes about 35,000 calls instead of building 10^10 boards.
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
void place(int n, int r, vector<string>& b, vector<bool>& col, vector<bool>& d1,
vector<bool>& d2, vector<vector<string>>& res) {
if (r == n) { res.push_back(b); return; }
for (int c = 0; c < n; c++) {
if (col[c] || d1[r + c] || d2[r - c + n - 1]) continue;
b[r][c] = 'Q';
col[c] = d1[r + c] = d2[r - c + n - 1] = true;
place(n, r + 1, b, col, d1, d2, res);
b[r][c] = '.';
col[c] = d1[r + c] = d2[r - c + n - 1] = false;
}
}
vector<vector<string>> solveNQueens(int n) {
vector<string> b(n, string(n, '.'));
vector<bool> col(n), d1(2 * n - 1), d2(2 * n - 1);
vector<vector<string>> res;
place(n, 0, b, col, d1, d2, res);
return res;
}
int main() {
for (auto& board : solveNQueens(4)) {
for (auto& row : board) cout << row << ' ';
cout << '\n';
}
for (int n : {1, 2, 3, 8, 10}) cout << "n = " << n << ": " << solveNQueens(n).size() << '\n';
}
Output: the two boards for n = 4, then n = 1: 1, n = 2: 0, n = 3: 0, n = 8: 92, n = 10: 724.
The same solution in Python
def solve_n_queens(n):
res, board = [], [["."] * n for _ in range(n)]
col, d1, d2 = [False] * n, [False] * (2 * n - 1), [False] * (2 * n - 1)
def place(r):
if r == n:
res.append(["".join(row) for row in board])
return
for c in range(n):
if col[c] or d1[r + c] or d2[r - c + n - 1]:
continue
board[r][c] = "Q"
col[c] = d1[r + c] = d2[r - c + n - 1] = True
place(r + 1)
board[r][c] = "."
col[c] = d1[r + c] = d2[r - c + n - 1] = False
place(0)
return res
print(solve_n_queens(4))
for n in (1, 2, 3, 8):
print("n =", n, ":", len(solve_n_queens(n)))
Output: [['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..']], then 1, 0, 0 and 92.
Three real bugs
Bug 1: d2[r - c] without the shift
import java.util.*;
public class Main {
static void place(int n, int r, char[][] b, boolean[] col, boolean[] d1,
boolean[] d2, List<List<String>> res) {
if (r == n) {
List<String> board = new ArrayList<>();
for (char[] row : b) board.add(new String(row));
res.add(board);
return;
}
for (int c = 0; c < n; c++) {
if (col[c] || d1[r + c] || d2[r - c]) continue;
b[r][c] = 'Q';
col[c] = d1[r + c] = d2[r - c] = true;
place(n, r + 1, b, col, d1, d2, res);
b[r][c] = '.';
col[c] = d1[r + c] = d2[r - c] = false;
}
}
static List<List<String>> solveNQueens(int n) {
char[][] b = new char[n][n];
for (char[] row : b) Arrays.fill(row, '.');
List<List<String>> res = new ArrayList<>();
place(n, 0, b, new boolean[n], new boolean[2 * n - 1],
new boolean[2 * n - 1], res);
return res;
}
public static void main(String[] args) {
System.out.println(solveNQueens(4));
}
}
Real output:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 7
at Main.place(Main.java:13)
Row 1, column 2: 1 - 2 = -1. Always use r - c + n - 1.
Bug 2: forgetting to un-mark
The queen is removed from the board (b[r][c] = '.'), but col, d1, d2 are never set back to false:
import java.util.*;
public class Main {
static void place(int n, int r, char[][] b, boolean[] col, boolean[] d1,
boolean[] d2, List<List<String>> res) {
if (r == n) {
List<String> board = new ArrayList<>();
for (char[] row : b) board.add(new String(row));
res.add(board);
return;
}
for (int c = 0; c < n; c++) {
if (col[c] || d1[r + c] || d2[r - c + n - 1]) continue;
b[r][c] = 'Q';
col[c] = d1[r + c] = d2[r - c + n - 1] = true;
place(n, r + 1, b, col, d1, d2, res);
b[r][c] = '.';
}
}
static List<List<String>> solveNQueens(int n) {
char[][] b = new char[n][n];
for (char[] row : b) Arrays.fill(row, '.');
List<List<String>> res = new ArrayList<>();
place(n, 0, b, new boolean[n], new boolean[2 * n - 1],
new boolean[2 * n - 1], res);
return res;
}
public static void main(String[] args) {
System.out.println(solveNQueens(4));
System.out.println(solveNQueens(8).size());
}
}
Real output: [] and 0. After the first dead end, the old queen's column and diagonals stay marked forever, so nothing fits again. Every choose needs its un-choose.
Bug 3: checking only the columns
import java.util.*;
public class Main {
static void place(int n, int r, char[][] b, boolean[] col, boolean[] d1,
boolean[] d2, List<List<String>> res) {
if (r == n) {
List<String> board = new ArrayList<>();
for (char[] row : b) board.add(new String(row));
res.add(board);
return;
}
for (int c = 0; c < n; c++) {
if (col[c]) continue;
b[r][c] = 'Q';
col[c] = d1[r + c] = d2[r - c + n - 1] = true;
place(n, r + 1, b, col, d1, d2, res);
b[r][c] = '.';
col[c] = d1[r + c] = d2[r - c + n - 1] = false;
}
}
static List<List<String>> solveNQueens(int n) {
char[][] b = new char[n][n];
for (char[] row : b) Arrays.fill(row, '.');
List<List<String>> res = new ArrayList<>();
place(n, 0, b, new boolean[n], new boolean[2 * n - 1],
new boolean[2 * n - 1], res);
return res;
}
public static void main(String[] args) {
System.out.println(solveNQueens(4).size());
System.out.println(solveNQueens(8).size());
}
}
Real output: 24 and 40320. Those are 4! and 8!: every way to give each row a different column. Diagonal attacks were never checked.
Complexity
| Approach | Time | Extra space | n = 10 |
|---|---|---|---|
| Every board, checked at the end | O(nⁿ · n²) | O(n) | 10^10 boards, TLE |
| Backtracking + O(1) checks | O(n!) upper bound, far less in practice | O(n) arrays + recursion depth n (+ the n x n board and the output) | ~35,000 calls, a few ms |
Why O(n!): row 0 has n choices, row 1 at most n - 1 (one column is taken), and so on. Diagonal pruning cuts much more than that. It is still exponential: the output itself grows exponentially, and no polynomial method for listing all boards is known.
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
d2[r - c] |
ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 7 |
r - c is negative right of the main diagonal |
d2[r - c + n - 1] |
| No un-mark after the recursive call | [] and 0 |
old queens stay marked forever | set all three back to false |
if (col[c]) continue; only |
24 and 40320 (n!) |
diagonals never checked | check col, d1 and d2 |
new boolean[n] for the diagonal arrays |
ArrayIndexOutOfBoundsException |
there are 2n - 1 diagonals each way |
new boolean[2 * n - 1] |
res.add(b) of the char grid itself |
every saved board is the empty board at the end | one shared array, changed by backtracking | copy each row into a new String |
| Checking every pair at the end | TLE at n = 10 | doomed boards are built in full | check while placing |
Mini project: the exam hall planner
Write a program that reads n and prints the first safe seating as a grid, using S for a student and _ for an empty bench, plus the total number of seatings. Example for n = 6: the first board found is .Q.... / ...Q.. / .....Q / Q..... / ..Q... / ....Q. and there are 4 boards in total. Extension: some benches are broken (given as a list of squares); skip them.
Practice
- N-Queens II (LeetCode 52): return only the number of boards.
Solution
Drop the board and the list; count when r == n.
static int count(int n, int r, boolean[] col, boolean[] d1, boolean[] d2) {
if (r == n) return 1;
int total = 0;
for (int c = 0; c < n; c++) {
if (col[c] || d1[r + c] || d2[r - c + n - 1]) continue;
col[c] = d1[r + c] = d2[r - c + n - 1] = true;
total += count(n, r + 1, col, d1, d2);
col[c] = d1[r + c] = d2[r - c + n - 1] = false;
}
return total;
}
count(8, 0, new boolean[8], new boolean[15], new boolean[15]) → 92.
- Stop at the first board. Make
placereturnbooleanand stop as soon as one board is found.
Solution
Return true at r == n, and if (place(...)) return true; inside the loop, before the un-place lines (so the board keeps the answer). This is exactly the pattern of the Sudoku solver in episode 34.
- n rooks. A rook attacks only along rows and columns. How many ways to place
nrooks?
Solution
n!: it is bug 3 on purpose. Row 0 has n columns, row 1 has n - 1, and so on.
- Symmetry. Why is the number of boards for
n = 4even?
Solution
Every board has a mirror image (flip left-right). For n = 4 the two boards are mirror images of each other. A faster solver only tries row-0 columns 0 .. n/2 - 1 and doubles the count (with care for the middle column when n is odd).
Quick quiz
System.out.println(solveNQueens(5).size());
0210120
Answer
10. A 5 x 5 board has 10 solutions. 120 = 5! would be the columns-only bug.
Interview questions
- Why exactly one queen per row? Two queens in one row attack each other, so a board is an array of
ncolumn numbers. - How do you check a diagonal in O(1)? Squares on one ↙ diagonal share
r + c; on one ↘ diagonal they sharer - c. Keep a boolean per diagonal. - Why
r - c + n - 1?r - cranges from-(n - 1)ton - 1; addingn - 1maps it to0 .. 2n - 2. - What is backtracking? Build a solution step by step; when a step can't lead to a solution, undo the last choice and try the next one.
- What is pruning here? Skipping an attacked square immediately, which removes its whole subtree of boards.
- Time complexity? O(n!) upper bound; in practice much less. Space O(n) plus the output.
- How would you return only the count? N-Queens II: same search, no board, return counts.
- Can you speed it up further? Bitmasks for
col,d1,d2(one integer each), and mirror symmetry.
Glossary
| Term | Meaning |
|---|---|
| Queen | A chess piece that attacks any number of squares along its row, column and both diagonals |
| Board / grid | An n x n table of squares; here char[][] with 'Q' and '.' |
| Diagonal | A line of squares going one row down and one column left (↙) or right (↘) each step |
r + c |
The same for every square on one ↙ diagonal |
r - c |
The same for every square on one ↘ diagonal |
| Backtracking | Choose, explore (recurse), un-choose, then try the next choice |
| Pruning | Cutting off a branch of the search early because it can't lead to an answer |
| Dead end | A row where every square is attacked |
| Boolean array | An array of true/false values, used as a set of "taken" flags |
n! (n factorial) |
n × (n - 1) × ... × 1; the number of ways to give each row a different column |
ArrayIndexOutOfBoundsException |
Java's error for reading an array at an index below 0 or at/after its length |
| Time Limit Exceeded (TLE) | Too slow for the judge's limit (8 s in the SyntaxPilot compiler) |
Summary
- One queen per row, so a board is
q[row] = column. Building allnⁿboards and checking at the end works for 8 but times out for 10. - Check each square while placing: an attacked square is skipped at once, and its whole subtree goes with it.
- Three boolean arrays make the check O(1):
col[c],d1[r + c],d2[r - c + n - 1], each diagonal array of size2n - 1. - Un-mark everything you marked when you back up. O(n!) upper bound, O(n) extra space.
Next episode: Sudoku solver (hard).