Algorithm
Problem Name: 52. N-Queens II
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
Constraints:
1 <= n <= 9
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#define IDX(I, J, SZ) ((I) * (SZ) + J)
void set_flags(int *buff, int i, int j, int n, int flag) {
int k, x, y;
buff[IDX(i, j, n)] = flag;
for (k = 0; k < n; k ++) { // row
if (k != j && buff[IDX(i, k, n)] != -1) {
buff[IDX(i, k, n)] += flag ? 1 : -1;
}
}
for (k = 0; k < n; k ++) { // col
if (k != i && buff[IDX(k, j, n)] != -1) {
buff[IDX(k, j, n)] += flag ? 1 : -1;
}
x = k;
y = j - i + k;
if (y >= 0 && y < n) {
if (x != i && y != j && buff[IDX(x, y, n)] != -1) {
buff[IDX(x, y, n)] += flag ? 1 : -1;
}
}
y = j + i - k;
if (y >= 0 && y < n) {
if (x != i && y != j && buff[IDX(x, y, n)] != -1) {
buff[IDX(x, y, n)] += flag ? 1 : -1;
}
}
}
}
void bt(int n, int *k, int *buff, int row) {
int col;
if (row == n) {
// all done
(*k) ++;
return;
}
for (col = 0; col < n; col ++) {
if (buff[IDX(row, col, n)] == 0) {
set_flags(buff, row, col, n, -1);
bt(n, k, buff, row + 1);
set_flags(buff, row, col, n, 0);
}
}
}
int totalNQueens(int n) {
int *buff, k = 0;
buff = calloc(n * n, sizeof(int));
//assert(result && buff);
bt(n, &k, buff, 0);
free(buff);
return k;
}
Input
n = 4
Output
2
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int totalNQueens(int n) {
return backtrack(0, new HashSet<>(), new HashSet<>(), new HashSet<>(), n);
}
private int backtrack(int row, Set < Integer> diagonals, Set antiDiagonals, Set columns, int n) {
if (row == n) {
return 1;
}
int possibleSolutions = 0;
for (int col = 0; col < n; col++) {
int currDiagonal = row - col;
int currAntiDiagonal = row + col;
if (columns.contains(col) || diagonals.contains(currDiagonal) || antiDiagonals.contains(currAntiDiagonal)) {
continue;
}
columns.add(col);
diagonals.add(currDiagonal);
antiDiagonals.add(currAntiDiagonal);
possibleSolutions += backtrack(row + 1, diagonals, antiDiagonals, columns, n);
columns.remove(col);
diagonals.remove(currDiagonal);
antiDiagonals.remove(currAntiDiagonal);
}
return possibleSolutions;
}
}
Input
n = 1
Output
1
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const totalNQueens = function(n) {
let count = 0;
const done = Math.pow(2, n) - 1;
const innerRecurse = function(ld, col, rd) {
if (col === done) {
count++;
return;
}
let poss = ~(ld | rd | col);
while (poss & done) {
let bit = poss & -poss;
poss -= bit;
innerRecurse((ld | bit) >> 1, col | bit, (rd | bit) << 1);
}
};
innerRecurse(0, 0, 0);
return count;
};
Input
n = 4
Output
2
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def totalNQueens(self, n):
res = [0]
def dfs(i, l, r, m):
if i == n:
res[0] += 1
else:
l = l[1:] + [0]
r = [0] + r[:-1]
for j in range(n):
if m[j] == l[j] == r[j] == 0:
l[j] = r[j] = m[j] = 1
dfs(i + 1, l, r, m)
l[j] = r[j] = m[j] = 0
dfs(0, [0] * n, [0] * n, [0] * n)
return res[0]
Input
n = 1
Output
1
#5 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _052_NQueens2
{
public int TotalNQueens(int n)
{
int result = 0;
var queenColumns = new int[n];
RecursiveSolver(n, 0, queenColumns, ref result);
return result;
}
void RecursiveSolver(int n, int currentRow, int[] queenColumns, ref int result)
{
if (currentRow == n)
{
result++;
return;
}
bool isValid = true;
for (int col = 0; col < n; col++)
{
isValid = true;
for (int i = 0; i < currentRow; i++)
{
if (queenColumns[i] == col || Math.Abs(col - queenColumns[i]) == Math.Abs(currentRow - i))
{
isValid = false;
break;
}
}
if (!isValid) continue;
queenColumns[currentRow] = col;
RecursiveSolver(n, currentRow + 1, queenColumns, ref result);
}
}
}
}
Input
n = 4
Output
2