JavaScript回溯法数独求解算法异常行为排查与修复

原始问题代码 #

let puzzle = [
    [0, 0, 7, 0, 0, 3, 5, 0, 0],
    [6, 0, 5, 4, 0, 8, 3, 0, 2],
    [0, 0, 4, 5, 2, 0, 9, 0, 6],
    [0, 0, 0, 0, 7, 1, 2, 0, 9],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [8, 0, 9, 2, 3, 0, 0, 0, 0],
    [9, 0, 1, 0, 8, 5, 6, 0, 0],
    [7, 0, 3, 9, 0, 2, 8, 0, 5],
    [0, 0, 8, 7, 0, 0, 1, 0, 0]
];

class Sudoku 
{
    constructor(puzzle) 
    {
        this.sudoku = puzzle;
    }

    isPossible(y, x, n) 
    {
        for (let i = 0; i < 9; i++) 
        {
            if (this.sudoku[y][i] == n)
                return false;
        }

        for (let i = 0; i < 9; i++) 
        {
            if (this.sudoku[i][x] == n)
                return false;
        }

        let y0 = (Math.floor(y / 3) * 3);
        let x0 = (Math.floor(x / 3) * 3);
        
        for (let i = 0; i < 3; i++) 
        {
            for (let j = 0; j < 3; j++) 
            {
                if (this.sudoku[y0 + i][x0 + j] == n)
                    return false;
            }
        }

        return true;
    }

    solve()
    {
        for (let y = 0; y < 9; y++)
        {
            for (let x = 0; x < 9; x++)
            {
                if (this.sudoku[y][x] == 0)
                {
                    for (let n = 1; n <= 9; n++)
                    {
                        if (this.isPossible(y, x, n))
                        {
                            this.sudoku[y][x] = n;
                            this.solve();
                            this.sudoku[y][x] = 0;
                        }
                    }

                    return;
                }
            }
        }

        console.table(this.sudoku);
    }
}

let s = new Sudoku(puzzle);
s.solve();

问题解答 #

1. 现象产生原因 #

这是无终止条件回溯算法的固有执行表现：当前solve方法实现的是暴力枚举所有可能填法的回溯逻辑，仅在递归到所有格子填充完成时触发打印，但没有设置「找到合法解后立即终止递归」的判断，递归流程会自动执行回溯退栈操作，逐层撤销之前试填的数字，直到退回到最外层调用，最终矩阵会回到初始未填充状态。

2. console.table执行后程序继续运行的触发逻辑 #

触发后续执行的是递归调用点后的回溯重置代码。当最深层递归（所有格子填满、无空位）执行完console.table后，当前层solve方法执行完毕，会回到上一层递归的调用位置，也就是this.solve();的下一行代码：this.sudoku[y][x] = 0;。这行代码会把当前层试填的数字重置为0，之后继续循环尝试下一个可能的数字，当前层所有数字试完则返回上一层，逐层执行重置逻辑，直到整个递归栈清空。

3. 不会二次执行console.table的原因 #

console.table的触发条件是遍历完9*9所有格子、找不到任何值为0的空位，也就是只有拼出完全符合数独规则的完整矩阵时才会走到这行代码：

• 回溯过程是逐层把已填数字改回0，过程中始终存在空位，不满足全填充的触发条件；
• 该数独谜题只有唯一合法解，回溯全程不会枚举到第二个符合规则的完整矩阵，因此不会二次触发打印。

4. 找到解后立即终止、保留结果的修改方案 #

给solve方法增加布尔类型返回值作为「已找到解」的传递信号：

• 当递归走到全填充、打印结果的位置时，返回true，表示已经找到合法解；
• 每一层递归调用子solve后，如果收到返回值true，立刻向上返回true，终止当前层的循环，不执行重置为0的回溯逻辑；
• 如果当前空位所有1-9的数字都尝试过仍不合法，返回false，通知上层继续尝试其他数字。

修改后的完整solve方法代码如下：

solve()
{
    for (let y = 0; y < 9; y++)
    {
        for (let x = 0; x < 9; x++)
        {
            if (this.sudoku[y][x] == 0)
            {
                for (let n = 1; n <= 9; n++)
                {
                    if (this.isPossible(y, x, n))
                    {
                        this.sudoku[y][x] = n;
                        // 收到已找到解的信号，直接向上返回，不执行回溯重置
                        if (this.solve()) {
                            return true;
                        }
                        this.sudoku[y][x] = 0;
                    }
                }
                // 当前空位无合法数字，返回false通知上层继续尝试
                return false;
            }
        }
    }
    // 所有空位填充完成，打印结果并返回找到解的信号
    console.table(this.sudoku);
    return true;
}

修改后执行s.solve()，打印完结果后递归会立即终止，实例的sudoku属性会保留完整填充的解矩阵，不会被回溯重置。

内容的提问来源于stack exchange，提问作者andrewthecoder