2014
11-18

# LeetCode-N-Queens[DFS]

### 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.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
[".Q..",  // Solution 1
"...Q",
"Q...",
"..Q."],

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


// LeetCode, N-Queens
// 深搜+剪枝
// 时间复杂度O(n!)，空间复杂度O(n)
class Solution {
public:
vector<vector<string> > solveNQueens(int n) {
this->columns = vector<int>(n, 0);
this->main_diag = vector<int>(2 * n, 0);
this->anti_diag = vector<int>(2 * n, 0);

vector<vector<string> > result;
vector<int> C(n, 0);  // C[i]表示第i行皇后所在的列编号
dfs(C, result, 0);
return result;
}
private:
// 这三个变量用于剪枝
vector<int> columns;  // 表示已经放置的皇后占据了哪些列
vector<int> main_diag;  // 占据了哪些主对角线
vector<int> anti_diag;  // 占据了哪些副对角线

void dfs(vector<int> &C, vector<vector<string> > &result, int row) {
const int N = C.size();
if (row == N) { // 终止条件，也是收敛条件，意味着找到了一个可行解
vector<string> solution;
for (int i = 0; i < N; ++i) {
string s(N, '.');
for (int j = 0; j < N; ++j) {
if (j == C[i]) s[j] = 'Q';
}
solution.push_back(s);
}
result.push_back(solution);
return;
}

for (int j = 0; j < N; ++j) {  // 扩展状态，一列一列的试
const bool ok = columns[j] == 0 && main_diag[row + j] == 0 &&
anti_diag[row - j + N] == 0;
if (！ok) continue;  // 剪枝：如果合法，继续递归
// 执行扩展动作
C[row] = j;
columns[j] = main_diag[row + j] = anti_diag[row - j + N] = 1;
dfs(C, result, row + 1);
// 撤销动作
// C[row] = 0;
columns[j] = main_diag[row + j] = anti_diag[row - j + N] = 0;
}
}
};


Java代码:

public class Solution {
static int path[];
public static List<String[]> solveNQueens(int n) {
path = new int[n];
List<String[]> listStr = new ArrayList<String[]>(100);
nqueens(0,n, listStr);
return listStr;
}
public static boolean check(int row){
for(int i=0; i<row; i++){
if(path[i] == path[row] || Math.abs(row-i) == Math.abs(path[row]-path[i]))
return false;
}
return true;
}
private static void nqueens(int row,int n, List<String[]> listStr) {
if(row == n){
String[] strs = new String[n];
char charArr[][] = new char[n][n];
for(int i=0; i<n; i++){
Arrays.fill(charArr[i],'.');
charArr[i][ path[i] ] = 'Q';
strs[i] = new String(charArr[i]);
}

}else{
for(int i=0; i<n; i++){
path[row] = i;
if(check(row)){
nqueens(row+1, n, listStr);
}
}

}
}
}

N-Queens II

1. 第一句可以忽略不计了吧。从第二句开始分析，说明这个花色下的所有牌都会在其它里面出现，那么还剩下♠️和♦️。第三句，可以排除2和7，因为在两种花色里有。现在是第四句，因为♠️还剩下多个，只有是♦️B才能知道答案。

2. #!/usr/bin/env python
def cou(n):
arr =
i = 1
while(i<n):
arr.append(arr[i-1]+selfcount(i))
i+=1
return arr[n-1]

def selfcount(n):
count = 0
while(n):
if n%10 == 1:
count += 1
n /= 10
return count

3. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.