## Algorithm

Problem Name: 51. N-Queens

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

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, char ****pp, int *psz, int *pn, int *buff, int row) {
int i, j, col, k;
if (row == n) {
// all done
if (*psz == *pn) {
*psz *= 2;
(*pp) = realloc(*pp, *psz * sizeof(char **));
//assert(*pp);
}
(*pp)[*pn] = malloc(n * sizeof(char *));
for (i = 0; i  <  n; i ++) {
(*pp)[*pn][i] = malloc((n + 1) * sizeof(char));
//assert((*pp)[*pn][i]);
for (j = 0; j  <  n; j ++) {
(*pp)[*pn][i][j] = buff[IDX(i, j, n)] == -1 ? 'Q' : '.';
}
(*pp)[*pn][i][j] = 0;
}
(*pn) ++;
return;
}
for (col = 0; col  <  n; col ++) {
if (buff[IDX(row, col, n)] == 0) {
set_flags(buff, row, col, n, -1);
bt(n, pp, psz, pn, buff, row + 1);
set_flags(buff, row, col, n, 0);
}
}
}
char*** solveNQueens(int n, int* returnSize) {
char ***p;
int *buff;
int psz;

psz = 10;
p = malloc(psz * sizeof(char **));
buff = calloc(n * n, sizeof(int));
//assert(result && buff);

*returnSize = 0;
bt(n, &p, &psz, returnSize, buff, 0);

free(buff);

if (!*returnSize) {
free(p);
p = NULL;
}

return p;
}
``````
Copy The Code &

Input

cmd
n = 4

Output

cmd
[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>

using namespace std;

class Solution {
public:
bool isValid(vector<int> &columns, int row) {
for (int i = 0; i  <  row; i++) {
if (columns[i] == columns[row]
|| abs(columns[i] - columns[row]) == (row - i)) {
return false;
}
}
return true;
}

void placeQueens(vector < vector<string> > &ret, vector<int> &columns, int row) {
int n = columns.size();
if (row == n) { /* found one solution! */
vector < string> solution;
/* build solution vector */
for (int i = 0; i  <  n; i++) {
string line(n, '.');
line[columns[i]] = 'Q';
solution.push_back(line);
}
ret.push_back(solution);
return;
}
for (int j = 0; j  <  n; j++) {
/* try to place a queen in this row */
columns[row] = j;
/* put another queen in next row if this row's position is valid */
if (isValid(columns, row)) {
placeQueens(ret, columns, row + 1);
}
}
}

vector < vector<string> > solveNQueens(int n) {
vector<vector<string> > ret;
vector<int> columns(n, 0);

placeQueens(ret, columns, 0);

return ret;
}
};

int main() {
Solution s;
vector < vector<string> > ret;
ret = s.solveNQueens(4);

for (int i = 0; i  <  ret.size(); i++) {
for (int j = 0; j  <  ret[0].size(); j++) {
cout << ret[i][j] << endl;
}
cout << "----" << endl;
}

ret = s.solveNQueens(5);

for (int i = 0; i  <  ret.size(); i++) {
for (int j = 0; j  <  ret[0].size(); j++) {
cout << ret[i][j] << endl;
}
cout << "-----" << endl;
}

return 0;
}
``````
Copy The Code &

Input

cmd
n = 1

Output

cmd
[["Q"]]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List();
char[][] board = new char[n][n];
for (char[] row : board) {
Arrays.fill(row, '.');
}
backtrack(0, new HashSet < >(), new HashSet<>(), new HashSet<>(), board, result, n);
return result;
}

private void backtrack(int row, Set < Integer> diagonals, Set antiDiagonals, Set columns, char[][] board, List buildBoard(char[][] board, int n) {
List resultBoard = new ArrayList<>();
for (int row = 0; row  <  n; row++) {
String currentRow = new String(board[row]);
}
return resultBoard;
}
}
``````
Copy The Code &

Input

cmd
n = 4

Output

cmd
[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const solveNQueens = function(n) {
const res = []
const chess = Array.from({length: n}, () => new Array(n).fill('.'))
bt(res, chess, 0)
return res
}

function bt(res, chess, row) {
if(row === chess.length) {
res.push(build(chess))
return
}
for(let i = 0, num = chess[0].length; i < num; i++) {
if(valid(chess, row, i)) {
chess[row][i] = 'Q'
bt(res, chess, row + 1)
chess[row][i] = '.'
}
}
}

function valid(chess, row, col> {
for(let i = row - 1; i >= 0; i--) {
if(chess[i][col] === 'Q') return false
}
for(let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if(chess[i][j] === 'Q') return false
}
for(let i = row - 1, j = col + 1; i >= 0 && j < chess[0].length; i--, j++) {
if(chess[i][j] === 'Q') return false
}
return true
}

function build(chess> {
return chess.map(el => el.join(''))
}
``````
Copy The Code &

Input

cmd
n = 1

Output

cmd
[["Q"]]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def solveNQueens(self, n):
res = []
def dfs(i, l, r, m, arr):
if i == n:
res.append(arr)
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, arr + [("." * j) + "Q" + ("." * (n - j - 1))])
l[j] = r[j] = m[j] = 0
dfs(0, [0] * n, [0] * n, [0] * n, [])
return res
``````
Copy The Code &

Input

cmd
n = 1

Output

cmd
[["Q"]]

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode
{
public class _051_NQueens
{
public IList < IList();
StringBuilder rowString;
for (int i = 0; i  <  n; i++)
{
rowString = new StringBuilder(CONST_RESULT, n);
rowString[queenColumns[i]] = 'Q';
}
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, results);
}
}
}
}
``````
Copy The Code &

Input

cmd
n = 4

Output

cmd
[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]