# 52. N-Queens II

## 刷题内容

• https://leetcode.com/problems/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.."]
]


Ë¼Â·1 **- Ê±¼ä¸´ÔÓ¶È: O(2^n)*- ¿Õ¼ä¸´ÔÓ¶È: O(n)***

ÕâÌâºÍÉÏÒ»µÀÌâ»ù±¾Ò»Ñù£¬Ö»ÊÇÇó´ÎÊý¡£ÉÔÎ¢¸Ä¶¯Ò»ÏÂ¾ÍºÃ£¬¾ßÌåµÄ²»¶àËµÁË

class Solution {
public:
int travel(int* d,int level,int n,int* l,int* r)
{
if(level >= n)
return 1;
int ans = 0;
for(int i = 0;i < n;++i)
if(!d[i] && !r[level + i] && !l[i - level + n])
{
d[i] = 1;
r[level + i] = 1;
l[i- level + n] = 1;
ans += travel(d,level + 1,n,l,r);
d[i] = 0;
r[level + i] = 0;
l[i- level + n] = 0;
}
return ans;
}
int totalNQueens(int n) {
int d[n];
int l[2 * n];
int r[2 * n];
memset(d,0,sizeof(d));
memset(l,0,sizeof(l));
memset(r,0,sizeof(r));
int ans = 0;
for(int i = 0;i < n;++i)
{
d[i] = 1;
r[i] = 1;
l[i + n] = 1;
ans += travel(d,1,n,l,r);
d[i] = 0;
r[i] = 0;
l[i + n] = 0;
}
return ans;
}
};