使用回溯算法解决数独

作者 : IT 大叔 本文共2184个字,预计阅读时间需要6分钟 发布时间: 2020-09-4

正如我在最近有关如何设计算法文章中所承诺的那样,在这里我将仔细研究另一种流行的算法设计技术,称为回溯

回溯是通过递增构建解决方案来解决递归问题的有用算法。通常,回溯涉及从可能的解决方案开始,如果它不起作用,则您回溯并尝试另一种解决方案,直到找到可行的解决方案。当解决诸如填字游戏,语言算术和Sudoku之类的约束满足问题时,回溯特别有用。

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

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

在本文中,我将通过解决一个称为Sudoku Solver的流行问题来演示回溯策略。

数独解算器

作为我自己的数独迷,我很高兴能深入研究这个问题。针对此问题的回溯算法将尝试将每个数字放在每一行和每一列中,直到解决为止。让我们从main方法开始:

function sudokuSolver(matrix) {
    if (solveSudoku(matrix) === true) {
        return matrix;
    }
    return 'NO SOLUTION';
}

现在,让我们进入算法的主要逻辑:

const UNASSIGNED = 0;

function solveSudoku(matrix) {
    let row = 0;
    let col = 0;
    let checkBlankSpaces = false;

    /* verify if sudoku is already solved and if not solved,
    get next "blank" space position */ 
    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;
        }
    }
    // no more "blank" spaces means the puzzle is solved
    if (checkBlankSpaces === false) {
        return true;
    }

    // try to fill "blank" space with correct num
    for (let num = 1; num <= 9; num++) {
        /* isSafe checks that num isn't already present 
        in the row, column, or 3x3 box (see below) */ 
        if (isSafe(matrix, row, col, num)) {
            matrix[row][col] = num;

            if (solveSudoku(matrix)) {
                return true;
            }

            /* if num is placed in incorrect position, 
            mark as "blank" again then backtrack with 
            a different 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));

这是通过回溯解决的数独示例:

使用回溯算法解决数独插图

结论

我对本文很感兴趣,希望您发现它有助于对回溯有一个基本的了解。以下是一些其他资源:

免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 使用回溯算法解决数独

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论