算法 中等 | 33. N皇后问题
题目描述
n皇后问题是将n个皇后放置在n*n的棋盘上，皇后彼此之间不能相互攻击(任意两个皇后不能位于同一行，同一列，同一斜线)。
给定一个整数n，返回所有不同的n皇后问题的解决方案。
每个解决方案包含一个明确的n皇后放置布局，其中“Q”和“.”分别表示一个女王和一个空位置。
样例1
输入:1
输出:
[["Q"]]
样例2
输入:4
输出:
[
// Solution 1
[".Q..",
"...Q",
"Q...",
"..Q."
],
// Solution 2
["..Q.",
"Q...",
"...Q",
".Q.."
]
]
java题解
暴力搜索，尝试可以放置的地点，返回每个方案即可
class Solution {
List<List<String>> solveNQueens(int n) {
List<List<String>> results = new ArrayList<>();
if (n <= 0) {
return results;
}
search(results, new ArrayList<Integer>(), n);
return results;
}
/*
* results store all of the chessboards
* cols store the column indices for each row
*/
private void search(List<List<String>> results,
List<Integer> cols,
int n) {
if (cols.size() == n) {
results.add(drawChessboard(cols));
return;
}
for (int colIndex = 0; colIndex < n; colIndex++) {
if (!isValid(cols, colIndex)) {
continue;
}
cols.add(colIndex);
search(results, cols, n);
cols.remove(cols.size() - 1);
}
}
private List<String> drawChessboard(List<Integer> cols) {
List<String> chessboard = new ArrayList<>();
for (int i = 0; i < cols.size(); i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < cols.size(); j++) {
sb.append(j == cols.get(i) ? 'Q' : '.');
}
chessboard.add(sb.toString());
}
return chessboard;
}
private boolean isValid(List<Integer> cols, int column) {
int row = cols.size();
for (int rowIndex = 0; rowIndex < cols.size(); rowIndex++) {
if (cols.get(rowIndex) == column) {
return false;
}
if (rowIndex + cols.get(rowIndex) == row + column) {
return false;
}
if (rowIndex - cols.get(rowIndex) == row - column) {
return false;
}
}
return true;
}
}
C++题解
暴力搜索，尝试可以放置的地点，返回每个方案即可
class Solution {
public:
vector<vector<string> > solveNQueens(int n) {
// write your code here
vector<vector<string> > result;
if( n <= 0 )
{
return result;
}
vector<int> cols;
search(n, cols, result);
return result;
}
void search(int n, vector<int> &cols, vector<vector<string> > &result)
{
if(cols.size() == n)
{
result.push_back(drawResult(cols, n));
return;
}
for(int col = 0; col < n; col++)
{
if(!isValid(cols, col))
{
continue;
}
cols.push_back(col);
search(n, cols, result);
cols.pop_back();
}
}
bool isValid(vector<int> &cols, int col)
{
int row = cols.size();
for(int i = 0; i < row; ++i)
{
if(cols[i] == col)
{
return false;
}
if(i - cols[i] == row - col)
{
return false;
}
if(i + cols[i] == row + col)
{
return false;
}
}
return true;
}
vector<string> drawResult(vector<int> &cols, int n)
{
vector<string> result;
for(int i = 0; i < cols.size(); ++i)
{
string temp(n, '.');
temp[cols[i]] = 'Q';
result.push_back(temp);
}
return result;
}
};
python题解
是用排列式的深度优先搜索算法。
class Solution:
def solveNQueens(self, n):
results = []
self.search(n, [], results)
return results
def search(self, n, cols, results):
row = len(cols)
if row == n:
results.append(self.draw_chessboard(cols))
return
for col in range(n):
if not self.is_valid(cols, row, col):
continue
cols.append(col)
self.search(n, cols, results)
cols.pop()
def draw_chessboard(self, cols):
n = len(cols)
board = []
for i in range(n):
row = ['Q' if j == cols[i] else '.' for j in range(n)]
board.append(''.join(row))
return board
def is_valid(self, cols, row, col):
for r, c in enumerate(cols):
if c == col:
return False
if r - c == row - col or r + c == row + col:
return False
return True