原题地址（困难）

思路

好久没做困难难度的题目了。

但是这道题，倒不是说多难想，而是说过程复杂了一点，代码多了一点，思路还是很简单的。
就是回溯。

  • 我们遍历9*9网格中的每一个元素，如果已经有数了，便略过；
  • 如果没数，则这个格子可以有 0~9 十种选择。
  • 对于每一种选择，我们判断是否满足行、列、3*3方格内都不重复这三个条件。
  • 如果不满足，则接着尝试下一个数字。
  • 如果满足，则继续处理下一个格子。

回溯体现在什么地方呢？

就是某个格子（记为格子 x ）填了一个数（记为 num ），满足行、列、3*3方格这三个条件了，然后继续填后面的格子。然而后面的格子怎么填，都不能解出数独。说明格子 x 不能填入数 num 。所以这时候就需要回溯到格子 x ，继续尝试其他的数。
**
核心还是在回溯，只不过判断条件啥的稍微麻烦了一些。套上回溯的模板，捋顺思路慢慢写，还是很好写的。

回溯模板

  1. void dfs(){
  2.     //终止条件
  3.     ....
  4.     //  递归
  5.     for(int i=1; i<=9; i++){
  6.         如果填入数字i满足不重复条件{
  7.             填入数字i
  8.             dfs()  // 继续递归
  9.             去除数字i
  10.         }
  11.     }
  12. }

详见代码，带有详细注释

cpp代码

class Solution {
public:
    /* row[i][j] = 1  第i行已经存在数字j   
        column[i][j] = 1  第i列已经存在数字j
        square[i][j][k] = 1  共有9个小方格 ， 第[i][j]个小方格已经存在数字k
    */
    int row[9][10], column[9][10], square[3][3][10];  
    vector<vector<char>> board;

    // dfs()函数含义：从board[i,j]这个格子开始解，如果可以解出数独，就返回true，否则返回false
    bool dfs(int i, int j, int right, int bottom){
        // 因为递归board是按行递归，所以最后的边界就是 行越界
        if(i > bottom )    return true;
        //  如果该格子还没有元素
        if(board[i][j] == '.'){
            for(int k =1; k<=9; k++){
                // if条件里是三个判断不重复的条件，如果满足，就把这个数字放进格子
                if(!row[i][k] && !column[j][k] && !square[i/3][j/3][k]){
                    board[i][j] = '0' + k;   //把数字放进格子
                    row[i][k] = column[j][k] = square[i/3][j/3][k] = 1;  // 相应的标记数组更新
                    // 继续进行下一个格子
                    if(j < right && dfs(i, j+1, right, bottom))
                            return true;
                    else if(j == right && dfs(i+1, 0, right, bottom))
                        return true;
                    // 恢复原状，目的是为了进行下一个数字的尝试
                    board[i][j] = '.';
                    row[i][k] = column[j][k] = square[i/3][j/3][k] = 0;
                }  
            }
            return false;
        }
        else{  // 该格子已经有元素了，略过，直接处理下一个格子
            if(j < right && dfs(i, j+1, right, bottom))
                    return true;
            else if(j == right && dfs(i+1, 0, right, bottom))
                return true;
            else    return false;
        }
    }

    void solveSudoku(vector<vector<char>>& board) {
        memset(row, 0, sizeof(row));
        memset(column, 0, sizeof(column));
        memset(square, 0, sizeof(square));
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                char c = board[i][j];
                if(c != '.')    
                    row[i][c-'0'] = column[j][c-'0'] = square[i/3][j/3][c-'0'] = 1;
            }
        }   
        this->board = board;
        bool b = dfs(0, 0, 8, 8);
        board = this->board;
        return;
    }
};