LeetCode算法题解（回溯，难点）|LeetCode37. 解数独

LeetCode37. 解数独

题目链接：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] 是一位数字或者 '.'
题目数据保证输入数独仅有一个解

算法分析：

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

回溯的返回值类型为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那么说明找到了解决方案，直接返回true
      board[i][j] = '.';//如果没找到，进行回溯
   }
}

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

public boolean canPut(char ch, int x, int y, char[][] board) {//判断当下坐标是否可以放置ch
        for(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宫格内是否出现ch
            for(int j = starty; j < starty + 3; j++) {
                ...
            }
        }
        return true;
    }

完整的代码如下：

class Solution {
    public boolean canPut(char ch, int x, int y, char[][] board) {//判断当下坐标是否可以放置ch
        for(int i = 0; i < board.length; i++) {//判断这一列是否出现过ch
            if(board[i][y] == ch)
            return false;
        }
        for(int j = 0; j < board[0].length; j++) {//判断这一行是否出现过ch
            if(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宫格内是否出现ch
            for(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那么说明找到了解决方案，直接返回true
                       board[i][j] = '.';//如果没找到，进行回溯
                   }
               }
               //1-9都不能填入当前空格，说明找不到解诀数独的方法，返回false
               return false;
           }
       }
       //遍历完了都没有返回false，说明找到了合适的棋盘位置，返回true
       return true;
    }
    public void solveSudoku(char[][] board) {
        backTravel(0, 0, board);
    }
}