力扣37题：回溯算法之解数独

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

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

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

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

大致思路：

枚举整个方格图形，对于每个空格的位置再枚举数字1-9，并判断是否符合数独的条件，如果符合则将该空格位置放入该数。当某个空格位置枚举数字1-9时都不满足数独条件，则说明该数独无解。当枚举到某个值而不满足数独条件时，则要进行回溯处理。当遍历完整个二维数组时，则填充出了满足数独条件的数独。

例如：从数字1-4中选择两个数分别填入红色格子和蓝色格子，使得出现的数字不重复。

回溯解题过程：

1.选择一个数填入红色格子

可见当选的数不满足条件时会进行回溯处理，最终红色格子填入2和4符合条件。所以要分别在此基础上选择一个数填入蓝色格子。

2.选一个数填入蓝色格子

最终只有两种填入方案符合条件。

回溯全过程图：

奉上本题代码：

int ROW,COL;//两个值可以直接改为9
bool IsValid(char**board,int row,int col,char k)//是否符合条件
{
    //行
    for(int i=0;i<COL;i++)
    {
        if(board[row][i]==k)
            return false;
    }
    //列
    for(int j=0;j<ROW;j++)
    {
        if(board[j][col]==k)
            return false;
    }
    //9宫格
    int startrow=row/3*3;
    int startcol=col/3*3;//九宫格的起始坐标
    for(int i=startrow;i<startrow+3;i++)
    {
        for(int j=startcol;j<startcol+3;j++)
        {
            if(board[i][j]==k)
                return false;
        }
    }
    return true;
}
bool bacjktracking(char**board)
{
    for(int i=0;i<ROW;i++)
    {
        for(int j=0;j<COL;j++)
        {
            if(board[i][j]=='.')//只能填入空格
            {
                for(char s='1';s<='9';s++)
                {
                    if(IsValid(board,i,j,s))
                    {
                        board[i][j]=s;
                        if(bacjktracking(board))//填入某个数符合条件
                            return true;
                        board[i][j]='.';
                    }
                }
                return false;//当某个格子填入任何数都不符合条件则，数独无解
            }
        }
    }
    return true;
}
void solveSudoku(char** board, int boardSize, int* boardColSize){
    ROW=boardSize;
    COL=*boardColSize;
    bool ans=bacjktracking(board);
}