LeetCode算法题解（回溯，难点）

题解（回溯，难点）"/>

LeetCode算法题解（回溯，难点）

LeetCode37. 解数独

题目链接：37. 解数独

题目描述：

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

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

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 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] 是一位数字或者 '.'
• 题目数据 保证 输入数独仅有一个解

算法分析：

利用回溯法确定并放置每个格子能放值的数字。

回溯的返回值类型为boolean，只要找到一个符合的条件就直接返回true。

利用双重for循环搜索每个格子的位置，并判断该格子是否是空格，如果不是空格不是空格直接跳过这一个格子。

   public boolean backTravel(int x, int y, char[][] board) {for(int i = x; i < board.length; i++) {for(int j = y; j < board[0].length; j++) {//遍历每一个格子if(board[i][j] != '.') continue;....}}}

如果该格子是空格子，判断该格子是否可以放入1-9当中的数字如果可以，放入数字，然后递归、回溯。

for(char ch = '1'; ch <= '9'; ch++) {if(canPut(ch, i, j, board)) {//判断当前空白格是否可以用1-9数字来填入board[i][j] = ch;//如果可以将数字字符填入空格内if(backTravel(i, y, board)) return true;//然后递归，如果递归返回的是true那么说明找到了解决方案，直接返回trueboard[i][j] = '.';//如果没找到，进行回溯}
}

判断是否可以放数字的函数：

public boolean canPut(char ch, int x, int y, char[][] board) {//判断当下坐标是否可以放置chfor(int i = 0; i < board.length; i++) {//判断这一列是否出现过ch...}for(int j = 0; j < board[0].length; j++) {//判断这一行是否出现过ch...}//找到当前格子所属的3*3宫格的左上角坐标int startx = (x/3)*3;int starty = (y/3)*3;for(int i = startx; i < startx + 3; i++) {//判断当前坐标所属的3*3宫格内是否出现chfor(int j = starty; j < starty + 3; j++) {...}}return true;}

完整的代码如下：

class Solution {public boolean canPut(char ch, int x, int y, char[][] board) {//判断当下坐标是否可以放置chfor(int i = 0; i < board.length; i++) {//判断这一列是否出现过chif(board[i][y] == ch)return false;}for(int j = 0; j < board[0].length; j++) {//判断这一行是否出现过chif(board[x][j] == ch)return false;}//找到当前格子所属的3*3宫格的左上角坐标int startx = (x/3)*3;int starty = (y/3)*3;for(int i = startx; i < startx + 3; i++) {//判断当前坐标所属的3*3宫格内是否出现chfor(int j = starty; j < starty + 3; j++) {if(board[i][j] == ch) return false;}}return true;}public boolean backTravel(int x, int y, char[][] board) {for(int i = x; i < board.length; i++) {for(int j = y; j < board[0].length; j++) {//遍历每一个格子if(board[i][j] != '.') continue;for(char ch = '1'; ch <= '9'; ch++) {if(canPut(ch, i, j, board)) {//判断当前空白格是否可以用1-9数字来填入board[i][j] = ch;//如果可以将数字字符填入空格内if(backTravel(i, y, board)) return true;//然后递归，如果递归返回的是true那么说明找到了解决方案，直接返回trueboard[i][j] = '.';//如果没找到，进行回溯}}//1-9都不能填入当前空格，说明找不到解诀数独的方法，返回falsereturn false;}}//遍历完了都没有返回false，说明找到了合适的棋盘位置，返回truereturn true;}public void solveSudoku(char[][] board) {backTravel(0, 0, board);}
}

总结

这道题的难点是对每个空格子该放入哪个数字，以及什么时候结束回溯的操作。