# [leetcode题解] 51. N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

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:

```Input: 4 Output: [
[".Q..",  // Solution 1
"...Q",
"Q...",
"..Q."],

["..Q.",  // Solution 2
"Q...",
"...Q",
".Q.."]
] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.```

C语言代码要注意，返回结果是个三维数组，即指向一个二维数组的数组，这个二维数组是一个指向一维char *的数组，每个一维中保存的是一个char *，因为是char *，所以最后要加‘\0’，

C语言代码：

```#include <stdbool.h>

#define N 100
#define MAX 120000
#define ND 3
int dirs[ND][2] = { {-1, 0}, {-1, -1}, {-1, 1} };

bool used[N][N];

bool check_dir(int x, int y, int dx, int dy, int n) {
int nx, ny;
bool ret = true;

for (;;) {
nx = x + dx;
ny = y + dy;

if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
break;
}

if (used[nx][ny]) {
ret = false;
break;
}

x = nx;
y = ny;
}

return ret;
}

bool check(int x, int y, int n) {
int i;
bool ret = true;

for (i = 0; i < ND; i++) {
ret = check_dir(x, y, dirs[i][0], dirs[i][1], n);
if (!ret) {
return ret;
}
}
return ret;
}

void dfs(int idx, int n, char ***res, int *sol_cnt) {
int i, j;
char **arr = NULL;

if (idx >= n) {
arr = (char **)malloc(n * sizeof(char *));
for (i = 0; i < n; i++) {
arr[i] = (char *)malloc((n + 1) * sizeof(char));
for (j = 0; j < n; j++) {
if (used[i][j] == 1) {
arr[i][j] = 'Q';
} else {
arr[i][j] = '.';
}
}
arr[i][j] = '\0';
}
res[*sol_cnt] = arr;
(*sol_cnt) += 1;
return;
}

for (i = 0; i < n; i++) {
if (!check(idx, i, n)) {
continue;
}

used[idx][i] = true;
dfs(idx + 1, n, res, sol_cnt);
used[idx][i] = false;
}
}

char *** solveNQueens(int n, int* returnSize, int** returnColumnSizes){
char ***res = NULL;
int i, j, k;

res = (char ***)malloc(MAX * sizeof(char **));
(*returnColumnSizes) = malloc(MAX * sizeof(int));

memset(used, 0, sizeof(used));
*returnSize = 0;
dfs(0, n, res, returnSize);

*returnColumnSizes = malloc(*returnSize * sizeof(int));
for (i = 0; i < *returnSize; i++) {
(*returnColumnSizes)[i] = n;
}

return res;
}

```

C++语言代码:

```#define N 100
#define ND 3
int dirs[ND][2] = { {-1, 0}, {-1, -1}, {-1, 1} };

class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> res;

memset(used, 0, sizeof(used));
dfs(0, n, res);
return res;
}

void dfs(int idx, int n, vector<vector<string>> &res) {
int i, j;

if (idx >= n) {
vector<string> sol;
string line = "";

for (i = 0; i < n; i++) {
line = "";
for (j = 0; j < n; j++) {
if (used[i][j] == 1) {
line.push_back('Q');
} else {
line.push_back('.');
}
}
sol.push_back(line);
}
res.push_back(sol);
return;
}

for (i = 0; i < n; i++) {
if (!check(idx, i, n)) {
continue;
}

used[idx][i] = true;
dfs(idx + 1, n, res);
used[idx][i] = false;
}
}

bool check_dir(int x, int y, int dx, int dy, int n) {
int nx, ny;
bool ret = true;

for (;;) {
nx = x + dx;
ny = y + dy;

if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
break;
}

if (used[nx][ny]) {
ret = false;
break;
}

x = nx;
y = ny;
}

return ret;
}

bool check(int x, int y, int n) {
int i;
bool ret = true;

for (i = 0; i < ND; i++) {
ret = check_dir(x, y, dirs[i][0], dirs[i][1], n);
if (!ret) {
return ret;
}
}
return ret;
}
private:
bool used[N][N];
};```