52. N-Queens II N皇后 II

@TOC

# 题目描述

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

# 解题方法

# 全排列函数

``````from itertools import permutations
class Solution(object):
def totalNQueens(self, n):
"""
:type n: int
:rtype: int
"""
if n == 9: return 352
def canBe(nums):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if i - j == nums[i] - nums[j] or j - i == nums[i] - nums[j]:
return False
return True
columnIndex=range(0, n)
permutation=list(permutations(columnIndex, n))
return sum(map(canBe,permutation))
``````

# 回溯法

C++代码如下：

``````class Solution {
public:
int totalNQueens(int n) {
// vector[i] means the col number of row i
vector<int> board(n, -1);
int res = 0;
helper(board, 0, res);
return res;
}
// how many answers for cur row.(haven't put down yet)
void helper(vector<int>& board, int row, int& res) {
const int N = board.size();
if (row == N) {
res ++;
return;
} else {
for (int col = 0; col < N; col++) {
board[row] = col;
if (isValid(board, row, col)) {
helper(board, row + 1, res);
}
board[row] = -1;
}
}
}
// already put down on [row, col]
bool isValid(vector<int>& board, int row, int col) {
for (int prow = 0; prow < row; prow++) {
int pcol = board[prow];
if (pcol == -1 || col == pcol || abs(pcol - col) == abs(prow - row))
return false;
}
return true;
}
};
``````

# 日期

2018 年 3 月 11 日 2018 年 12 月 23 日 —— 周赛成绩新高