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.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Example

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Explanation

1. What is the problem actually asking?

You're given a chessboard of size n × n. You need to place n queens on it so that no two queens can attack each other. Return every valid arrangement.

Quick chess refresher — a queen is the most powerful piece on the board. From wherever she stands, she can attack:

• Any square in the same row (left/right)
• Any square in the same column (up/down)
• Any square along both diagonals (the \ and / directions)

So "no two queens attack each other" means: no two queens share a row, a column, or a diagonal. That's the entire rulebook.

For n = 4, valid solutions looks like this:

Notice no two Qs line up horizontally, vertically, or diagonally.

2. The first big insight: one queen per row

Here's the observation that makes everything click.

We need to place n queens. Two queens can never be in the same row. And the board has exactly n rows. So if we want to fit n queens with no row repeated, each row must contain exactly one queen. Not zero, not two — exactly one.

This is huge, because it changes the problem from "try placing queens on any of the n² squares" into a much simpler shape:

Go row by row. For each row, just decide which column the queen sits in.

Row 0 gets one queen, row 1 gets one queen, and so on until row n-1. We never have to worry about two queens sharing a row again — our strategy guarantees it.

So now the only real question per row is: which column is safe?

3. What makes a column "safe"?

When we're about to place a queen in the current row, we have to make sure it doesn't clash with any queen we've already placed in the rows above. There are three ways it could clash:

1. Same column — another queen is already sitting in that column.
2. Same \ diagonal — a queen is on the diagonal going from top-left to bottom-right.
3. Same / anti-diagonal — a queen is on the diagonal going from top-right to bottom-left.

