原题链接：Leecode 37. 解数独



巧用pair<int,int>存储空格的位置：

解法一：数组存储

class Solution {
public:
    int row[10][10];//行
    int col[10][10];//列
    int box[10][10];//宫
    vector<pair<int, int>> t;
    bool valid=false;
    void dfs(vector<vector<char>>& board,int num)
    {
        if(num==t.size())
        {
            valid=true;
            return ;
        }
        int i=t[num].first;
        int j=t[num].second;
        for(int k=1;k<=9;k++)
        {
            if(!valid)
            {
                int index=(j/3)*3+i/3; 
                if(!row[i][k] && !col[j][k] && !box[index][k])
                {
                    row[i][k]=col[j][k]=box[index][k]=1;
                    board[i][j]=k+'0';
                    dfs(board,num+1);
                    row[i][k]=col[j][k]=box[index][k]=0;
                }
            }
        }
    }
    void solveSudoku(vector<vector<char>>& board) {
        int sum=0;
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                int index=(j/3)*3+i/3; //该数在哪一个宫中
                if(board[i][j]=='.')
                {
                    t.push_back({i,j});
                }
                else 
                {
                    int tmp=board[i][j]-'0';
                    row[i][tmp]=1;
                    col[j][tmp]=1;
                    box[index][tmp]=1;
                }
            }
        }
        dfs(board,0);
    }
};

解法二：位运算

class Solution {
public:
    int row[10];//行
    int col[10];//列
    int box[10];//宫
    vector<pair<int, int>> t;
    bool valid=false;
    void dfs(vector<vector<char>>& board,int num)
    {
        if(num==t.size())
        {
            valid=true;
            return ;
        }
        int i=t[num].first;
        int j=t[num].second;
        for(int k=1;k<=9;k++)
        {
            if(!valid)
            {
                int index=(j/3)*3+i/3; 
                if(!((row[i]>>k)&1) && !((col[j]>>k)&1) && !((box[index]>>k)&1))
                {
                    row[i]|=(1<<k);
                    col[j]|=(1<<k);
                    box[index]|=(1<<k);
                    board[i][j]=k+'0';
                    dfs(board,num+1);
                    row[i]&=~(1<<k);
                    col[j]&=~(1<<k);
                    box[index]&=~(1<<k);
                }
            }
        }
    }
    void solveSudoku(vector<vector<char>>& board) {
        int sum=0;
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                int index=(j/3)*3+i/3; //该数在哪一个宫中
                if(board[i][j]=='.')
                {
                    t.push_back({i,j});
                }
                else 
                {
                    int tmp=board[i][j]-'0';
                    row[i]|=(1<<tmp);
                    col[j]|=(1<<tmp);
                    box[index]|=(1<<tmp);
                }
            }
        }
        dfs(board,0);
    }
};