题目大意：
解数独
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
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-解题思路分析/