(We don't need to check rows, remember — our one-queen-per-row rule already handles that.)

So before placing a queen, we ask three questions: Is this column taken? Is this diagonal taken? Is this anti-diagonal taken? If all three answers are "no", the square is safe.

The clever trick is figuring out a cheap way to recognize diagonals. That's where the math comes in.

4. The diagonal math (the part everyone gets stuck on)

The \ diagonals → row - col is constant

Every \ diagonal has its own unique signature number, and that number is row - col.

The / anti-diagonals → row + col is constant

Every / anti-diagonal has its own unique signature number, and that number is row + col.

Did you see how each \ diagonal and / anti-diagonal are bands of identical numbers? That's the whole idea:

• two queens are on the same \ diagonal if and only if they have the same row - col value.
• two queens are on the same / anti-diagonal if and only if they have the same row + col value.

So how do we know which column, diagonal, and anti-diagonal Queen is placed in?

We will use sets. We keep cols, diagonals, and anti_diagonals as sets. Every time we place a Queen, we will save its column, diagonal, and anti-diagonal to respective sets. And then whenever we place next Queen, we will check if the same column or same diagonal, or same anti-diagonal has a Queen already.

if col in cols or (row - col) in diagonals or (row + col) in anti_diagonals:
    # this square is under attack — skip it

So essentially the algorithm gets break down into the following steps.

• Try placing a queen in a safe column of the current row.
• Mark that column, diagonal, and anti-diagonal as occupied (add to the sets) and drop a "Q" on the board.
• Recurse into the next row to keep building the solution.
• When we come back, undo everything we did in step 2 (remove from the sets, reset the square to ".") and try the next column instead.

Here is full picture how is this gonna work.

Java Code

class Solution {
    
    public List<List<String>> ans = new ArrayList<>();
    
    public List<String> arrangeBoard(char board[][]) {
        List<String> newBoard = new ArrayList<>();
        for(int i = 0; i < board.length; i++) {
            StringBuilder string = new StringBuilder();
            for(int j = 0; j < board.length; j++) {
                string.append(board[i][j]);
            }
            newBoard.add(string.toString());
        }
        return newBoard;
    }
    
    public void solve(int row, Set<Integer> cols, Set<Integer> diagonals, Set<Integer> anti_diagonals, char board[][]) {
        if(row == board.length) {
            ans.add(arrangeBoard(board));
            return;
        }    
        
        for(int col = 0; col < board.length; col++) {
            int curr_diag = row - col;
            int curr_anti_diag = row + col;
            
            if(cols.contains(col) || diagonals.contains(curr_diag) || anti_diagonals.contains(curr_anti_diag))
                continue;
            
            cols.add(col);
            diagonals.add(curr_diag);
            anti_diagonals.add(curr_anti_diag);
            board[row][col] = 'Q';
            
            solve(row + 1, cols, diagonals, anti_diagonals, board);
            
            cols.remove(col);
            diagonals.remove(curr_diag);
            anti_diagonals.remove(curr_anti_diag);
            board[row][col] = '.';
        }
    }
    
    public List<List<String>> solveNQueens(int n) {
        char initialBoard[][] = new char[n][n];
        for(int i = 0; i < n; i++) {
            Arrays.fill(initialBoard[i], '.');
        }
        solve(0, new HashSet<>(), new HashSet<>(), new HashSet<>(), initialBoard);
        return ans;
        
        
    }
}

C++ Code

class Solution {
public:
    vector<vector<string>> ans;

    vector<string> arrangeBoard(vector<vector<char>>& board) {
        vector<string> newBoard;

        for (int i = 0; i < board.size(); i++) {
            string row = "";
            for (int j = 0; j < board.size(); j++) {
                row += board[i][j];
            }
            newBoard.push_back(row);
        }

        return newBoard;
    }

    void solve(int row,
               unordered_set<int>& cols,
               unordered_set<int>& diagonals,
               unordered_set<int>& antiDiagonals,
               vector<vector<char>>& board) {

        if (row == board.size()) {
            ans.push_back(arrangeBoard(board));
            return;
        }

        for (int col = 0; col < board.size(); col++) {
            int currDiag = row - col;
            int currAntiDiag = row + col;

            if (cols.count(col) ||
                diagonals.count(currDiag) ||
                antiDiagonals.count(currAntiDiag)) {
                continue;
            }

            cols.insert(col);
            diagonals.insert(currDiag);
            antiDiagonals.insert(currAntiDiag);
            board[row][col] = 'Q';

            solve(row + 1, cols, diagonals, antiDiagonals, board);

            cols.erase(col);
            diagonals.erase(currDiag);
            antiDiagonals.erase(currAntiDiag);
            board[row][col] = '.';
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        vector<vector<char>> board(n, vector<char>(n, '.'));

        unordered_set<int> cols;
        unordered_set<int> diagonals;
        unordered_set<int> antiDiagonals;

        solve(0, cols, diagonals, antiDiagonals, board);

        return ans;
    }
};

Python Code

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        
        def arrange_board(board):
            new_board = []
            for row in board:
                new_board.append("".join(row))
            return new_board          
        
        def solve(row, cols, diagonals, anti_diagonals, board):
            if row == n:
                ans.append(arrange_board(board))
                return 
            for col in range(n):
                curr_diag = row - col
                curr_anti_diag = row + col
                
                if col in cols or curr_diag in diagonals or curr_anti_diag in anti_diagonals:
                    continue
                
                cols.add(col)
                diagonals.add(curr_diag)
                anti_diagonals.add(curr_anti_diag)
                board[row][col] = "Q"
                
                solve(row + 1, cols, diagonals, anti_diagonals, board)
                
                board[row][col] = "."
                cols.remove(col)
                diagonals.remove(curr_diag)
                anti_diagonals.remove(curr_anti_diag)
        
        ans = []
        initial_board = [["."] * n for i in range(n)]
        solve(0, set(), set(), set(), initial_board)
        return ans
        

Javascript Code

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
    const ans = [];

    function arrangeBoard(board) {
        const newBoard = [];

        for (let row of board) {
            newBoard.push(row.join(""));
        }

        return newBoard;
    }

    function solve(row, cols, diagonals, antiDiagonals, board) {
        if (row === n) {
            ans.push(arrangeBoard(board));
            return;
        }

        for (let col = 0; col < n; col++) {
            const currDiag = row - col;
            const currAntiDiag = row + col;

            if (
                cols.has(col) ||
                diagonals.has(currDiag) ||
                antiDiagonals.has(currAntiDiag)
            ) {
                continue;
            }

            cols.add(col);
            diagonals.add(currDiag);
            antiDiagonals.add(currAntiDiag);
            board[row][col] = 'Q';

            solve(row + 1, cols, diagonals, antiDiagonals, board);

            cols.delete(col);
            diagonals.delete(currDiag);
            antiDiagonals.delete(currAntiDiag);
            board[row][col] = '.';
        }
    }

    const board = Array.from(
        { length: n },
        () => Array(n).fill('.')
    );

    solve(
        0,
        new Set(),
        new Set(),
        new Set(),
        board
    );

    return ans;
};      

Time and Space Complexity

Time: In the worst case the search explores on the order of N! arrangements (the first row has N choices, the next row has fewer, and so on), and formatting each found board costs O(N²). So a common way to express it is O(N! · N). In practice the diagonal/anti-diagonal pruning cuts off huge swaths of the tree, so it runs far faster than that ceiling suggests.

Space: O(N) for the three sets and the recursion depth (we go at most N rows deep), plus the board itself which is O(N²). So, overall it's O(N*N).