【游戏】实现数独作弊器

labuladong原创约 249 字

按照要求实现 solveSudoku 方法，完成一个可运行的数独作弊器，通过暴力穷举一键解决任何数独问题。

完成代码后请点击「提交」按钮，让算法完成数独题目。完成后，可以点击「回放」按钮，查看算法暴力穷举的过程。

数独游戏演示

这道题比较简单，可以直接套用回溯算法实践：数独和 N 皇后问题的解法。参考代码如下：

function solveSudoku(boardHandler) {
    // 标记是否已经找到可行解
    let found = false;

    function backtrack(index) {
        if (found) {
            // 已经找到一个可行解，立即结束
            return;
        }

        const m = 9, n = 9;
        const i = Math.floor(index / n), j = index % n;
        if (index === m * n) {
            // 找到一个可行解，触发 base case
            found = true;
            return;
        }

        if (boardHandler.get(i, j) !== null && !boardHandler.isEditable(i, j)) {
            // 如果有预设数字，不用我们穷举
            backtrack(index + 1);
            return;
        }

        for (let c = 1; c <= 9; c++) {
            // 剪枝：如果遇到不合法的数字，就跳过
            if (!isValid(i, j, c)) {
                continue;
            }

            // 做选择
            boardHandler.set(i, j, c);

            backtrack(index + 1);
            if (found) {
                // 如果找到一个可行解，立即结束
                // 不要撤销选择，否则值会被重置
                return;
            }

            // 撤销选择
            boardHandler.set(i, j, null);
        }
    }

    function isValid(r, c, num) {
        // 判断行是否存在重复
        for (let i = 0; i < 9; i++) {
            if (boardHandler.get(r, i) === num) return false;
        }
        
        // 判断列是否存在重复
        for (let i = 0; i < 9; i++) {
            if (boardHandler.get(i, c) === num) return false;
        }
        
        // 判断 3 x 3 方框是否存在重复
        const boxRow = Math.floor(r / 3) * 3;
        const boxCol = Math.floor(c / 3) * 3;
        for (let i = 0; i < 3; i++) {
            for (let j = 0; j < 3; j++) {
                if (boardHandler.get(boxRow + i, boxCol + j) === num) {
                    return false;
                }
            }
        }
        
        return true;
    }

    backtrack(0);
}