SyntaxPilot
Courses/DSA and Coding Problems/Lesson 33
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 33 of 90

N-Queens (hard)

queued

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:

  1. To fill row r, try each column c.
  2. If square (r, c) is attacked by a queen already placed, skip it now.
  3. 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).
  4. 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

  1. 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.

  1. Stop at the first board. Make place return boolean and 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.

  1. n rooks. A rook attacks only along rows and columns. How many ways to place n rooks?
Solution

n!: it is bug 3 on purpose. Row 0 has n columns, row 1 has n - 1, and so on.

  1. Symmetry. Why is the number of boards for n = 4 even?
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());
  • 0
  • 2
  • 10
  • 120
Answer

10. A 5 x 5 board has 10 solutions. 120 = 5! would be the columns-only bug.

Interview questions

  1. Why exactly one queen per row? Two queens in one row attack each other, so a board is an array of n column numbers.
  2. How do you check a diagonal in O(1)? Squares on one ↙ diagonal share r + c; on one ↘ diagonal they share r - c. Keep a boolean per diagonal.
  3. Why r - c + n - 1? r - c ranges from -(n - 1) to n - 1; adding n - 1 maps it to 0 .. 2n - 2.
  4. 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.
  5. What is pruning here? Skipping an attacked square immediately, which removes its whole subtree of boards.
  6. Time complexity? O(n!) upper bound; in practice much less. Space O(n) plus the output.
  7. How would you return only the count? N-Queens II: same search, no board, return counts.
  8. 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 all nⁿ 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 size 2n - 1.
  • Un-mark everything you marked when you back up. O(n!) upper bound, O(n) extra space.

Next episode: Sudoku solver (hard).