Last updated on March 7th, 2025 at 08:26 pm

Here, we see an N Queens LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Backtracking

Level of Question

Hard

N-Queens LeetCode Solution

1. Problem Statement

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 1:

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

Example 2:

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

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Backtracking”. Backtracking is a general algorithmic technique that involves searching through all possible combinations to solve a problem. It is particularly useful for constraint satisfaction problems like the N-Queens problem, where we need to place queens on a chessboard such that no two queens threaten each other.

3. Code Implementation in Different Languages

3.1 N-Queens C++

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        ans.clear();
        board.resize(n, string(n, '.'));
        place(0,0,0,0);
        return ans;
    }
    
private:
    vector<vector<string>> ans;
    vector<string> board;
    
    void place(int i, int vert, int ldiag, int rdiag) {
        int N = board.size();
        if (i == N) {
            vector<string> res;
            for (auto row : board) res.push_back(row);
            ans.push_back(res);
            return;
        }
        for (int j = 0; j < N; j++) {
            int vmask = 1 << j, lmask = 1 << (i+j), rmask = 1 << (N-i-1+j);
            if (vert & vmask || ldiag & lmask || rdiag & rmask) continue;
            board[i][j] = 'Q';
            place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask);
            board[i][j] = '.';
        }        
    }
};

3.2 N-Queens Java

class Solution {
    public List<List<String>> solveNQueens(int n) {
        boolean[] 
            //ocp0 = new boolean[n], //whether there's a queen ocupying nth row, I don't need it
            ocp90 = new boolean[n], //whether there's a queen ocupying nth column
            ocp45 = new boolean[2 * n - 1], // mark 45 degree occupation
            ocp135 = new boolean[2 * n - 1]; // mark 135 degree occupation
        List<List<String>> ans = new ArrayList<List<String>>();
        char[][] map = new char[n][n];
        for (char[] tmp : map) Arrays.fill(tmp, '.'); //init
        
        solve(0, n, map, ans, ocp45, ocp90, ocp135);
        return ans;
    }
    
    private void solve(int depth, int n, char[][] map, List<List<String>> ans, 
    boolean[] ocp45, boolean[] ocp90, boolean[] ocp135) {
        if (depth == n) {
            addSolution(ans, map);
            return;
        }
        
        for (int j = 0; j < n; j++)
            if (!ocp90[j] && !ocp45[depth + j] && !ocp135[j - depth + n - 1]) {
                ocp90[j] = true;
                ocp45[depth + j] = true;
                ocp135[j - depth + n - 1] = true;
                map[depth][j] = 'Q';
                solve(depth + 1, n, map, ans, ocp45, ocp90, ocp135);
                ocp90[j] = false;
                ocp45[depth + j] = false;
                ocp135[j - depth + n - 1] = false;
                map[depth][j] = '.';
            }
    }
    
    private void addSolution(List<List<String>> ans, char[][] map) {
        List<String> cur = new ArrayList<String>();
        for (char[] i : map) cur.add(String.valueOf(i));
        ans.add(cur);        
    }
}

3.3 N-Queens JavaScript

var solveNQueens = function(n) {
    let ans = [],
        board = Array.from({length: n}, () => new Array(n).fill('.'))
    
    const place = (i, vert, ldiag, rdiag) => {
        if (i === n) {
            let res = new Array(n)
            for (let row = 0; row < n; row++)
                res[row] = board[row].join("")
            ans.push(res)
            return
        }
        for (let j = 0; j < n; j++) {
            let vmask = 1 << j, lmask = 1 << (i+j), rmask = 1 << (n-i-1+j)
            if (vert & vmask || ldiag & lmask || rdiag & rmask) continue
            board[i][j] = 'Q'
            place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask)
            board[i][j] = '.'
        }
    }

    place(0,0,0,0)
    return ans    
};

3.4 N-Queens Python

class Solution(object):
    def solveNQueens(self, n):
        def DFS(queens, xy_dif, xy_sum):
            p = len(queens)
            if p==n:
                result.append(queens)
                return None
            for q in range(n):
                if q not in queens and p-q not in xy_dif and p+q not in xy_sum: 
                    DFS(queens+[q], xy_dif+[p-q], xy_sum+[p+q])  
        result = []
        DFS([],[],[])
        return [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n!)	O(n²)
Java	O(n!)	O(n²)
JavaScript	O(n!)	O(n²)
Python	O(n!)	O(n²)

The N-Queens problem is a classic example of backtracking.
The algorithm explores all possible solutions but uses constraints to prune invalid placements, improving efficiency.
The time complexity is factorial due to the combinatorial nature of the problem, while the space complexity is quadratic due to the board and result storage.