# [leetcode题解]52. N-Queens II

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 the number of distinct solutions to the n-queens puzzle.

Example:

```Input: 4 Output: 2 Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
[".Q..",  // Solution 1
"...Q",
"Q...",
"..Q."],

["..Q.",  // Solution 2
"Q...",
"...Q",
".Q.."]
]```

N皇后问题，跟51题是一样的，只不过51题要求把所有的放置方法输出来，本题只要求输出放置方案的个数，所以代码可以直接使用上题代码，只需要把返回放置方案的部分去掉即可。

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, int *sol_cnt) {
int i, j;
char **arr = NULL;

if (idx >= n) {
*sol_cnt += 1;
return;
}

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

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

int totalNQueens(int n){
int res = 0;

dfs(0, n, &res);
return res;
}

```