Last updated on October 10th, 2024 at 12:30 am

Here, We see N-Queens LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

N-Queens LeetCode Solution

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"]]

1. N-Queens Leetcode Solution 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] = '.';
        }        
    }
};

2. N-Queens Leetcode Solution 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. N-Queens Leetcode Solution 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    
};

4. N-Queens Leetcode Solution 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]