LeetCode——解数独

NO.37 解数独困难

思路一：回溯法 就是模拟人解数独时的简单想法：

人在解数独的时候要注意每一行、每一列、每一个子数独中哪些数字已经被使用过了；
一行一行的进行填充，填充完一行就聚焦到下一行继续填充；
如果一个单元格中不为空，则去下一个单元格；
如果一个单元格为空，我们就看一下这个单元格所属的行、列、子数独中有哪些数字没有使用过，就将未使用过的数字填入单元格，并且记录这个被填入的数字在此单元格所属的行、列、子数独中已经被使用过了；
如果出现因为之前填充空格时选择不佳，导致无法继续填写空格的情况，就逐步擦除之前填入的数字，并将被擦除的数字在所属的行、列、子数独中设置为未使用的状态后，重新选择下一个未使用过的数字进行填充，尝试继续完成填充；
如果已经填充完所有行，即成功解数独。

通过描述”我”解这类数独时的朴素想法，我们大概知道编码的方法了：

大方向上，我们就是对需要填写的空白格进行尝试，不断地将每个空白格填写上当前状态可用的数字。当填写逐步推进的过程中，如果出现无法满足要求的组合时，就返回并擦除填写的数字，直至得到一个完全符合要求的组合。这个过程就是典型的dfs剪枝回溯的思路。
我们需要实时的记录更新每一行、每一列、每一个子数独中1~9数字的使用情况。这里可以用三大小为9*9的boolean类型数组分别记录，初始化为false表示都未使用，遍历初始数独将已使用过的数字记录为true表示已使用。
回溯方法中需要按行逐步推进，所有行都填写完毕即完成解数独。编写时需要时刻记录当前填写的行和被填写的列。

//三个数组分别记录9行、9列、9个子数独中9个数字的使用状态，finished记录是否完成解数独
boolean[][] rows=new boolean[9][9],cols=new boolean[9][9],blocks=new boolean[9][9];
boolean finished=false;
//解数独方法
public void solveSudoku(char[][] board) {
    //初始化状态数组，遍历初始数独，将使用过的数字的状态置为true
    for (int row = 0; row < 9; row++) {
        for (int col = 0; col < 9; col++) {
            if (board[row][col] != '.'){
                rows[row][board[row][col]-'1']=
                    cols[col][board[row][col]-'1']=
                    blocks[row/3*3+col/3][board[row][col]-'1']=true;
            }
        }
    }
    dfs(board,0,0);
}
//深度遍历，row记录当前要填写的行，col记录当前要填写的列
private void dfs(char[][] board, int row, int col) {
    //0-8行都已经填写，解数独完毕
    if (row==9){
        finished=true;
        return;
    }
    //不是空白格，不需要填写，继续向后移动
    if (board[row][col] != '.'){
        //如果本行已经是最后一列，则继续填写下一行的第一列；否则继续当前行的下一列。
        if (col==8) dfs(board,row+1,0);
        else dfs(board,row,col+1);
    }else {
        //按顺序将当前行、列、子数独未使用的数字尝试填入空白格
        int block = row / 3 * 3 + col / 3;
        for (int i=0;i<9;i++){
            //如果i+1未使用，可以填入当前空白格
            if (!rows[row][i] && !cols[col][i] && !blocks[block][i]){
                board[row][col]=(char)(i+'1');
                //更新被入数字的状态
                rows[row][i]=cols[col][i]=blocks[block][i]=true;
                //填写完毕当前空白格，继续填写一格
                if (col==8)dfs(board,row+1,0);
                else dfs(board,row,col+1);
                //如果当前尝试填入的数字组合不能成功解数独(导致后序空白格无法填写)，则回溯
                if (!finished){
                    //擦除填入的数字，并更新被擦除数字的状态
                    board[row][col]='.';
                    rows[row][i]=cols[col][i]=blocks[block][i]=false;
                }
            }
        }
    }
}

代码看着长，除去注释其实没多少。而且这道题思路比较简单清晰易懂。

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github

NO.37 解数独 困难

NO.37 解数独困难