关于算法:回溯算法最佳实践解数独

5次阅读

共计 3710 个字符，预计需要花费 10 分钟才能阅读完成。

读完本文，你能够去力扣拿下如下题目：

37. 解数独

———–

常常拿回溯算法来说事儿的，无非就是八皇后问题和数独问题了。那咱们明天就通过 理论且乏味的例子 来讲一下如何用回溯算法来解决数独问题。

说实话我小的时候也尝试过玩数独游戏，但素来都没有实现过一次。做数独是有技巧的，我记得一些比拟业余的数独游戏软件，他们会教你玩数独的技巧，不过在我看来这些技巧都太简单，我基本就没有趣味看上来。

不过自从我学习了算法，多艰难的数独问题都拦不住我了。上面是我用程序实现数独的一个例子：

PS：GIF 可能呈现 bug，若卡住点开查看即可，下同。

这是一个安卓手机中的数独游戏，我应用一个叫做 Auto.js 的脚本引擎，配合回溯算法来实现主动实现填写，并且算法记录了执行次数。

能够察看到前两次都执行了 1 万屡次，而最初一次只执行了 100 屡次就算出了答案，这阐明对于不同的场面，回溯算法失去答案的工夫是不雷同的。

那么计算机如何解决数独问题呢？其实十分的简略，就是穷举嘛，上面我可视化了求解过程：

算法的外围思路十分十分的简略，就是对每一个空着的格子穷举 1 到 9，如果遇到不非法的数字（在同一行或同一列或同一个 3×3 的区域中存在雷同的数字）则跳过，如果找到一个非法的数字，则持续穷举下一个空格子。

对于数独游戏，兴许咱们还会有另一个误区：就是下意识地认为如果给定的数字越少那么这个场面的难度就越大。

这个论断对人来说应该没故障，但对于计算机而言，给的数字越少，反而穷举的步数就越少，失去答案的速度越快，至于为什么，咱们前面探讨代码实现的时候会讲。

上一个 GIF 是最初一关 70 关，下图是第 52 关，数字比拟多，看起来仿佛不难，然而咱们看一下算法执行的过程：

能够看到算法在前两行穷举了半天都没有走进来，因为工夫起因我就没有持续录制了，事实上，这个场面穷举的次数大略是上一个场面的 10 倍。

言归正传，上面咱们就来具体探讨一下如何用算法来求解数独问题，顺便说说我是如何可视化这个求解过程的。

首先，咱们不必管游戏的 UI，先单纯地解决回溯算法，LeetCode 第 37 题就是解数独的问题，算法函数签名如下：

void solveSudoku(char[][] board);

输出是一个 9 ×9 的棋盘，空白格子用点号字符 . 示意，算法须要在原地批改棋盘，将空白格子填上数字，失去一个可行解。

至于数独的要求，大家想必都很相熟了，每行，每列以及每一个 3×3 的小方格都不能有雷同的数字呈现。那么，当初咱们间接套回溯框架即可求解。

前文回溯算法详解，曾经写过了回溯算法的套路框架，如果还没看过那篇文章的，倡议先看看。

回顾方才的 GIF 图片，咱们求解数独的思路很简略粗犷，就是对每一个格子所有可能的数字进行穷举。对于每个地位，应该如何穷举，有几个抉择呢？很简略啊，从 1 到 9 就是抉择，全副试一遍不就行了：

// 对 board[i][j] 进行穷举尝试
void backtrack(char[][] board, int i, int j) {
    int m = 9, n = 9;
    for (char ch = '1'; ch <= '9'; ch++) {
        // 做抉择
        board[i][j] = ch;
        // 持续穷举下一个
        backtrack(board, i, j + 1);
        // 撤销抉择
        board[i][j] = '.';
    }
}

emmm，再持续细化，并不是 1 到 9 都能够取到的，有的数字不是不满足数独的非法条件吗？而且当初只是给 j 加一，那如果 j 加到最初一列了，怎么办？

很简略，当 j 达到超过每一行的最初一个索引时，转为减少 i 开始穷举下一行，并且在穷举之前增加一个判断，跳过不满足条件的数字：

void backtrack(char[][] board, int i, int j) {
    int m = 9, n = 9;
    if (j == n) {
        // 穷举到最初一列的话就换到下一行从新开始。backtrack(board, i + 1, 0);
        return;
    }
    
    // 如果该地位是预设的数字，不必咱们操心
    if (board[i][j] != '.') {backtrack(board, i, j + 1);
        return;
    } 

    for (char ch = '1'; ch <= '9'; ch++) {
        // 如果遇到不非法的数字，就跳过
        if (!isValid(board, i, j, ch))
            continue;
        
        board[i][j] = ch;
        backtrack(board, i, j + 1);
        board[i][j] = '.';
    }
}

