Here, We see N-Queens II 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 II 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 the number of distinct solutions to the n-queens puzzle.
Example 1: Input: n = 4 Output: 2 Explanation: There are two distinct solutions to the 4-queens puzzle as shown. Example 2: Input: n = 1 Output: 1
N-Queens II Leetcode Solution C++
class Solution {
public:
int totalNQueens(int n) {
ans = 0;
place(0,0,0,0,n);
return ans;
}
private:
int ans;
void place(int i, int vert, int ldiag, int rdiag, int N) {
if (i == N) ans++;
else 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;
place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask, N);
}
}
};
Code language: PHP (php)
N-Queens II Leetcode Solution Java
class Solution {
int ans;
public int totalNQueens(int n) {
ans = 0;
place(0,0,0,0,n);
return ans;
}
private void place(int i, int vert, int ldiag, int rdiag, int N) {
if (i == N) ans++;
else 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) > 0) continue;
place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask, N);
}
}
}
Code language: PHP (php)
N-Queens II Leetcode Solution JavaScript
var totalNQueens = function(n) {
let ans = 0
const place = (i, vert, ldiag, rdiag) => {
if (i === n) ans++
else 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
place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask)
}
}
place(0,0,0,0)
return ans
};
Code language: JavaScript (javascript)
N-Queens II Leetcode Solution Python
class Solution(object):
def totalNQueens(self, n):
self.res = 0
self.dfs([-1]*n, 0)
return self.res
def dfs(self, nums, index):
if index == len(nums):
self.res += 1
return #backtracking
for i in range(len(nums)):
nums[index] = i
if self.valid(nums, index):
self.dfs(nums, index+1)
def valid(self, nums, n):
for i in range(n):
if nums[i] == nums[n] or abs(nums[n]-nums[i]) == n-i:
return False
return True