DFS 矩阵搜索算法题解：N 皇后与数独

N 皇后

题目链接

题解

1. 画出决策树
2. 全局变量：ret 用来统计结果，path 统计每次的路径，checkcol 检查列有没有 Q，checkdig1 检查主对角线有没有 Q，checkdig2 检查副对角线有没有 Q
3. 剪枝：使用哈希表的策略，每一行不需要检查，每次都递归每一行该放的不会出现攻击，主对角线斜率一样，利用 y-x = b，每一条线上截距是相同的，如果出现相同的就表明放过了 Q，y-x 可能为负数所以加上了 n，副对角线 y + x = b，和主对角线类似
4. 回溯：将列，主对角线和副对角线变为 false，path[row][col] 恢复为点
5. 递归出口：行越界的时候填完矩阵

代码

class Solution {
public:
    // 检查列，主对角线和副对角线
    // 行每次都只放一个不用检查，不会出现攻击
    bool checkcol[10], checkdig1[20], checkdig2[20];
    vector<vector<string>> ret;
    vector<string> path;
    int n;

    vector<vector<string>> solveNQueens(int _n) {
        n = _n;
        path.resize(n);
        for (int i = 0; i < n; i++) {
            path[i].append(n, '.');
        }
        dfs(0);
        return ret;
    }

    void dfs(int row) {
        if (n == row) {
            ret.push_back(path);
            return;
        }
        for (int col = 0; col < n; col++) // 放置每一行
        {
            if (!checkcol[col] && !checkdig1[row + col] && !checkdig2[col - row + n]) {
                path[row][col] = 'Q';
                checkcol[col] = checkdig1[row + col] = checkdig2[col - row + n] = ;
                (row + );
                
                checkcol[col] = checkdig1[row + col] = checkdig2[col - row + n] = ;
                path[row][col] = ;
            }
        }
    }
};