// 判断 board[i][j] 是否能够填入 n
boolean isValid(char[][] board, int r, int c, char n) {for (int i = 0; i < 9; i++) {
        // 判断行是否存在反复
        if (board[r][i] == n) return false;
        // 判断列是否存在反复
        if (board[i] == n) return false;
        // 判断 3 x 3 方框是否存在反复
        if (board[(r/3)*3 + i/3][(c/3)*3 + i%3] == n)
            return false;
    }
    return true;
}

emmm，当初基本上差不多了，还剩最初一个问题：这个算法没有 base case，永远不会进行递归。这个好办，什么时候完结递归？显然 r == m 的时候就阐明穷举完了最初一行，实现了所有的穷举，就是 base case。

另外，前文也提到过，为了缩小复杂度，咱们能够让 backtrack 函数返回值为 boolean，如果找到一个可行解就返回 true，这样就能够阻止后续的递归。只找一个可行解，也是题目的本意。

最终代码批改如下：

boolean backtrack(char[][] board, int i, int j) {
    int m = 9, n = 9;
    if (j == n) {
        // 穷举到最初一列的话就换到下一行从新开始。return backtrack(board, i + 1, 0);
    }
    if (i == m) {
        // 找到一个可行解，触发 base case
        return true;
    }

    if (board[i][j] != '.') {
        // 如果有预设数字，不必咱们穷举
        return backtrack(board, i, j + 1);
    } 

    for (char ch = '1'; ch <= '9'; ch++) {
        // 如果遇到不非法的数字，就跳过
        if (!isValid(board, i, j, ch))
            continue;
        
        board[i][j] = ch;
        // 如果找到一个可行解，立刻完结
        if (backtrack(board, i, j + 1)) {return true;}
        board[i][j] = '.';
    }
    // 穷举完 1~9，仍然没有找到可行解，此路不通
    return false;
}

boolean isValid(char[][] board, int r, int c, char n) {// 见上文}

当初能够答复一下之前的问题，为什么有时候算法执行的次数多，有时候少？为什么对于计算机而言，确定的数字越少，反而算出答案的速度越快？

咱们曾经实现了一遍算法，把握了其原理，回溯就是从 1 开始对每个格子穷举，最初只有试出一个可行解，就会立刻进行后续的递归穷举。所以暴力试出答案的次数和随机生成的棋盘关系很大，这个是说不准的。

那么你可能问，既然运行次数说不准，那么这个算法的工夫复杂度是多少呢？

对于这种工夫复杂度的计算，咱们只能给出一个最坏状况，也就是 O(9^M)，其中 M 是棋盘中空着的格子数量。你想嘛，对每个空格子穷举 9 个数，后果就是指数级的。

这个复杂度十分高，但稍作思考就能发现，实际上咱们并没有真的对每个空格都穷举 9 次，有的数字会跳过，有的数字基本就没有穷举，因为当咱们找到一个可行解的时候就立刻完结了，后续的递归都没有开展。

这个 O(9^M) 的复杂度实际上是齐全穷举，或者说是找到所有可行解的工夫复杂度。

如果给定的数字越少，相当于给出的约束条件越少，对于计算机这种穷举策略来说，是更容易进行上来，而不容易走回头路进行回溯的，所以说 如果仅仅找出一个可行解，这种状况下穷举的速度反而比拟快。

至此，回溯算法就实现了，你能够用以上代码通过 LeetCode 的判题零碎，上面咱们来简略说下我是如何把这个回溯过程可视化进去的。

让算法帮我玩游戏的外围是算法，如果你了解了这个算法，剩下就是借助安卓脚本引擎 Auto.js 调 API 操作手机了，工具我都放在后盾了，你等会儿就能够下载。

用伪码简略说下思路，我能够写两个函数：

void setNum(Button b, char n) {// 输出一个方格，将该方格设置为数字 n}

void cancelNum(Button b) {// 输出一个方格，将该方格上的数字撤销}

回溯算法的外围框架如下，只有在框架对应的地位加上对应的操作，即可将算法做抉择、撤销抉择的过程齐全展现进去，兴许这就是套路框架的魅力所在：

for (char ch = '1'; ch <= '9'; ch++) {Button b = new Button(r, c);
    // 做抉择
    setNum(b, ch);
    board[i][j] = ch;
    // 持续穷举下一个
    backtrack(board, i, j + 1)
    // 撤销抉择
    cancelNum(b);
    board[i][j] = '.';
}

以上思路就能够模拟出算法穷举的过程：

正文完