LeetCode 51 N皇后

51.N皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位

双hash+回溯递归

此处采取逐行去填充元素位置的方式：

1. bool col[9]={false}; 记录那些列被使用了，通过记录和逐行填充的方式实现了行列的不冲突
2. vector<pair<int,int>> pos; 记录每一行所使用的列号用于判断是否会出现的在同一斜线上

基本的递归流程：递归的参数为 n,cur 分表表示皇后的个数和当前处理的行数（从0开始），那么当 cur==n 时递归结束，将本次递归的结果集加入到结果集中。 cur 行放置位置的选取，从0开始逐个判断，是否和前面已选元素在同行和同列，或者在一条斜线上，不是则选取后递归，递归返回后再进行回溯。

是否在同一斜线上的判断：利用 pos 数组进行判断，主要是看二维坐标中的点，行距和列距是否相同。

bool isSlash(int i,int j){ // 第i行，第j列处的元素是否和前面的元素处于同一斜线
        if(pos.empty()) return false;
        for(auto &a:pos){
            if(abs(a.first-i)==abs(a.second-j)) return true;
        }
        return false;
    }

总体代码实现：

class Solution {
public:
    vector<vector<string>> res;
    vector<string> tmp;
    bool col[9]={false};
    vector<pair<int,int>> pos;
    bool isSlash(int i,int j){ // 第i行，第j列处的元素是否和前面的元素处于同一斜线
        if(pos.empty()) return false;
        for(auto &a:pos){
            if(abs(a.first-i)==abs(a.second-j)) return true;
        }
        return false;
    }
    void DFS(int cur,int n){ // 逐行放置
        if(cur==n){
            res.push_back(tmp);
            return;
        }
        for(int i=0;i<n;i++){ // cur行位置的选取
            if(!col[i]&&!isSlash(cur,i)){ // 和前面的行，不在同一列，并且不在同一斜线
                col[i]=true;
                pos.push_back({cur,i});
                string s(n,'.');
                s[i]='Q';
                tmp.push_back(s);
                DFS(cur+1,n);
                col[i]=false;
                tmp.pop_back();
                pos.pop_back();
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        DFS(0,n);
        return res;
    }
};