☕ DSA Java Articles

Topics › Recursion and Backtracking › Trying out all Combos / Hard

N Queen

Hard TUF ID 870 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Place n chess queens on an n x n board so that no two queens attack each other. A queen attacks every square in its row, its column and both of its diagonals. Return all distinct arrangements. Each arrangement is given as n strings of length n, where Q marks a queen and . an empty square.

Constraints: 1 ≤ n ≤ 9.

Example 1

n = 4
answer = [[".Q..",      [ "..Q.",
           "...Q",        "Q...",
           "Q...",        "...Q",
           "..Q."],       ".Q.." ]]
// exactly two arrangements exist, and they are mirror images of each other

Example 2

n = 1
answer = [["Q"]]    // n = 2 and n = 3 have no arrangement at all, so the answer is []

Approach 1: Brute force, row by row with a board scan

Intuition. Trying all C(n², n) ways to choose n squares is hopeless (for n = 8 that is over four billion). The first big saving comes from a structural fact: every row must hold exactly one queen, because two queens in a row attack each other and n queens must fill n rows. So we place one queen per row, top to bottom, choosing a column for each. That reduces the raw search to n^n sequences, and the moment a queen is attacked we abandon that branch instead of finishing it.

To test “is (row, col) attacked?” we scan the board. Since only rows above row have queens so far, only three directions matter: straight up, up-left and up-right.

Algorithm.

  1. Start with an all-. board and row = 0.
  2. If row == n, every queen is placed: copy the board into the answer.
  3. Otherwise, for each col: if isSafe(row, col), put a Q, recurse on row + 1, then remove the Q.
static List<List<String>> bruteForce(int n) {
    List<List<String>> result = new ArrayList<>();
    char[][] board = new char[n][n];
    for (char[] row : board) Arrays.fill(row, '.');
    placeScan(0, n, board, result);
    return result;
}

private static void placeScan(int row, int n, char[][] board, List<List<String>> result) {
    if (row == n) {
        result.add(toStrings(board));
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isSafe(board, row, col, n)) {
            board[row][col] = 'Q';
            placeScan(row + 1, n, board, result);
            board[row][col] = '.';                   // undo and try the next column
        }
    }
}

/** Only rows above `row` hold queens, so three upward directions need checking. */
private static boolean isSafe(char[][] board, int row, int col, int n) {
    for (int r = row - 1; r >= 0; r--) if (board[r][col] == 'Q') return false;
    for (int r = row - 1, c = col - 1; r >= 0 && c >= 0; r--, c--) if (board[r][c] == 'Q') return false;
    for (int r = row - 1, c = col + 1; r >= 0 && c < n; r--, c++) if (board[r][c] == 'Q') return false;
    return true;
}

Complexity. Time O(n! · n): the search tree has at most n · (n-1) · (n-2) ... live nodes because each placed queen removes at least one column from every later row, and each node pays an O(n) scan. Space O(n²) for the board plus O(n) recursion depth, not counting the output.

The undo step board[row][col] = '.' is what makes this backtracking rather than brute force: the same board object is reused for every branch, so each branch must leave it exactly as it found it.

Approach 2: Optimal, constant-time safety check

Intuition. The scan in isSafe re-derives information we already have. Every queen that is placed occupies one column, one \ diagonal and one / diagonal, and that is all it attacks in the rows below. So keep three boolean arrays:

Checking a square becomes three array lookups. We also stop storing the whole board; queenCol[r] (the column of the queen in row r) is enough to rebuild the strings at the end.

Algorithm.

  1. placeFast(row): if row == n, build the n strings from queenCol and add them.
  2. For each col: compute d = row - col + n - 1 and a = row + col. Skip if cols[col] || diag[d] || anti[a].
  3. Set the three flags, record queenCol[row] = col, recurse, then clear the three flags.
static List<List<String>> optimal(int n) {
    List<List<String>> result = new ArrayList<>();
    int[] queenCol = new int[n];                     // queenCol[r] = column of the queen placed in row r
    boolean[] cols = new boolean[n];
    boolean[] diag = new boolean[2 * n];             // indexed by row - col + n - 1, constant along "\" lines
    boolean[] anti = new boolean[2 * n];             // indexed by row + col, constant along "/" lines
    placeFast(0, n, queenCol, cols, diag, anti, result);
    return result;
}

private static void placeFast(int row, int n, int[] queenCol, boolean[] cols, boolean[] diag, boolean[] anti,
                              List<List<String>> result) {
    if (row == n) {
        List<String> rows = new ArrayList<>();
        for (int r = 0; r < n; r++) {
            char[] line = new char[n];
            Arrays.fill(line, '.');
            line[queenCol[r]] = 'Q';
            rows.add(new String(line));
        }
        result.add(rows);
        return;
    }
    for (int col = 0; col < n; col++) {
        int d = row - col + n - 1, a = row + col;
        if (cols[col] || diag[d] || anti[a]) continue;
        cols[col] = diag[d] = anti[a] = true;
        queenCol[row] = col;
        placeFast(row + 1, n, queenCol, cols, diag, anti, result);
        cols[col] = diag[d] = anti[a] = false;       // undo
    }
}

Dry run for n = 4 (the first solution found):

row col tried result
0 0 free: place, set cols[0], diag[3], anti[0]
1 0 cols[0] taken
1 1 diag[3] taken (same \ diagonal as (0,0))
1 2 free: place, set cols[2], diag[2], anti[3]
2 0, 1, 2, 3 cols[0], anti[3], cols[2], diag[2]: dead end, undo (1,2)
1 3 free: place, set cols[3], diag[1], anti[4]
2 1 free: place, set cols[1], diag[4], anti[3]
3 0, 1, 2, 3 cols[0], cols[1], diag[4], cols[3]: dead end, undo (2,1)
2 2, 3 diag[3], cols[3]: dead end, undo (1,3), then undo (0,0)
0 1 free: place, set cols[1], diag[2], anti[1]
1 3 first free column (0 hits anti[1], 1 the column, 2 diag[2]): place
2 0 free: place
3 2 free: place; row == 4, record .Q.. / ...Q / Q... / ..Q.

Complexity. Time O(n!) nodes with O(1) work per node; building each answer costs O(n²), which is unavoidable because that is the output size. Space O(n) for the three flag arrays and the recursion.

Variant: counting with bitmasks

When only the number of arrangements is wanted, the three flag arrays can be three integers whose bits are the attacked columns of the current row. Shifting diag left and anti right by one bit when moving to the next row exactly tracks how diagonals move: a \ diagonal that hits column c in this row hits column c + 1 in the next, and a / diagonal hits c - 1. The free mask is then the complement of their union, restricted to n bits, and free & -free extracts the lowest free column.

static int countBitmask(int n) {
    return countRows(0, n, 0, 0, 0);
}

private static int countRows(int row, int n, int cols, int diag, int anti) {
    if (row == n) return 1;
    int free = ~(cols | diag | anti) & ((1 << n) - 1); // columns not attacked in this row
    int total = 0;
    while (free != 0) {
        int bit = free & -free;                      // lowest free column
        free -= bit;
        total += countRows(row + 1, n, cols | bit, (diag | bit) << 1, (anti | bit) >> 1);
    }
    return total;
}

This is the fastest practical N-Queens counter for n ≤ 31 and is what competitive programmers reach for. The Java file checks it against the sizes of the two lists above for n = 1..8: 1, 0, 0, 2, 10, 4, 40, 92.

Edge cases and pitfalls