数据结构与算法之递归: LeetCode 37. 解数独 (Ts版)

解数独

• https://leetcode.cn/problems/sudoku-solver/description/

描述

• 编写一个程序，通过填充空格来解决数独问题
• 数独的解法需 遵循如下规则：
  • 数字 1-9 在每一行只能出现一次
  • 数字 1-9 在每一列只能出现一次
  • 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
• 数独部分空格内已填入了数字，空白格用 ‘.’ 表示

示例 1

输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示

• board.length == 9
• board[i].length == 9
• board[i][j] 是一位数字或者 ‘.’
• 题目数据 保证 输入数独仅有一个解

Typescript 版算法实现

1 ) 方案1: 回溯

/**
 Do not return anything, modify board in-place instead.
 */
function solveSudoku(board: string[][]): void {
    const line: boolean[][] = Array.from({ length: 9 }, () => Array(9).fill(false));
    const column: boolean[][] = Array.from({ length: 9 }, () => Array(9).fill(false));
    const block: boolean[][][] = Array.from({ length: 3 }, () => 
        Array.from({ length: 3 }, () => Array(9).fill(false))
    );
    const spaces: number[][] = [];

    // 初始化状态
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            if (board[i][j] === '.') {
                spaces.push([i, j]);
            } else {
                const digit = parseInt(board[i][j]) - 1;
                line[i][digit] = true;
                column[j][digit] = true;
                block[Math.floor(i / 3)][Math.floor(j / 3)][digit] = true;
            }
        }
    }

    // 深度优先搜索函数
    function dfs(pos: number): boolean {
        if (pos === spaces.length) {
            return true;
        }
        const [i, j] = spaces[pos];
        for (let digit = 0; digit < 9; digit++) {
            if (!line[i][digit] && !column[j][digit] && !block[Math.floor(i / 3)][Math.floor(j / 3)][digit]) {
                line[i][digit] = true;
                column[j][digit] = true;
                block[Math.floor(i / 3)][Math.floor(j / 3)][digit] = true;
                board[i][j] = (digit + 1).toString();

                if (dfs(pos + 1)) {
                    return true;
                }

                // 回溯
                line[i][digit] = false;
                column[j][digit] = false;
                block[Math.floor(i / 3)][Math.floor(j / 3)][digit] = false;
                board[i][j] = '.';
            }
        }
        return false;
    }

    dfs(0);
}

2 ) 方案2: 位运算优化

/**
 Do not return anything, modify board in-place instead.
 */
function solveSudoku(board: string[][]): void {
    const line: number[] = Array(9).fill(0);
    const column: number[] = Array(9).fill(0);
    const block: number[][] = Array.from({ length: 3 }, () => Array(3).fill(0));
    const spaces: number[][] = [];

    // 翻转函数，用于设置或清除位
    function flip(i: number, j: number, digit: number) {
        const mask = 1 << digit;
        line[i] ^= mask;
        column[j] ^= mask;
        block[Math.floor(i / 3)][Math.floor(j / 3)] ^= mask;
    }

    // 初始化状态
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            if (board[i][j] === '.') {
                spaces.push([i, j]);
            } else {
                const digit = parseInt(board[i][j]) - 1;
                flip(i, j, digit);
            }
        }
    }

    // 深度优先搜索函数
    function dfs(pos: number): boolean {
        if (pos === spaces.length) {
            return true;
        }
        const [i, j] = spaces[pos];
        let mask = 0x1ff & ~(line[i] | column[j] | block[Math.floor(i / 3)][Math.floor(j / 3)]);

        while (mask > 0) {
            const digit = Math.log2(mask & -mask); // 找到最右侧的 1 的位置
            flip(i, j, digit);
            board[i][j] = (digit + 1).toString();
            if (dfs(pos + 1)) {
                return true;
            }
            flip(i, j, digit);
            mask &= mask - 1; // 将最右侧的 1 置为 0
        }
        return false;
    }

    dfs(0);
}

3 ) 方案3: 枚举优化

/**
 Do not return anything, modify board in-place instead.
 */
function solveSudoku(board: string[][]): void {
    const line: number[] = Array(9).fill(0);
    const column: number[] = Array(9).fill(0);
    const block: number[][] = Array.from({ length: 3 }, () => Array(3).fill(0));
    const spaces: number[][] = [];

    // 翻转函数，用于设置或清除位
    function flip(i: number, j: number, digit: number) {
        const mask = 1 << digit;
        line[i] ^= mask;
        column[j] ^= mask;
        block[Math.floor(i / 3)][Math.floor(j / 3)] ^= mask;
    }

    // 初始化已知数字的状态
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            if (board[i][j] !== '.') {
                const digit = parseInt(board[i][j]) - 1;
                flip(i, j, digit);
            }
        }
    }

    // 尝试通过唯一解填充空格
    let modified: boolean;
    do {
        modified = false;
        for (let i = 0; i < 9; i++) {
            for (let j = 0; j < 9; j++) {
                if (board[i][j] !== '.') {
                    continue;
                }
                let mask = 0x1ff & ~(line[i] | column[j] | block[Math.floor(i / 3)][Math.floor(j / 3)]);
                if ((mask & (mask - 1)) === 0 && mask !== 0) { // mask 的二进制表示仅有一个 1
                    const digit = Math.log2(mask); // 找到最右侧的 1 的位置
                    flip(i, j, digit);
                    board[i][j] = (digit + 1).toString();
                    modified = true;
                }
            }
        }
    } while (modified);

    // 记录剩余未填充的空格
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            if (board[i][j] === '.') {
                spaces.push([i, j]);
            }
        }
    }

    // 深度优先搜索函数
    function dfs(pos: number): boolean {
        if (pos === spaces.length) {
            return true;
        }
        const [i, j] = spaces[pos];
        let mask = 0x1ff & ~(line[i] | column[j] | block[Math.floor(i / 3)][Math.floor(j / 3)]);

        while (mask > 0) {
            const digit = Math.log2(mask & -mask); // 找到最右侧的 1 的位置
            flip(i, j, digit);
            board[i][j] = (digit + 1).toString();
            if (dfs(pos + 1)) {
                return true;
            }
            flip(i, j, digit);
            mask &= mask - 1; // 将最右侧的 1 置为 0
        }
        return false;
    }

    dfs(0);
}