## 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;
}
``````
Copy The Code &

Input

cmd
n = 4

Output

cmd
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;
}
}
``````
Copy The Code &

Input

cmd
n = 1

Output

cmd
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;
};
``````
Copy The Code &

Input

cmd
n = 4

Output

cmd
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]
``````
Copy The Code &

Input

cmd
n = 1

Output

cmd
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);
}
}
}
}
``````
Copy The Code &

Input

cmd
n = 4

Output

cmd
2
Advertisements