题目：数独

描述：请编写一个程序，给数独中的剩余的空格填写上数字

空格用字符'.'表示

解法一：

思路分析：首先我们通过该题目了解一下什么是数独，数独是十八世纪在瑞士产生的一种小游戏，是通过不断的演算推导出来的逻辑游戏，在上述中，属于9行9列的格子，且被分为9个3*3的方块，该方块内的数字取值范围为1-9，玩家通过在剩余的空白格子中填入数字，数字需要满足的条件为数字1-9在每一行每一列只能出现一次，且数字1-9在每一个粗实线分隔的3*3宫内只能出现一次。

我们需要做的就是，找出当前可能存在的各种解法，不断地填入可能的数字，如果通过演算得出的解法错误就将该结果撤回，否则的话，就已知尝试不同的解法，通过上述描述，我们可以想到的首先是递归的方法，通过尝试不同的可能的解，向上返回所有的尝试结果，可能的结果只有两种，一种为成功，一种为失败，具体采用的递归方法为：

1、首先推测出每一个空白的格子中可能存在的数字

2、找到可供选择的最小的那个格子

3、如果有可选的数字，填入可选的数字，生成一个数独，否则的话就返回失败的信息

4、不断的通过调用递归函数来处理新的数独

5、不断的填入新的数字进行判断，当成功则返回成功的信息，当失败则重新进行递归判断。

6、每成功一次就向上一层返回成功的信息

因为空白格子有一定的数量，所以我们使用1-9来进行记录，采用unsigned int类型进行记录从右往左数的第K为代表的数字K，使用1定位相应的位置，使用或和与运算进行相关的操作，对于i行j列的小方格，使用i / 3 * 3 + j / 3即可以得出相应3 * 3方块的下标。

实例分析：在一个实例分析中我们采用表格进行判断，简化操作

5

3

7

6

1

9

5

9

8

6

8

6

3

4

8

3

1

7

2

6

6

2

8

4

1

9

5

8

7

9


在计算机进行判断的时候，会将该表格看成一个坐标系，以i行j列为例，进行判断，以左上角3*3为例

5

3

1,2,4

6

2,7


2,4,7

1,2

9

8

（其中蓝色表示可能出现的数字）
        计算机通过行与列的数字进行判断，包括这一个子宫格内的数字判断，将可能输出的值（蓝色字符）进行比较，像上表所示，选择一个可供选择最小的（如1，2）然后进行输入1，然后逐步递归根据条件确定其他几个格子内的数字。可能出现的情况为以下几种（就不一一举例了）：

5

3

4

6

2

7

1

9

8

5

3

4

6

7

2

1

9

8

通过各个子宫格的确定，最终如果判断成功，则输出最终结果。

具体C++代码为： 


class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        unsigned int pos_r[9];//每一行剩下的可选数字
        unsigned int pos_l[9];//每一列剩下的可选数字
        unsigned int pos_b[9];//每一方块剩下的可选数字
        //九个数字均可选        
for (int i = 0; i < 9; i++){
            pos_r[i] = 0b111111111;
            pos_l[i] = 0b111111111;
            pos_b[i] = 0b111111111;
        }
        for (int i = 0; i < 9; i++){
            for (int j = 0; j < 9; j++){
                if(board[i][j] != '.' ){//出现了新的数字，空白格用点号表示
                    unsigned int bit = 1 << (board[i][j] - '1');
                    pos_r[i] &= ~bit;//把相应的位置为0
                    pos_l[j] &= ~bit;
                    pos_b[i/3*3+j/3] &= ~bit;
                }
            }
        }
        slove(board, pos_r, pos_l, pos_b);//调用函数
    }
    bool slove(vector<vector<char>>& board, unsigned int *pos_r, unsigned int *pos_l, unsigned int *pos_b){
         int min_choice = 10;
         int a = 0, b = 0;
         unsigned int pos_bit = 0;
         for (int i = 0; i < 9; i++){
            for (int j = 0; j < 9; j++){
                if(board[i][j] == '.' ){
                    //该位置没有填
                    unsigned int possible = pos_r[i] & pos_l[j] & pos_b[i/3*3+j/3];//计算出同时满足三个条件的数字
                    if (possible == 0) return false;//无解
                    int choice = __builtin_popcount(possible);//计算可能的数字有多少（1的位数）
                    if (choice < min_choice){//找到可填入数字最少的
                        min_choice = choice;
                        a = i;
                        b = j;
                        pos_bit = possible;
                    }

                }
            }
        }
        if (min_choice == 10) 
            return true; //全部填完了，返回

        //pos_bit 记录可能的数字
        while(pos_bit){
            unsigned int test_bit = 1 << __builtin_ctz(pos_bit);//从最右边的位开始（选最小的数字）
            board[a][b] = __builtin_ctz(pos_bit) + '1';//填入数字
            pos_r[a] &= ~test_bit;
            pos_l[b] &= ~test_bit;
            pos_b[a/3*3+b/3] &= ~test_bit;
            if (slove(board, pos_r, pos_l, pos_b)){
                return true;//成功 返回
            }
            //失败，撤回后继续试
            board[a][b] = '.';
            pos_r[a] |= test_bit;
            pos_l[b] |= test_bit;
            pos_b[a/3*3+b/3] |= test_bit;
            //清除试过的位
            pos_bit &= ~test_bit;
        }
        return false;//找不到解
    }
};


因为要遍历每一行每一列的元素来进行判断，所以其时间复杂度为O(N^2)，N为i行或j列，用三个数组表示可选择的数字，空间复杂度为O(N * i * j)。

解法二：

思路分析：上述代码较为复杂，可以采用暴力法代码，主要遵循三个基本原则每一行只能出现1～9这九个数字，并且不能重复，每一列只能出现1～9这九个数字，并且不能重复。每一个九宫格里面只能出现1～9这九个数字，不能重复，可直接通过暴力解决。

具体Java代码为： 


public class Solution {
    public void solveSudoku(char[][] board) {
        if(board == null || board.length == 0)//特殊情况
            return;
        solve(board);
    }

    public boolean solve(char[][] board){
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(board[i][j] == '.'){
                    for(char c = '1'; c <= '9'; c++){//尝试1-9的情况
                        if(isValid(board, i, j, c)){
                            board[i][j] = c; //将c的值放进去
                            if(solve(board))
                                return true; //如果解决了返回true
                            else
                                board[i][j] = '.'; //其他的返回.
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isValid(char[][] board, int row, int col, char c){
        for(int i = 0; i < 9; i++) {
            if(board[i][col] != '.' && board[i][col] == c)//检查行
                return false;
            if(board[row][i] != '.' && board[row][i] == c)//检查列
                return false;
            if(board[3 * (row / 3) + i / 3][ 3 * (col / 3) + i % 3] != '.' && board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)//检查子宫格 
                return false;
        }
        return true;
    }
}


其时间复杂度为O(N^3)，因为包括行列的循环和数字1-9的循环，所以最大时间复杂度为O(N^3)，空间复杂度也为O(N^3)。