Leetcode37 解数独

题目

代码分析

递归参数的确定

1,使用的思想就是回溯递归，每放入一个位置就判断一下，如果可以的话，我们就继续递归，不行的话，复原当前位置，换一个数字继续递归。对于二维数组的话，我们的row和col是不断改变的。所以我们的方法参数包括row和col,每一次这个f的时候，需要改变的就是row和col。
2,当然也需要带上char[][] board这个二维数组
3,除了回溯的思想，我们还需要用到hash的概念，因为每放一个数字就要判断它的合法性，如果使用for循环进行判断的话，时间复杂度会很高，所以我们使用hash的思想来降低时间复杂度，需要判断的时间复杂度来自于三个地方

行，列，小方块

使用二维数组这个变形的hash结构

boolean[][] rowUsed=new boolean[row][num]
boolean[][] colUsed=new boolean[col][num]
boolean[][] smallAreaUsed=new boolean[row/3][col/3][nun]

举个例子,如果我们放入的数字是5,然后所在的行是3,我们的意思就是在第3行数字5有没有出现过，有没有出现过就是使用false和true

初始化

 public void solveSudoku(char[][] board) {
        // 三个布尔数组 表明 行, 列, 还有 3*3 的方格的数字是否被使用过
        boolean[][] rowUsed = new boolean[9][10];
        boolean[][] colUsed = new boolean[9][10];
        boolean[][][] boxUsed = new boolean[3][3][10];
        // 初始化
        for(int row = 0; row < board.length; row++){
            for(int col = 0; col < board[0].length; col++) {
                int num = board[row][col] - '0';
                if(1 <= num && num <= 9){
                    rowUsed[row][num] = true;
                    colUsed[col][num] = true;
                    boxUsed[row/3][col/3][num] = true;
                }
            }
        }
        // 递归尝试填充数组
        recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, 0, 0);
 }

递归

递归的大概框架如下

f(char[][] board,int row,int col,三个哈希结构)
{
         //base case
         //如果是空位置，就要具体的进行递归
　　//如果不是空位置,就继续递归进入　 
}

首先是base case,我们就想的极端一点，如果我们进入到最后一个位置的话，表明这个数独已经填充完毕，这样的话就表明数独解开了

if(col == board[0].length){
            col = 0;
            row++;
            if(row == board.length){
                return true;
            }
        }

两种情况，一个是最极端的情况，一个是有点极端的情况，对于后者，我们就需要换行操作，如果换行操作导致了是最后一行＋１的话，表明就是前者这个最极端的情况。这个就是base case的完成情况

然后就是对于空位置的处理情况，肯定就是一个个的字符进行尝试，尝试成功的话，就进入，如果失败的话，就for循环的下一个位置。如果所有的for循环都不成功，就表明这个数独是无解的就直接return false就可以了。
如果某一个循环的情况是有解的话，我们就可以直接return true，我们来展示一下我们的递归框架

for(循环１－－－－９)
{
      if 看看放数字可不可以，就是使用那三个hash结构进行判断
　 {
              如果可以放的话，我们就放入，然后修改哈希的结构。然后就进行递归了
　　　f(char[][] ,row,col+1,哈希结构)
             我们不能直接将这个f返回，只有它返回是true的情况才可以返回，如果是false的话，不能直接返回，因为我们还需要判断其他的情况，也就是使用下个循环的内容。
　　　如果没有返回true的话，表明我们就要进行下一次的循环了，然后就是复原操作
      } 　　
}
如果所有的情况都不行，表明在当前位置数独是没有解的，我们就直接返回false就可以了

详细代码如下

if(board[row][col]=='.')
        {
            for(char c='1';c<='9';c++)
            {
                int num=c-'0';
                boolean used=!(rowUsed[row][num]||colUsed[col][num]||smallAreaUsed[row/3][col/3][num]);
                if(used)
                {
                    board[row][col]=c;
                    rowUsed[row][num]=true;
                    colUsed[col][num]=true;
                    smallAreaUsed[row/3][col/3][num]=true;
                    if(f(board, rowUsed, colUsed, smallAreaUsed, row, col+1)) return true;
                    board[row][col]='.';

                    rowUsed[row][num]=false;
                    colUsed[col][num]=false;
                    smallAreaUsed[row/3][col/3][num]=false;
                }
            }
            return false;
        }

如果不是空的话，直接进入下次的循环就可以了

else
        {
            return f(board, rowUsed, colUsed, smallAreaUsed, row, col+1);
        }

代码展示

public static void main(String[] args) {
        char[][] 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'}
        };
        solveSudoku(board);
        for(int i=0;i<board.length;i++)
        {
            for(int j=0;j<board[0].length;j++)
            {
                System.out.print(board[i][j]+" ");
            }
            System.out.println();
        }
    }
    public static void solveSudoku(char[][] board) {
       //1-----9
       boolean[][] rowUsed=new boolean[9][10];
       boolean[][] colUsed=new boolean[9][10];
       boolean[][][] smallAreaUsed=new boolean[3][3][10];
       //init
       for(int i=0;i<board.length;i++)
           for(int j=0;j<board[0].length;j++)
           {
               if(board[i][j]!='.')
               {
                   int num=board[i][j]-'0';
                   rowUsed[i][num]=true;
                   colUsed[j][num]=true;
                   smallAreaUsed[i/3][j/3][num]=true;
               }
           }
       //递归求解
       f(board,rowUsed,colUsed,smallAreaUsed,0,0);

    }

    public static boolean f(char[][] board,
                            boolean[][] rowUsed, boolean[][] colUsed
            ,boolean[][][] smallAreaUsed
            ,int row,int col)
    {
        if(col==board[0].length)
        {
            col=0;
            row++;
            if(row==board.length)
            {
                return true;
            }
        }
        if(board[row][col]=='.')
        {
            for(char c='1';c<='9';c++)
            {
                int num=c-'0';
                boolean used=!(rowUsed[row][num]||colUsed[col][num]||smallAreaUsed[row/3][col/3][num]);
                if(used)
                {
                    board[row][col]=c;
                    rowUsed[row][num]=true;
                    colUsed[col][num]=true;
                    smallAreaUsed[row/3][col/3][num]=true;
                    if(f(board, rowUsed, colUsed, smallAreaUsed, row, col+1)) return true;
                    board[row][col]='.';

                    rowUsed[row][num]=false;
                    colUsed[col][num]=false;
                    smallAreaUsed[row/3][col/3][num]=false;
                }
            }
            return false;
        }else
        {
            return f(board, rowUsed, colUsed, smallAreaUsed, row, col+1);
        }
    }