N-Queens

Hard Problem 94 of 151 Java and Python

Problem

Place n queens on an n × n chessboard so that no two queens attack each other (no two share a row, column or diagonal).

Return all distinct solutions. Each solution is a list of strings, one per row, where Q is a queen and . is empty.

Example 1

Input: n = 4
Output: [[".Q..", "...Q", "Q...", "..Q."], ["..Q.", "Q...", "...Q", ".Q.."]]
Why: The two solutions for a 4 × 4 board.

Example 2

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

Constraints

1 ≤ n ≤ 9

Explanation

Every row has exactly one queen, so place them row by row and only choose the column. A column is safe if no earlier queen uses that column or either of its diagonals.

Cells on the same "\" diagonal share row - col; cells on the same "/" diagonal share row + col. Three sets make each safety check O(1).

Approach 1 · Better

Row by row, scan the board for attacks

Time O(n! · n)
Space O(n²) for the board

Place a queen in each row, checking safety by scanning the rows above for a queen in the same column or diagonal.

place(row): if row == n, record the board.
For each column, if safe(row, col) (scan earlier rows), place, recurse, remove.

Java

import java.util.*;

class Solution {
    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (char[] row : board) {
            Arrays.fill(row, '.');
        }
        List<List<String>> result = new ArrayList<>();
        place(board, 0, result);
        return result;
    }

    private void place(char[][] board, int row, List<List<String>> result) {
        int n = board.length;
        if (row == n) {
            List<String> rows = new ArrayList<>();
            for (char[] r : board) {
                rows.add(new String(r));
            }
            result.add(rows);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (safe(board, row, col)) {
                board[row][col] = 'Q';
                place(board, row + 1, result);
                board[row][col] = '.';
            }
        }
    }

    private boolean safe(char[][] board, int row, int col) {
        for (int r = row - 1, d = 1; r >= 0; r--, d++) {
            if (board[r][col] == 'Q'
                || (col - d >= 0 && board[r][col - d] == 'Q')
                || (col + d < board.length && board[r][col + d] == 'Q')) {
                return false;
            }
        }
        return true;
    }
}

Python

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        board = [["."] * n for _ in range(n)]
        result = []

        def safe(row, col):
            for d in range(1, row + 1):
                r = row - d
                if board[r][col] == "Q":
                    return False
                if col - d >= 0 and board[r][col - d] == "Q":
                    return False
                if col + d < n and board[r][col + d] == "Q":
                    return False
            return True

        def place(row):
            if row == n:
                result.append(["".join(r) for r in board])
                return
            for col in range(n):
                if safe(row, col):
                    board[row][col] = "Q"
                    place(row + 1)
                    board[row][col] = "."

        place(0)
        return result

Approach 2 · Optimal

Sets for columns and diagonals

Time O(n!)
Space O(n) besides the board

Track occupied columns, row - col diagonals and row + col anti-diagonals in sets so each check is O(1).

place(row): if row == n, record the board.
For each col not in cols, diag (row – col) or anti (row + col): add to all three, place, recurse, then remove.

Java

import java.util.*;

class Solution {
    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (char[] row : board) {
            Arrays.fill(row, '.');
        }
        List<List<String>> result = new ArrayList<>();
        place(board, 0, new boolean[n], new boolean[2 * n], new boolean[2 * n], result);
        return result;
    }

    private void place(char[][] board, int row, boolean[] cols, boolean[] diag, boolean[] anti, List<List<String>> result) {
        int n = board.length;
        if (row == n) {
            List<String> rows = new ArrayList<>();
            for (char[] r : board) {
                rows.add(new String(r));
            }
            result.add(rows);
            return;
        }
        for (int col = 0; col < n; col++) {
            int d = row - col + n;
            int a = row + col;
            if (cols[col] || diag[d] || anti[a]) {
                continue;
            }
            cols[col] = diag[d] = anti[a] = true;
            board[row][col] = 'Q';
            place(board, row + 1, cols, diag, anti, result);
            board[row][col] = '.';
            cols[col] = diag[d] = anti[a] = false;
        }
    }
}

Python

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        board = [["."] * n for _ in range(n)]
        cols, diag, anti = set(), set(), set()
        result = []

        def place(row):
            if row == n:
                result.append(["".join(r) for r in board])
                return
            for col in range(n):
                if col in cols or row - col in diag or row + col in anti:
                    continue
                cols.add(col)
                diag.add(row - col)
                anti.add(row + col)
                board[row][col] = "Q"
                place(row + 1)
                board[row][col] = "."
                cols.remove(col)
                diag.remove(row - col)
                anti.remove(row + col)

        place(0)
        return result

Complexity compared

Approach	Time	Space
Better Row by row, scan the board for attacks	O(n! · n)	O(n²) for the board
Optimal Sets for columns and diagonals	O(n!)	O(n) besides the board

Key takeaways

row - col and row + col identify diagonals; offset row - col by n when using an array instead of a set.
N-Queens II (count the solutions) uses the same code with a counter.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem