怎样应对IT面试与笔试-（八）

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面试与笔试-（十六）