题目

力扣题目链接

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

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

示例：
image.png

  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"]]
  2. 输出：[["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"]]

解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
image.png

提示：

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字或者 ‘.’
  • 题目数据 保证 输入数独仅有一个解

思路

棋盘搜索问题可以使用回溯法暴力搜索，只不过这次我们要做的是二维递归。

怎么做二维递归呢？

大家已经跟着「算法总纲」刷过了如下回溯法题目，例如：77.组合，131.分割回文串，78.子集，46.全排列，以及51.N皇后，其实这些题目都是一维递归。

如果以上这几道题目没有做过的话，不建议上来就做这道题！

51.N皇后 是因为每一行每一列只放一个皇后，只需要一层 for 循环遍历一行，递归来来遍历列，然后一行一列确定皇后的唯一位置。

本题就不一样了，本题中棋盘的每一个位置都要放一个数字，并检查数字是否合法，解数独的树形结构要比 N 皇后更宽更深。

因为这个树形结构太大了，我抽取一部分，如图所示：
image.png

回溯三部曲

1、递归函数以及参数

递归函数的返回值需要是 boolean 类型，为什么呢？

因为解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回，相当于找从根节点到叶子节点一条唯一路径，所以需要使用 boolean 返回值，这一点在 51.N皇后 中已经介绍过了，一样的道理。

我把棋盘 board 保存到全局变量中，方便使用，因此就不需要传参了。

代码如下：

  1. char[][] board = null;
  2. boolean backtracking()

2、递归终止条件

本题递归不用终止条件，解数独是要遍历整个树形结构寻找可能的叶子节点就立刻返回。

不用终止条件会不会死循环？

递归的下一层的棋盘一定比上一层的棋盘多一个数，等数填满了棋盘自然就终止（填满当然好了，说明找到结果了），所以不需要终止条件！

那么有没有永远填不满的情况呢？

这个问题我在递归单层搜索逻辑里在来讲。

3、递归单层搜索逻辑

image.png

在树形图中可以看出我们需要的是一个二维的递归（也就是两个for循环嵌套着递归）

一个 for 循环遍历棋盘的行，一个 for 循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放 9 个数字的可能性！
代码如下：（详细看注释）

  1. private boolean backtracking() {
  2.     for (int i = 0; i < board.length; i++) {           // 遍历行
  3.         for (int j = 0; j < board[0].length; j++) {    // 遍历列
  4.             if (board[i][j] != '.') {                   // 跳过棋盘原来就存在的数字
  5.                 continue;
  6.             }
  8.             for (char k = '1'; k <= '9'; k++) {        // board[i, j] 这个位置放 k 是否合适
  9.                 if (isValidSudoku(i, j, k, board)) {   // 检查放置的 k 是否合法
  10.                     board[i][j] = k;                   // 放置k
  12.                     if (backtracking()) {               // 继续尝试给下一个空位填数字
  13.                         return true;                   // 如果找到合适一组立刻返回
  14.                     }
  16.                     board[i][j] = '.';                   // 回溯，撤销 k
  17.                 }
  18.             }
  20.             return false;                               // 9个数都试完了，都不行，那么就返回false
  21.             // 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
  22.             // 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
  23.         }
  24.     }
  26.     return true;                                       // 遍历完没有返回 false ，说明找到了合适棋盘位置了，返回 true
  27. }

注意这里 return false 的地方，这里放 return false 是有讲究的。

因为如果一行一列确定下来了，这里尝试了 9 个数都不行，说明这个棋盘找不到解决数独问题的解。

那么会直接返回 false ， 这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去。

判断棋盘是否合法

判断棋盘是否合法有如下三个维度：

  • 同行是否重复
  • 同列是否重复
  • 9宫格里是否重复

