X

LEETCODE 37. Sudoku Solver 解题思路分析

题目大意:

解数独

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

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

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

空白格用 '.' 表示。

一个数独。

答案被标成红色。

Note:

  • 给定的数独序列只包含数字 1-9 和字符 '.'
  • 你可以假设给定的数独只有唯一解。
  • 给定数独永远是 9x9 形式的。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=37

解题思路分析:

对于矩阵中的任意一点,我们可选的数字范围在1-9之间。但考虑到当前行,列以及当前所在的小正方形内不能出现重复数字的原则,实际上可选的数字可能要小于9种。首先我们需要遍历一遍二维数组,查看每行,每列,以及每个小正方形内都包含哪些数字。记录数字出现的状态我们通过使用3个bool型数组来表示:

// usedPerRow[i][j]=true代表第i行中存在数字j
boolean[][] usedPerRow=new boolean[9][9];
// usedPerCol[i][j]=true代表第i列中存在数字j
boolean[][] usedPerCol=new boolean[9][9];
// usedPerSquare[i][j]=true代表第i个小正方形中存在数字j
boolean[][] usedPerSquare=new boolean[9][9];

接下来我们开始递归求解,递归函数中我们循环数组中每一个点,当遇到没有数字的位置时,我们尝试使用可以使用的数字填充该点。我们循环数字1-9,如果当前数字在当前行,列以及当前小正方形内均没被使用过,我们即可使用当前数字填充当前点,并将当前状态传到下层递归函数。如果下层递归函数返回true的话,代表当前选的数字可以使得全局成立,本层递归直接返回true。如果下层递归返回false,代表选择当前数字并不能使得全局成立,我们继续尝试选择填充下一个可选数字。当所有可选数字都不成立或者当前点没有可选数字时,本层递归返回false。当矩阵中所有点都已经填充完数字,递归终止,返回true。

实现代码:

// usedPerRow[i][j]=true代表第i行中存在数字j
boolean[][] usedPerRow=new boolean[9][9];
// usedPerCol[i][j]=true代表第i列中存在数字j
boolean[][] usedPerCol=new boolean[9][9];
// usedPerSquare[i][j]=true代表第i个小正方形中存在数字j
boolean[][] usedPerSquare=new boolean[9][9];
public void solveSudoku(char[][] board) {
    // 循环每一个点,统计每行每列以及每个小正方形中出现过的数字
    for(int r=0;r<9;r++){
        for(int c=0;c<9;c++){
            char ch = board[r][c];
            if(ch=='.') continue;
            usedPerRow[r][ch-'1']=true;
            usedPerCol[c][ch-'1']=true;
            int squareIndex=r/3*3+c/3;
            usedPerSquare[squareIndex][ch-'1']=true;
        }
    }
    help(board);
}
boolean help(char[][] board){
    // 循环每一个点
    for(int r=0;r<9;r++){
        for(int c=0;c<9;c++){
            // 如果当前点已经存在数字,跳过
            if( board[r][c]!='.') continue;
            // 当前点所在小正方形的下标
            int squareIndex=r/3*3+c/3;
            // 从数字1-9中尝试选择可行的数字填充到当前位置
            for(int i=0;i<9;i++){
                // 如果当前数字在当前列,行以及当前小正方形内没出现过
                if(!usedPerRow[r][i]&&!usedPerCol[c][i]
                   &&!usedPerSquare[squareIndex][i]){
                    // 尝试使用当前数字
                    board[r][c]=(char)(i+'1');
                    // 设置当前行该数字已使用过
                    usedPerRow[r][i]=true;
                    // 设置当前行该数字已使用过
                    usedPerCol[c][i]=true;
                    // 设置当前小正方形内该数字已使用过
                    usedPerSquare[squareIndex][i]=true;
                    // 递归至下层子问题
                    // 如果子问题返回true,本层递归直接返回true
                    if(help(board)) return true;
                    // 如果子问题返回false,代表当前数字不成立
                    // 将当前数字还原为'.'
                    board[r][c]='.';
                    // 还原当前数字的使用状态
                    usedPerRow[r][i]=false;
                    usedPerCol[c][i]=false;
                    usedPerSquare[squareIndex][i]=false;
                }
            } // 数字1-9循环结束
            // 如果选择数字1-9都无法成立,返回false
            return false;
        }
    }
    // 能走到这里,代表数组中都以设置上数字,返回true。
    return true;
}

本题解法执行时间为4ms。

Runtime: 4 ms, faster than 88.78% of Java online submissions for Sudoku Solver.

Memory Usage: 37.4 MB, less than 19.30% of Java online submissions for Sudoku Solver.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-37-sudoku-solver-解题思路分析/
Categories: leetcode
kwantong: