N-Queens

Share

The N-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other (no two share the same row, column, or diagonal). Given an integer n, return all distinct solutions to the N-queens puzzle. Each solution contains a distinct board configuration where 'Q' indicates a queen and '.' indicates an empty space.

Example 1
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There are two distinct solutions to the 4-queens puzzle.
Example 2
Input: n = 1
Output: [["Q"]]

Solution Approach

We place queens one row at a time. For each row we try every column position and check whether it is safe (no conflict in column, main diagonal, or anti-diagonal). We use three boolean sets to track occupied columns and diagonals for O(1) conflict checks.

  • Maintain sets for occupied columns, main diagonals (row-col), and anti-diagonals (row+col).
  • Recursively try each column in the current row; skip if any set contains the position.
  • Place the queen (update sets and board array), recurse to the next row, then backtrack.
  • When all n rows are filled, convert the board array to a list of strings and add to results.
Java
import java.util.*;

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

        Set<Integer> cols = new HashSet<>();
        Set<Integer> diag1 = new HashSet<>(); // row - col
        Set<Integer> diag2 = new HashSet<>(); // row + col
        backtrack(board, 0, cols, diag1, diag2, result);
        return result;
    }

    private void backtrack(char[][] board, int row,
                           Set<Integer> cols, Set<Integer> diag1,
                           Set<Integer> diag2,
                           List<List<String>> result) {
        int n = board.length;
        if (row == n) {
            List<String> solution = new ArrayList<>();
            for (char[] r : board) solution.add(new String(r));
            result.add(solution);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (cols.contains(col) || diag1.contains(row - col)
                    || diag2.contains(row + col)) continue;
            board[row][col] = 'Q';
            cols.add(col); diag1.add(row - col); diag2.add(row + col);
            backtrack(board, row + 1, cols, diag1, diag2, result);
            board[row][col] = '.';
            cols.remove(col); diag1.remove(row - col); diag2.remove(row + col);
        }
    }
}
Complexity Analysis:

Time complexity: O(n!) in the worst case (n choices for row 1, n-2 for row 2, etc.).
Space complexity: O(n^2) for the board plus O(n) for the recursion stack and sets.