作者：Christina

翻译：疯狂的技术宅

原文：https://dev.to/christinamcmah...

未经容许严禁转载

前几天咱们在《浅析常见的算法范式》中探讨了一些常见的算法范式，然而还留下了回溯算法没有解决。本文来钻研回溯算法。

回溯是通过逐渐构建解决方案来解决递归问题的算法。通常回溯从可能的解决方案开始，如果它不起作用，则须要回溯并尝试另一种解决方案，直到找到可行的解决方案为止。回溯在解决 CSP（束缚满足问题）时特地有用，例如填字游戏、迷宫和数独等。

通常回溯算法可用于以下三种类型的问题：

  1. 须要找到可行解决方案的决策问题
  2. 须要找到最佳解决方案的优化问题
  3. 须要找到一组可行解决方案的列举问题

在本文中，我将通过解决数独问题来演示回溯策略。

解决数独问题

针对此类问题的回溯算法会尝试在每个空格中列举所有的数字，直到问题被解决为止。先从 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个计划及实现
  • 更多文章...