N-Queens

NeetCode: N-Queens · LeetCode: 51. N-Queens · Difficulty: Hard

Place n queens on an n x n chessboard so that no two queens attack each other (no two share a row, column, or diagonal). Return every distinct solution as a board of strings, where 'Q' is a queen and '.' an empty square.

Example

Text

Input:  n = 4
Output: [[".Q..", "...Q", "Q...", "..Q."],
         ["..Q.", "Q...", "...Q", ".Q.."]]

Input:  n = 1    Output: [["Q"]]

Brute force: every column permutation, then validate

Exactly one queen per row is forced, so a candidate is "which column is the queen in each row". Requiring distinct columns as well means a candidate is a permutation of 0..n. Generate all n! permutations, and for each one check every pair of rows: two queens (i, p[i]) and (j, p[j]) share a diagonal exactly when |p[i] - p[j]| == j - i. Keep the permutations with no such pair. A permutation is built completely even when its first two queens already attack each other. The code keeps the permutation in a List<Integer>, and perm.remove(perm.size() - 1) removes by index (an int argument), so it takes off the last element. toBoard fills a char[] row with '.', sets the queen's column to 'Q', and turns the array into a String.

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Main {
    static class Solution {
        public List<List<String>> solveNQueens(int n) {
            List<List<String>> result = new ArrayList<>();
            dfs(n, new boolean[n], new ArrayList<>(), result);
            return result;
        }

        private void dfs(int n, boolean[] used, List<Integer> perm, List<List<String>> result) {
            if (perm.size() == n) {
                if (valid(perm)) {
                    result.add(toBoard(perm, n));
                }
                return;
            }
            for (int c = 0; c < n; c++) {
                if (!used[c]) {
                    used[c] = true;
                    perm.add(c);
                    dfs(n, used, perm, result);
                    perm.remove(perm.size() - 1);
                    used[c] = false;
                }
            }
        }

        private boolean valid(List<Integer> perm) {
            for (int i = 0; i < perm.size(); i++) {
                for (int j = i + 1; j < perm.size(); j++) {
                    if (Math.abs(perm.get(i) - perm.get(j)) == j - i) {
                        return false;
                    }
                }
            }
            return true;
        }

        private List<String> toBoard(List<Integer> placement, int n) {
            List<String> board = new ArrayList<>();
            for (int c : placement) {
                char[] row = new char[n];
                Arrays.fill(row, '.');
                row[c] = 'Q';
                board.add(new String(row));
            }
            return board;
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        List<List<String>> r = sol.solveNQueens(4);
        r.sort(Comparator.comparing(board -> String.join("", board))); // fixed print order
        for (List<String> board : r) {
            System.out.println(board);
        }
        System.out.println(sol.solveNQueens(1));
        System.out.println(sol.solveNQueens(6).size());
        System.out.println(sol.solveNQueens(8).size());
    }
}

Output

[..Q., Q..., ...Q, .Q..]
[.Q.., ...Q, Q..., ..Q.]
[[Q]]
4
92

main sorts the boards for n = 4 before printing, because the problem allows any order of solutions. Time: O(n² · n!) (n! permutations, an O(n²) pair check each). Space: O(n) recursion plus the stored boards.

Optimal: backtrack row by row, tracking columns and diagonals

Place one queen per row and reject a square immediately if it is attacked, so a bad partial placement is abandoned as soon as it appears rather than after n rows. Three boolean[] arrays answer "is this square attacked?" in O(1):

cols[c]: a queen already sits in column c.
diag[r + c]: cells on the same / diagonal share r + c.
anti[r + n - 1 - c]: cells on the same \ diagonal share r - c; adding n - 1 keeps the index non-negative.

Set the three flags when placing a queen, recurse to the next row, and clear them to undo.

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Main {
    static class Solution {
        public List<List<String>> solveNQueens(int n) {
            List<List<String>> result = new ArrayList<>();
            dfs(0, n, new boolean[n], new boolean[2 * n], new boolean[2 * n], new ArrayList<>(), result);
            return result;
        }

        private void dfs(int r, int n, boolean[] cols, boolean[] diag, boolean[] anti,
                         List<Integer> placement, List<List<String>> result) {
            if (r == n) {
                result.add(toBoard(placement, n));
                return;
            }
            for (int c = 0; c < n; c++) {
                int d = r + c;
                int a = r + n - 1 - c;
                if (cols[c] || diag[d] || anti[a]) {
                    continue; // attacked: prune
                }
                cols[c] = true;
                diag[d] = true;
                anti[a] = true;
                placement.add(c);
                dfs(r + 1, n, cols, diag, anti, placement, result);
                placement.remove(placement.size() - 1);
                cols[c] = false;
                diag[d] = false;
                anti[a] = false;
            }
        }

        private List<String> toBoard(List<Integer> placement, int n) {
            List<String> board = new ArrayList<>();
            for (int c : placement) {
                char[] row = new char[n];
                Arrays.fill(row, '.');
                row[c] = 'Q';
                board.add(new String(row));
            }
            return board;
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        List<List<String>> r = sol.solveNQueens(4);
        r.sort(Comparator.comparing(board -> String.join("", board))); // fixed print order
        for (List<String> board : r) {
            System.out.println(board);
        }
        System.out.println(sol.solveNQueens(1));
        System.out.println(sol.solveNQueens(6).size());
        System.out.println(sol.solveNQueens(8).size());
    }
}

Output

[..Q., Q..., ...Q, .Q..]
[.Q.., ...Q, Q..., ..Q.]
[[Q]]
4
92

Time: bounded by O(n!) (row r has at most n - r free columns) and much less in practice because of diagonal pruning. Space: O(n) for the tracking arrays and recursion, plus the stored boards.

How to explain it in an interview

Baseline: try every column permutation (one queen per row) and validate the diagonals: O(n² · n!). A clash is only detected after the whole board is built.
Key insight: check attacks as each queen is placed so a bad partial board is abandoned immediately. Three boolean arrays make the check O(1): column c, diagonal r + c, anti-diagonal r - c (shifted by n - 1 to stay non-negative).
Steps: (1) dfs(row) with the base case row == n that converts the placement to strings; (2) loop over columns and skip if cols[c] || diag[r + c] || anti[r + n - 1 - c]; (3) set the three flags and push c; (4) recurse on row + 1; (5) undo all of it.
Complexity: time bounded by O(n!) and far smaller in practice; space O(n) besides the output.
Follow-ups and pitfalls: counting solutions only is N-Queens II (no board building). Common bugs are forgetting to undo a flag and using r - c as a negative index.