问题描述
来源：LeetCode第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"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
题目数据 保证 输入数独仅有一个解
问题分析
前面我们刚讲过字节二面原题，有效的数独。今天我们就来解数独，数独问题和八皇后问题很类似，都可以使用回溯算法解决，不过数独问题要比八皇后问题稍微难一点，因为八皇后问题只需要每行放一个皇后就可以了，而数独问题需要每行全部放上数字。这题我们就使用回溯算法来解决。
回溯算法其实就是试探，如果不了解回溯算法的也可以看下我很久之前写的一篇文章450，什么叫回溯算法，一看就会，一写就废。对于这道题，我们可以在每一个空的位置放入一个数字，如果所有空的位置都能正确放入数字，说明这就是数独的一个解，如果任何一个位置放入数字发生了冲突，我们就撤销，然后放其他数字……如下图所示，我们在第3个位置可以放1,2,4,6,8,9……，其实就相当于一颗n叉树，如果当前位置能放数字，我们就沿着这个分支往下走，如果不能放，我们就撤销，这个具体也可以参照593，经典回溯算法题-全排列
来看下代码
//回溯算法
public boolean solveSudoku(char[][] board) {
return backTrace(board, 0, 0);
}
//row表示第几行，col表示第几列。
private boolean backTrace(char[][] board, int row, int col) {
//注意row是从0开始的，当row等于board.length的时候表示数独的
//最后一行全部读遍历完了，说明数独中的值是有效的，直接返回true
if (row == board.length)
return true;
//如果当前行的最后一列也遍历完了，就从下一行的第一列开始。这里的遍历
//顺序是从第1行的第1列一直到最后一列，然后第二行的第一列一直到最后
//一列，然后第三行的……
if (col == board.length)
return backTrace(board, row + 1, 0);
//如果当前位置已经有数字了，就不能再填了，直接跳过
if (board[row][col] != '.')
return backTrace(board, row, col + 1);
//如果上面条件都不满足，我们就从1到9选择一个合适的数字填入到数独中
for (char i = '1'; i <= '9'; i++) {
//判断当前位置[row，col]是否可以放数字i，如果不能放再判断下
//一个能不能放，直到找到能放的为止，如果从1-9都不能放，就会下面
//直接return false
if (!isValid(board, row, col, i))
continue;
//如果能放数字i，就把数字i放进去
board[row][col] = i;
//如果成功就直接返回，不需要再尝试了
if (backTrace(board, row, col))
return true;
//否则就撤销重新选择
board[row][col] = '.';
}
//如果当前位置[row，col]不能放任何数字，直接返回false
return false;
}
//验证当前位置[row，col]是否可以存放字符c
private boolean isValid(char[][] board, int row, int col, char c) {
for (int i = 0; i < 9; i++) {
//当前列有没有和字符c重复的
if (board[i][col] == c)
return false;
//当前行有没有和字符c重复的
if (board[row][i] == c)
return false;
//当前的单元格内是否有和字符c重复的
if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
return false;
}
return true;
}联系客服
