作者：Christina
翻译：疯狂的技术宅
原文：https://dev.to/christinamcmah…
未经允许严禁转载
前几天我们在《浅析常见的算法范式》中讨论了一些常见的算法范式，但是还留下了回溯算法没有解决。本文来研究回溯算法。
回溯是通过逐步构建解决方案来解决递归问题的算法。通常回溯从可能的解决方案开始，如果它不起作用，则需要回溯并尝试另一种解决方案，直到找到可行的解决方案为止。回溯在解决 CSP（约束满足问题）时特别有用，例如填字游戏、迷宫和数独等。
通常回溯算法可用于以下三种类型的问题：
- 需要找到可行解决方案的决策问题
- 需要找到最佳解决方案的优化问题
- 需要找到一组可行解决方案的列举问题
在本文中，我将通过解决数独问题来演示回溯策略。
解决数独问题
针对此类问题的回溯算法会尝试在每个空格中列举所有的数字，直到问题被解决为止。先从 main 方法开始：
function sudokuSolver(matrix) {
if (solveSudoku(matrix) === true) {
return matrix;
}
return '无解';
}接下来看一看算法的主要逻辑：
const UNASSIGNED = 0;
function solveSudoku(matrix) {
let row = 0;
let col = 0;
let checkBlankSpaces = false;
// 验证数独是否已解决，如果尚未解决，则获取下一个空格的位置
for (row = 0; row < matrix.length; row++) {
for (col = 0; col < matrix[row].length; col++) {
if (matrix[row][col] === UNASSIGNED) {
checkBlankSpaces = true;
break;
}
}
if (checkBlankSpaces === true) {
break;
}
}
//当没有空格时则意味着已经解决
if (checkBlankSpaces === false) {
return true;
}
// 尝试用正确的数字填充空格
for (let num = 1; num <= 9; num++) {
// isSafe 用于检查在行、列或 3x3 的格子中是否已经存在了数字 num（代码实现在后面）
if (isSafe(matrix, row, col, num)) {
matrix[row][col] = num;
if (solveSudoku(matrix)) {
return true;
}
// 如果 num 所在的位置不合适，需要再次标记为“空格”，然后用不同的 num 回溯
matrix[row][col] = UNASSIGNED;
}
}
return false;
}接下来看辅助函数的实现：
function isSafe(matrix, row, col, num) {
return (
!usedInRow(matrix, row, num) &&
!usedInCol(matrix, col, num) &&
!usedInBox(matrix, row - (row % 3), col - (col % 3), num)
);
}
function usedInRow(matrix, row, num) {
for (let col = 0; col < matrix.length; col++) {
if (matrix[row][col] === num) {
return true;
}
}
return false;
}
function usedInCol(matrix, col, num) {
for (let row = 0; row < matrix.length; row++) {
if (matrix[row][col] === num) {
return true;
}
}
return false;
}
function usedInBox(matrix, boxStartRow, boxStartCol, num) {
for (let row = 0; row < 3; row++) {
for (let col = 0; col < 3; col++) {
if (matrix[row + boxStartRow][col + boxStartCol] === num) {
return true;
}
}
}
return false;
}最后对算法进行测试：
const sudokuGrid = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
];
console.log(sudokuSolver(sudokuGrid));以下是通过回溯法求解数独问题的模拟动画：
希望本文能帮你理解回溯算法，以后我门还会再讨论更多有趣的算法。
本文首发微信公众号：前端先锋
欢迎扫描二维码关注公众号，每天都给你推送新鲜的前端技术文章
欢迎继续阅读本专栏其它高赞文章：
- 深入理解Shadow DOM v1
- 一步步教你用 WebVR 实现虚拟现实游戏
- 13个帮你提高开发效率的现代CSS框架
- 快速上手BootstrapVue
- JavaScript引擎是如何工作的？从调用栈到Promise你需要知道的一切
- WebSocket实战：在 Node 和 React 之间进行实时通信
- 关于 Git 的 20 个面试题
- 深入解析 Node.js 的 console.log
- Node.js 究竟是什么？
- 30分钟用Node.js构建一个API服务器
- Javascript的对象拷贝
- 程序员30岁前月薪达不到30K，该何去何从
- 14个最好的 JavaScript 数据可视化库
- 8 个给前端的顶级 VS Code 扩展插件
- Node.js 多线程完全指南
- 把HTML转成PDF的4个方案及实现