代码如下：

  1. boolean isValidSudoku(int row, int col, char val) {
  2.     // 同行是否重复
  3.     for (int i = 0; i < 9; i++) {
  4.         if (board[row][i] == val) {
  5.             return false;
  6.         }
  7.     }
  8.     // 同列是否重复
  9.     for (int j = 0; j < 9; j++) {
  10.         if (board[j][col] == val) {
  11.             return false;
  12.         }
  13.     }
  14.     // 9宫格里是否重复
  15.     int startRow = (row / 3) * 3;
  16.     int startCol = (col / 3) * 3;
  17.     for (int i = startRow; i < startRow + 3; i++) {
  18.         for (int j = startCol; j < startCol + 3; j++) {
  19.             if (board[i][j] == val) {
  20.                 return false;
  21.             }
  22.         }
  23.     }
  24.     return true;
  25. }

因为我将 board 设置为全局变量，因此可以直接访问，不需要函数传参。

总结

解数独可以说是非常难的题目了，如果还一直停留在单层递归的逻辑中，这道题目可以让大家瞬间崩溃。

所以我在开篇就提到了二维递归，这也是我自创词汇，希望可以帮助大家理解解数独的搜索过程。

一波分析之后，在看代码会发现其实也不难，唯一难点就是理解二维递归的思维逻辑。

这样，解数独这么难的问题，也被我们攻克了。

答案

Java

  1. class Solution {
  2.     char[][] board = null;
  4.     public void solveSudoku(char[][] board) {
  5.         this.board = board;
  7.         backtracking();
  8.     }
  10.     private boolean backtracking() {
  11.         // 一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！
  13.         // 遍历棋盘的行
  14.         for (int i = 0; i < board.length; i++) {
  15.             // 遍历棋盘的列
  16.             for (int j = 0; j < board[0].length; j++) {
  17.                 // 跳过原始数字
  18.                 if (board[i][j] != '.') {
  19.                     continue;
  20.                 }
  22.                 // 尝试向 棋盘[i,j] 这个位置放 1~9
  23.                 for (char k = '1'; k <= '9'; k++) {
  24.                     // 检查放置的数字是否合法
  25.                     if (isValidSudoku(i, j, k)) {
  26.                         // 给棋盘[i,j]位置分配数字
  27.                         board[i][j] = k;
  29.                         // 继续尝试给下一个空位填数字
  30.                         if (backtracking()) {
  31.                             return true;
  32.                         }
  34.                         // 回溯
  35.                         board[i][j] = '.';
  36.                     }
  37.                 }
  38.                 // 9个数都试完了，都不行，那么就返回false
  39.                 return false;
  40.                 // 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
  41.                 // 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
  42.             }
  43.         }
  45.         // 遍历完没有返回false，说明找到了合适棋盘位置了，返回true
  46.         return true;
  47.     }
  49.     /**
  50.      * 判断棋盘是否合法有如下三个维度:
  51.      * 同行是否重复
  52.      * 同列是否重复
  53.      * 9宫格里是否重复
  54.      */
  55.     private boolean isValidSudoku(int row, int col, char val) {
  56.         // 同行是否重复
  57.         for (int i = 0; i < 9; i++) {
  58.             if (board[row][i] == val) {
  59.                 return false;
  60.             }
  61.         }
  62.         // 同列是否重复
  63.         for (int j = 0; j < 9; j++) {
  64.             if (board[j][col] == val) {
  65.                 return false;
  66.             }
  67.         }
  68.         // 9宫格里是否重复
  69.         int startRow = (row / 3) * 3;
  70.         int startCol = (col / 3) * 3;
  71.         for (int i = startRow; i < startRow + 3; i++) {
  72.             for (int j = startCol; j < startCol + 3; j++) {
  73.                 if (board[i][j] == val) {
  74.                     return false;
  75.                 }
  76.             }
  77.         }
  78.         return true;
  79.     }
  80. }

REF

https://programmercarl.com/0037.解数独.html
https://leetcode-cn.com/problems/sudoku-solver/