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](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
N-Queens LeetCode Solution
Table of Contents
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"]]
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] = '.';
}
}
};
Code language: PHP (php)
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);
}
}
Code language: PHP (php)
N-Queens Leetcode Solution JavaScript
/**
* @param {number} n
* @return {string[][]}
*/
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
};
Code language: JavaScript (javascript)
N-Queens Leetcode Solution Python
class Solution(object):
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
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]