乐趣区

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

读完本文,你能够去力扣拿下如下题目:

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] = '.';
}

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

退出移动版