Backtracking（回溯法）
51. N-Queens
经典的N皇后问题，将n个皇后放到n*n的棋盘上，使得两两皇后不能攻击（同一行、同一列、同一斜线上的皇后都会自动攻击）
我们需要返回所有的可行方法，Q表示皇后位置，.表示空位。
像题目中给出的例子：
Input: 4
Output: [
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
先给出代码：
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string> > res;
vector<string> nQueens(n,string(n,'.'));
solveNQueens(res,nQueens,0,n);
return res;
}
void solveNQueens(vector<vector<string> >&res, vector<string>& nQueens,int row,int &n)
{
if(row == n)
{
res.push_back(nQueens);
return;
}
for(int col = 0; col != n; ++col)
{
//isValid是用来保证每一行、每一列和对角线都没有冲突的皇后
if(isValid(nQueens,row,col,n))
{
nQueens[row][col] = 'Q';
//递归，深度优先搜索
solveNQueens(res,nQueens,row + 1, n);
//清理现场
nQueens[row][col] = '.';
}
}
}
bool isValid(vector<string> &nQueens,int row,int col,int &n)
{
for(int i = 0; i != row; ++i)
{
if(nQueens[i][col] == 'Q')
return false;
}
for(int i = row -1,j = col -1; i >=0 && j >=0;--i,--j)
{
if(nQueens[i][j] == 'Q')
return false;
}
for(int i = row -1,j = col + 1; i >= 0 && j <n; --i,++j)
{
if(nQueens[i][j] == 'Q')
return false;
}
return true;
}
};
以2*2的简单棋盘说明：
51.png
（1）箭头上的数字表示了程序的执行流程
（2）红色箭头是进行深度优先探索过程
（3）黑色箭头是进行回溯（清理现场）过程
回溯作为一种算法思想，通常都是使用递归这种方式来实现
怎样应对IT面试与笔试-（一）
怎样应对IT面试与笔试-（二）
怎样应对IT面试与笔试-（三）
怎样应对IT面试与笔试-（四）
怎样应对IT面试与笔试-（五）
怎样应对IT面试与笔试-（五-1）
怎样应对IT面试与笔试-（六）
怎样应对IT面试与笔试-（七）
怎样应对IT面试与笔试-（八）
怎样应对IT面试与笔试-（九）
怎样应对IT面试与笔试-（十）
怎样应对IT面试与笔试-（十一）
怎样应对IT面试与笔试-（十二）
怎样应对IT面试与笔试-（十三）
怎样应对IT面试与笔试-（十四）
怎样应对IT面试与笔试-（十五）
怎样应对IT面试与笔试-（十六）
