编程语言算法
递归搜索与回溯算法综合练习：暴搜决策树详解
通过多个经典算法题（如优美的排列、N 皇后、数独、单词搜索等），深入讲解递归、搜索与回溯算法。重点分析了暴搜决策树的构建、剪枝策略（如行列对角线检测、哈希映射优化）以及代码实现细节。内容涵盖问题解析、算法原理、函数设计及常见难点处理，帮助读者掌握回溯算法的核心逻辑与应用技巧。
通过多个经典算法题（如优美的排列、N 皇后、数独、单词搜索等），深入讲解递归、搜索与回溯算法。重点分析了暴搜决策树的构建、剪枝策略（如行列对角线检测、哈希映射优化）以及代码实现细节。内容涵盖问题解析、算法原理、函数设计及常见难点处理，帮助读者掌握回溯算法的核心逻辑与应用技巧。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
绿色剪枝：剪去遍历的格子所在列出现其他皇后的情况； 紫色剪枝：剪去遍历的格子所在主副对角线出现其他皇后的情况；
所以 N = 3，3 皇后是没有合法的放置方法的； 当我们的行数为 N+1，说明已经枚举到了一种合法的结果。
如何剪枝：考虑当前位置，能否放上皇后
策略一：无脑循环
我们在遍历到一个格子的时候，使用四个循环判断当前格子所在行、列、左对角线、右对角线是否放有其他皇后，总体时间复杂度 O(N) = 4N * (2^N)。虽然时间复杂度高，但是也是可以通过的。 我们可以对这个方法进行优化，因为我们的决策树是每一行的其中一个格子用来放皇后，所以行是一定不会出现皇后攻击的情况的，所以只用看列、左对角线、右对角线是否放有其他皇后。
策略二：类似哈希表的策略
对于棋盘，我们分别定义两个 boolean 类型的数组 row[]，col[]，用于判断某一行或者某一列是否放置皇后。
如果某个格子放置有皇后，对应的 row[i]，col[j] 要置为 true；后续再进行决策的时候，就可以先看看对应的 row，col 是否为 true，任意一个为 true 则不用再考虑本次枚举的格子。
接下来，我们来解决主对角线和副对角线的情况。
我们通过观察可以发现，当皇后要放置 N 个时，对应的主对角线和副对角线都是 2*N - 1。 并且斜率分别是 1 和 -1，所以对于一条对角线，可以用 y = x + b 或者 y = -x + b 来表示。
对于主对角线，则有 y - x = b，纵坐标 + 横坐标为一个定值；对于副对角线，则有 x + y = b，纵坐标 - 横坐标为一个定值；
所以我们再次定义两个 boolean 类型的数组 dig1，dig2，分别表示主对角线和副对角线；这两个数组的长度为 2*N，用于存储所有的主对角线，或者副对角线。 用 b = y - x，b = y + x 来表示某一条对角线的映射关系，当 dig1[b] == true || dig2[b] == true，则说明该格子所在对角线放有其他皇后。
但是还有一个细节问题：
对于上图的主对角线，y - x 是一个负数，如果直接使用 dig1[b] 会越界； 解决办法：添加上一个偏移量 n：y - x + n = b + n，让对角线统一向上移动 n 个单位，来处理截距为负数的情况；所以针对主对角线，我们判断的是 dig1[b + n] 是否是 true 即可。
编写代码
前期初始化操作
主逻辑
题目解析
本题并不是关于暴搜的题目，而是一个哈希表的题；我们通过讲解这道题的算法原理，为下一道题 解数独 做好铺垫。
算法原理
解法：暴搜
我们先来定义一个 boolean 类型的数组 row[][]：
第一个 [i] 表示的是数独表中的第 i 行，第二个 [j] 表示的是在这一行有没有出现 j 这个数字； 如：row[2][4] 表示的是第二行有没有出现 4 这个数字，有的话 row[2][4] == true；
col[i][j] 数组同理，表示的是第 i 列是否出现了 j 这个数字；
除了用数组来表示数度表外，我们也可以用哈希表来表示数独表，并且用哈希表非常巧妙：
我们是以一个 3 x 3 的小数独表作为一个单位格子的，此时下标就只有 0，1，2；
我们设置一个 boolean 类型的数组 grid：
grid[0][0] 表示左上角第一个 3x3 的大方格；
为了查看一个 3x3 的大方格所有数是否都出现过，我们再开一个空间给 grid：
如何定义小方格和大方格下标的映射关系呢？
当有一个元素的位置为 [x, y]，映射的九宫格下标位置为 [x/3, y/3]；
编写代码
题目解析
算法原理
解法：暴搜
决策树
上图代表决策树的某一条分支，我们可以发现，当按照其中一条分支填到第一行最后一个格子时，第一行每使用过的最后一个元素可能是不能填入该格子中的。
那我们怎么知道这条分支的选择不能填满数独表呢？在遍历某个 '.' 的格子时，如果所有数都不符合题意，我们返回 false 即可；
这个代码的报错原因，就是没有对【因为前面的选择，导致某一个格子 1 到 9 都不能填入】的情况进行处理；
所以如果遇到【某一个格子 1 到 9 都不能填入】的情况，我们就应该向上返回 false，因此，我们的 dfs 应该设置 boolean 类型的返回值，告诉上一层，这种选法是否可以得到正确的数独，如果返回 false，我们就要让上一层的格子尝试下一个数；
dfs 的参数其实可以直接把 board 数组传入即可；在 dfs 中遍历 board，专门处理 board[i][j] == '.' 的情况；
编写代码
初始化
填数逻辑
攻克难点
本题难点就是要想到 dfs 是 boolean 类型，并且要找到 dfs 中合适的位置进行返回；
对这三处 return 的解读
题目解析
算法原理
解法：深度优先遍历
模拟过程
我们以下面这个矩阵和 word 为例子来模拟过程：
刚开始，会先遍历矩阵中所有的元素，直到找到 word 的第一个字符 'A'
此时会对当前 A 的格子上下左右进行扫描，直到找到 B：
对于当前位置的 A，上下左右位置并没有 B，说明这个 A 不是我们要找的 A，我们寻找下一个 A:
此时，我们发现当前 A 的位置右边和下方都有 B，就需要递归这两种情况：
下方的 B 上下左右查找，并没有找到 C，我们遍历右边的 B
此时的情况和上面同理：
最终得到结果，返回 true：
如果按照上面的模拟过程，矩阵找不到 word，则返回 false；
决策树
函数设计
细节问题一：如何避免走重复路径
问题描述
模拟过程
解决方法一：设置一个 boolean 数组
定义一个跟原始矩阵相同规模的 boolean 数组：
用 visit 来标记当前位置，下次遍历到某一个位置时，通过 visit 查看这个位置是否已经被使用过；
解决方法二：修改原始矩阵的值
当我们对某一个格子进行上下左右查找，查找到下一个字符时，把这个位置修改成 '.'
面试时可询问是否允许修改原始矩阵，直接修改原数据存在风险；
细节问题二：用向量数组映射 (i, j) 位置的上下左右坐标
设置两个一维数组 dx[4]，dy[4]：
dx[i] 和 dy[i] 要能映射到同一个方向，映射关系如下：
我们使用一个 for 循环，就可以一个坐标的上下左右关系全部找到；如果要找 8 个方向，我们就定义两个长度为 8 的数组，来表示 8 个不同的方向；这种方法在二维数组表示方向的时候，是非常好用的；
编写代码
准备工作
在主函数中，先遍历一次矩阵，找到第一个 word[0]，然后调用 dfs，从第一个 word[0] 所在位置开始找 word 剩下的元素；
主逻辑
代码细节详解
模拟上述对 return 会遇到的情况：
题目解析
算法原理
本题的算法原理和上一题是一类题型，解法大差不差，只是一些细节问题不同；这一题先尝试自己编写代码，再参考标准解法优化。
解法：暴搜
编写代码
编写历程
那么，我们什么时候在主函数更新结果呢？如果要设置递归出口，就要再写一层 for 循环，判断上下左右的 vis==true || grid==0，对于这道题是没有必要设置递归出口的；
只需要找到一轮递归的最大值 tmp 即可，并且更新 ret 即可；所以我们一进入 dfs 就更新 ret；
总结
关于更新结果的问题是难点：尤其是在哪里更新结果？这么更新结果有什么用？为什么要这样更新结果？ 每次作出一题，都要想清楚这几个问题，并且学会新的处理细节问题的方式，如：二维矩阵搜索路径时，避免走重复路径的方法；使用向量坐标表示一个格子不同的方向；
题目解析
算法原理
解法：暴搜
编写代码
优化
减少循环次数：
继续优化
我们可以对递归出口进行优化，原来是只有合法路径才 return，现在是只要走到终点就 return：
关于暴搜的题目，算法原理其实并不难，重点考察的就是我们的代码能力，以及能否发现细节问题，并且对细节问题进行合理的处理；
