LeetCode#37

LeetCode#37解数独

题目链接

一道暴力的深搜就能过的题，按照数独的规则，在安放一个数的时候需要分别考虑横向、纵向以及当前位置所在的九宫格。我们可以先遍历一遍题目给出的图，分别统计出空格的位置，每一行、每一列以及每个小九宫格中已经存在的数据，然后以空格数量作为循环变量，当空格没有全部用完则继续往下一层递归，直到找到所有答案为止。为了提高递归回溯的速度，我们还可以设置一个标记判断是否已经找到其中一种解，只要找到了则停止递归。
附上代码：

class Solution {
public:
    bool line[9][9];//行标记数组，第一维代表是第几行，第二维代表这个数字是否存在，下面两个数组相同
    bool col[9][9];//列标记数组
    bool flag[3][3][9];//九宫格标记数组
    vector<pair<int,int>>nums;//储存所有需要填数字的空格
    bool ans = false;//判断是否已经找到一个答案的标记
    void dfs(vector<vector<char>>& board,int pos)
    {
        if(pos >= nums.size())
        {
            ans = true;
            return ;
        }
        auto [x,y] = nums[pos];
        for(int i = 0 ; i < 9 ; i++)
        {
           if(!line[x][i] && !col[y][i] && !flag[x/3][y/3][i] && !ans)
           {
               board[x][y] = i + 1 + '0';
               line[x][i] = col[y][i] = flag[x/3][y/3][i] = true;
               dfs(board,pos+1);
               line[x][i] = col[y][i] = flag[x/3][y/3][i] = false;
           }
        }
    }
    void solveSudoku(vector<vector<char>>& board) {
        for(int i = 0 ; i < 9 ; i++)//先遍历一遍数组找到所有已知信息
        {
            for(int j = 0 ; j < 9 ; j++)
            {
                if(board[i][j] == '.')
                    nums.push_back(pair(i,j));
                else
                    {
                        int num = board[i][j]-'0'-1;//存储表是从0开始，所以需要减1
                        line[i][num] = true;
                        col[j][num] = true;
                        flag[i/3][j/3][num] = true;
                    }
            }
        }
        dfs(board,0);
    }
};