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:
代码语言：javascript复制[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]N皇后问题
没有什么特别简单的方法，只能DFS
按行搜索，因而行不可能重复，只要判断列坐标和两者横纵坐标之差是否相等就行了。
代码语言：javascript复制class Solution {
public:
bool judge(vector<int> col,int nowRow)
{
for(int i=0;i<nowRow;i )
if(col[i] == col[nowRow] || abs(col[nowRow]-col[i])==abs(i-nowRow)) return false;
return true;
}
void dfs(vector<vector<string>> &result,int nowRow,vector<string> temp,vector<int> col)
{
int n=col.size();
if(nowRow==n)
{
result.push_back(temp);
return ;
}
temp.push_back(string(n,'.'));
for(col[nowRow]=0;col[nowRow]<n;col[nowRow] )
if(judge(col,nowRow))
{
vector<string> temp2=temp;
temp2[nowRow][col[nowRow]]='Q';
dfs(result,nowRow 1,temp2,col);
}
}
vector<vector<string>> solveNQueens(int n)
{
vector<vector<string>> result;
vector<string> temp;
vector<int> col(n);
dfs(result,0,temp,col);
return result;
}
};
