编写一个程序，通过填充空格来解决数独问题。

    数独的解法需 遵循如下规则：

    1. 数字 1-9 在每一行只能出现一次。
    2. 数字 1-9 在每一列只能出现一次。
    3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

    数独部分空格内已填入了数字，空白格用 '.' 表示。

    示例：

    H37-解数独 - 图1

    1. 输入：board = 
    2. [["5","3",".",".","7",".",".",".","."],
    3. ["6",".",".","1","9","5",".",".","."],
    4. [".","9","8",".",".",".",".","6","."],
    5. ["8",".",".",".","6",".",".",".","3"],
    6. ["4",".",".","8",".","3",".",".","1"],
    7. ["7",".",".",".","2",".",".",".","6"],
    8. [".","6",".",".",".",".","2","8","."],
    9. [".",".",".","4","1","9",".",".","5"],
    10. [".",".",".",".","8",".",".","7","9"]]
    11. 输出：
    12. [["5","3","4","6","7","8","9","1","2"],
    13. ["6","7","2","1","9","5","3","4","8"],
    14. ["1","9","8","3","4","2","5","6","7"],
    15. ["8","5","9","7","6","1","4","2","3"],
    16. ["4","2","6","8","5","3","7","9","1"],
    17. ["7","1","3","9","2","4","8","5","6"],
    18. ["9","6","1","5","3","7","2","8","4"],
    19. ["2","8","7","4","1","9","6","3","5"],
    20. ["3","4","5","2","8","6","1","7","9"]]
    21. 解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

    提示：

    • board.length == 9
    • board[i].length == 9
    • board[i][j] 是一位数字或者 '.'
    • 题目数据 保证 输入数独仅有一个解

    题解:

    class Solution {
public:

    bool legal(int row,int list,char k,vector<vector<char>>& board){
        //行有没有重复
        for(int i=0;i<9;i++){
            if(board[row][i]==k) return false;
        }
        //列有没有重复
        for (int i=0; i<9; i++){
            if(board[i][list] == k) return false;
        }
        //所处九宫格有没有重复
        int newrow=(row/3)*3;  
        //   row/3是第几个行格子(0开始), 再*3是得到这个格子的起始行
        int newlist=(list/3)*3;
        for (int i = newrow; i < newrow+3; i++){
            for (int j = newlist; j < newlist+3; j++){
                if (board[i][j] == k)return false; 
            }
        }
        return true;
    }

    bool bt(vector<vector<char>>& board){  
        //只有一种解或者说要求是最优解的情况下用bool
        //遍历行
        for (int i = 0; i < 9; i++){
            for (int j = 0; j < 9; j++){//遍历列
                if(board[i][j]!='.') continue; //跳过已经有数字的格子
                for (char k = '1'; k <='9'; k++){
                    if(legal(i,j,k,board)){
                        board[i][j]=k;
                        if(bt(board)) return true;
                        board[i][j] = '.';
                    }
                }
                //程序能执行到这说明9个数都试过了没一个通过的,说明无解
                return false;
            }
        }
        //程序可以执行到这里,说明整个循环已经结束了
        return true;
    }

    void solveSudoku(vector<vector<char>>& board) {
        bt(board);
    }
};