题目
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.."]
]
分析
n皇后问题，比较经典。没记错的话应该使用回溯法。一层层往下搜索，跳过不能放置的位置，如果个数够了就输出，如果搜完全图都不够就返回。另外对于斜线的表示，可以利用主斜线上元素的坐标之差固定，副斜线上元素的坐标之和固定这个性质来判断。
实现一
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> ans;
vector<string> board(n, string(n, '.'));
vector<bool> row(n, false), col(n, false);
vector<bool> md(2*n-1, false), cd(2*n-1, false);
solve(0, 0, n, ans, board, row, col, md, cd);
return ans;
}
private:
void solve(int x, int y, int nleft, vector<vector<string>> &ans,
vector<string> &board, vector<bool> &row,
vector<bool> &col, vector<bool> &md, vector<bool> &cd){
if(nleft==0){
ans.push_back(board);
return;
}
if(y>board[0].size()-1){
if(x<board.size()-1){
x++;
y = 0;
}
else{
return;
}
}
for(int i=x; i<board.size(); i++){
if(row[i]) continue;
for(int j=((i==x)?y:0); j<board[0].size(); j++){
if(col[j] || md[i-j+board.size()-1] || cd[i+j]) continue;
board[i][j] = 'Q';
row[i] = true;
col[j] = true;
md[i-j+board.size()-1] = true;
cd[i+j] = true;
solve(i, j+1, nleft-1, ans, board, row, col, md, cd);
board[i][j] = '.';
row[i] = false;
col[j] = false;
md[i-j+board.size()-1] = false;
cd[i+j] = false;
}
}
}
};
思考一
通过是通过了，但是相比别人3ms的解答，我这132ms的方法简直腊鸡到我不忍直视。看了别人的代码受到了启发：皇后的性质决定了棋盘的每一行有且只有一个皇后，所以直接枚举每一行就行了。这一简单的改动不但使得代码更加简单了，而且让复杂度由原来的O(n(n2))降低到了O(n^n)，直接让程序的耗时到达了3ms。
实现二
思考二
由于我的代码经过了多次修改，所以可能不太美观，见谅=_=。
