题目

Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'
.
You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red.

分析

一开始想通过推理得到，希望通过数独的规则得到每个空白格子可能的取值，然后往只有一种可能取值的格子填入该值。但是发现这样不能得到最终结果。因为推理的过程实际上要使用三种方法。这就使得算法变得很复杂。
另一个思路是使用搜索，但是直接搜索恐怕需要花费高昂的代价。
不过看题解是通过填入一个数字，然后使用第36题中的方法来判断是否合法来确定是否继续。这样其实不需要搜索完整个空间，可以不超时完成。

实现一

class Solution {
public:
    bool solveSudoku(vector<vector<char>>& board) {
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                if(board[i][j]!='.')
                    continue;
                for(int num=0; num<9; num++){
                    board[i][j] = num + '0' + 1;
                    if(isValidSudoku(board) && solveSudoku(board))
                        return true;
                    board[i][j] = '.';
                }
                return false;
            }
        }
        return true;
    }
private:
    bool isValidSudoku(vector<vector<char>>& board) {
        for(int i=0; i<9; i++){
            int trow[9]={0}, tcol[9]={0}, tblk[9]={0};
            for(int j=0; j<9; j++){
                if(board[i][j]!='.'){
                    int nrow = board[i][j] - '0' - 1;
                    if(trow[nrow]) return false;
                    trow[nrow]++;
                }
                if(board[j][i]!='.'){
                    int ncol = board[j][i] - '0' - 1;
                    if(tcol[ncol]) return false;
                    tcol[ncol]++;
                }
                int x = i / 3 * 3 + j / 3;
                int y = i % 3 * 3 + j % 3;
                if(board[x][y]!='.'){
                    int nblk = board[x][y] - '0' - 1;
                    if(tblk[nblk]) return false;
                    tblk[nblk]++;
                }
            }
        }
        return true;
    }
};

思考一

这种方法虽然可行，而且简单，但是实在是太暴力了。所以想到把搜索和推理结合，以此来进行剪枝的方法。具体就是记录每一行、每一列以及每一个方块中未出现的数字，搜索时只搜索其允许的取值。另外还可以使用二进制中的每一位来表示每一个数字是否被使用。

实现二

class Solution {
public:
    int row[9], col[9], blo[9];
    void solveSudoku(vector<vector<char>>& board) {
        for(int i=0; i<9; i++){
            row[i] = (1<<9) - 1;
            col[i] = (1<<9) - 1;
            blo[i] = (1<<9) - 1;
        }
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                if(board[i][j]!='.'){
                    int num = board[i][j] - '1';
                    row[i] -= 1<<num;
                    col[j] -= 1<<num;
                    blo[i/3*3 + j/3] -= 1<<num;
                }
            }
        }
        dfs(0, 0, board);
    }

private:
    bool dfs(int x, int y, vector<vector<char>>& board){
        if(y>8){
            if(x<8){
                y = 0;
                x++;
            }
            else
                return true;
        }
        if(board[x][y]!='.')
            return dfs(x, y+1, board);

        int tmp = row[x] & col[y] & blo[x/3*3 + y/3];
        if(tmp==0)
            return false;
        for(int i=0; i<9; i++){
            if(!(tmp & (1<<i)))
                continue;
            board[x][y] = i + '1';
            row[x] -= 1<<i;
            col[y] -= 1<<i;
            blo[x/3*3 + y/3] -= 1<<i;
            if(dfs(x, y+1, board))
                return true;
            board[x][y] = '.';
            row[x] += 1<<i;
            col[y] += 1<<i;
            blo[x/3*3 + y/3] += 1<<i;
            tmp -= 1<<i;
        }
        return false;
    }
};