37.解数独(内含回溯算法重要思路)

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

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：

输入：board =

[["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"]]
输出：

[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],

["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],

["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],

["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],

["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

思路： 回溯算法最佳实践：解数独 :: labuladong的算法小抄 (gitee.io)

关于backtrack函数设置bool返回值：

如果不设置返回值，会发现最后返回的board和输入的一样。这是因为回溯过程中没有及时退出，将原本要求的board又一步步还原成了最初的board，所以设置bool返回值，找到一个可行解就立即返回，结束回溯。

具体分析，在做选择阶段，有九种选择，从1开始试，相当于以1为根节点生成了一棵子决策树，如果能走到 i == m ，那么就要赶紧结束回溯，此时board的状态就是要求的状态。要是走不到 i == m，那么就先取消选择，意思就是1对应的这棵子决策树已经走完了，下面打算再试试此位置放2能不能走到 i == m ，如果能就赶紧返回，结束回溯，如果不能，依次类推，一直试下去试到9

class Solution {
public:
    void solveSudoku(vectorchar>>& board) {
        backtrack(board,0,0);
    }
    bool backtrack(vectorchar>>& board,int i,int j)
    {
        int m=9;
        int n=9;
        if(j==n)//到最后一列时换到下一列重新开始
        { 
            return backtrack(board,i+1,0); 
        }
 
        if(i==m)//全部穷举完了
        {
            return true;
        }
        
        if(board[i][j]!='.')//如果已经填上数字，就跳过
        {
            return backtrack(board,i,j+1);
        }
 
        for(char ch='1';ch<='9';ch++)
        {
            //遇到不合法的数字，就跳过
            if(!isVaild(board,i,j,ch))
            {
                continue;
            }
            //做选择
            board[i][j]=ch;
            //如果找到一个可行解，就要立刻返回，结束回溯
            if(backtrack(board,i,j+1))
            {
                return true;
            }
            //撤销选择
            board[i][j]='.';
        }
        //穷举完1~9，仍然没有找到可行解，此路不通 
        return false;
    }
    /*
    //二维递归，思路同上
    bool backtrack(vector>& board)
    {
        for(int i=0;i
        {
            for(int j=0;j
            {
                if(board[i][j]!='.')
                    continue;
                for(char ch='1';ch<='9';ch++)
                {
                    if(!isVaild(board,i,j,ch))
                        continue;
                    board[i][j]=ch;
                    if(backtrack(board))
                        return true;
                    board[i][j]='.';
                }
                return false;
            }
        }
        return true;
    }
    */
    bool isVaild(vectorchar>>& board,int row,int col,char ch)
    {
        for(int i=0;i<9;i++)//判断该列是否存在重复
        {
            if(board[i][col]==ch)
                return false;
        }
        for(int j=0;j<9;j++)//判断该行是否存在重复
        {
            if(board[row][j]==ch)
                return false;
        }
        int minRow=(row/3)*3;
        int minCol=(col/3)*3;
        for(int i=minRow;i3;i++)//判断该数字所在的3*3方框内是否存在重复
        {
            for(int j=minCol;j3;j++)
            {
                if(board[i][j]==ch)
                    return false;
            }
        }
        return true;
    }
};