LeetCode 37. 解数独

Categories:

题目描述
思路分析
1. 解法一：回溯 + 布尔数组预处理（推荐）
2. 解法二：朴素回溯
相似题目

题目描述

✅ 37. 解数独

思路分析

解法一：回溯 + 布尔数组预处理（推荐）

核心思路：

用三个布尔数组 rowUsed[i][d]、colUsed[j][d]、boxUsed[b][d] 分别记录第 i 行、第 j 列、第 b 个 3×3 宫格中数字 d 是否已被使用，其中宫格编号 b = (i/3)*3 + j/3。

初始化时遍历棋盘，将已填入的数字标记到三个数组中，同时收集所有空格坐标。

按顺序对每个空格尝试填入 1~9，若当前数字在对应行、列、宫格均未使用，则填入并递归处理下一个空格。

若递归返回失败，则回溯：撤销填入，继续尝试下一个数字。

当所有空格都被合法填满时，递归返回 true，终止搜索。

复杂度分析：

时间复杂度：O(9^m)，其中 m 表示棋盘中空格数量，最坏情况下每个空格尝试 9 个数字

空间复杂度：O(1)，棋盘大小固定为 9×9，布尔数组均为常数大小

class Solution {

    // 记录每行数字使用情况
    private boolean[][] rowUsed = new boolean[9][10];
    // 记录每列数字使用情况
    private boolean[][] colUsed = new boolean[9][10];
    // 记录每个 3×3 宫格数字使用情况
    private boolean[][] boxUsed = new boolean[9][10];
    // 存储所有空格坐标
    private List<int[]> blanks = new ArrayList<>();

    public void solveSudoku(char[][] board) {
        // 初始化：遍历棋盘，标记已有数字，收集空格位置
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    blanks.add(new int[]{i, j});
                } else {
                    int d = board[i][j] - '0';
                    int b = (i / 3) * 3 + j / 3;
                    rowUsed[i][d] = true;
                    colUsed[j][d] = true;
                    boxUsed[b][d] = true;
                }
            }
        }
        backtrack(board, 0);
    }

    private boolean backtrack(char[][] board, int index) {
        // 所有空格填完，返回成功
        if (index == blanks.size()) {
            return true;
        }
        int[] pos = blanks.get(index);
        int i = pos[0], j = pos[1];
        int b = (i / 3) * 3 + j / 3;

        // 尝试填入 1~9
        for (int d = 1; d <= 9; d++) {
            // 判断当前数字在行、列、宫格是否合法
            if (!rowUsed[i][d] && !colUsed[j][d] && !boxUsed[b][d]) {
                board[i][j] = (char) ('0' + d);
                rowUsed[i][d] = true;
                colUsed[j][d] = true;
                boxUsed[b][d] = true;

                if (backtrack(board, index + 1)) {
                    return true;
                }

                // 回溯：撤销填入
                board[i][j] = '.';
                rowUsed[i][d] = false;
                colUsed[j][d] = false;
                boxUsed[b][d] = false;
            }
        }
        return false;
    }
}

func solveSudoku(board [][]byte) {
    // 记录每行、每列、每个 3×3 宫格中数字使用情况
    var rowUsed, colUsed, boxUsed [9][10]bool
    var blanks [][2]int

    // 初始化：标记已有数字，收集空格坐标
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if board[i][j] == '.' {
                blanks = append(blanks, [2]int{i, j})
            } else {
                d := int(board[i][j] - '0')
                b := (i/3)*3 + j/3
                rowUsed[i][d] = true
                colUsed[j][d] = true
                boxUsed[b][d] = true
            }
        }
    }

    backtrack(board, blanks, &rowUsed, &colUsed, &boxUsed, 0)
}

func backtrack(board [][]byte, blanks [][2]int,
    rowUsed, colUsed, boxUsed *[9][10]bool, index int) bool {
    // 所有空格填完，返回成功
    if index == len(blanks) {
        return true
    }
    i, j := blanks[index][0], blanks[index][1]
    b := (i/3)*3 + j/3

    // 尝试填入 1~9
    for d := 1; d <= 9; d++ {
        // 判断当前数字在行、列、宫格是否合法
        if !rowUsed[i][d] && !colUsed[j][d] && !boxUsed[b][d] {
            board[i][j] = byte('0' + d)
            rowUsed[i][d] = true
            colUsed[j][d] = true
            boxUsed[b][d] = true

            if backtrack(board, blanks, rowUsed, colUsed, boxUsed, index+1) {
                return true
            }

            // 回溯：撤销填入
            board[i][j] = '.'
            rowUsed[i][d] = false
            colUsed[j][d] = false
            boxUsed[b][d] = false
        }
    }
    return false
}

解法二：朴素回溯

核心思路：

不使用辅助数组，直接每次通过遍历棋盘来判断某个数字在当前行、列、宫格中是否合法。

找到第一个空格后，尝试填入 1~9，每次填入前都执行合法性校验，合法则递归处理下一个空格。

相比解法一，校验代价更高（每次 O(9)），但代码更简洁直观。

复杂度分析：

时间复杂度：O(9^m × 9)，其中 m 表示空格数量，每次合法性校验需要 O(9) 扫描

空间复杂度：O(m)，其中 m 为空格数量，递归调用栈深度

class Solution {

    public void solveSudoku(char[][] board) {
        backtrack(board);
    }

    private boolean backtrack(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    continue;
                }
                // 对当前空格尝试填入 1~9
                for (char c = '1'; c <= '9'; c++) {
                    if (isValid(board, i, j, c)) {
                        board[i][j] = c;
                        if (backtrack(board)) {
                            return true;
                        }
                        // 回溯
                        board[i][j] = '.';
                    }
                }
                // 当前空格所有数字均不合法，返回失败
                return false;
            }
        }
        return true;
    }

    private boolean isValid(char[][] board, int row, int col, char c) {
        for (int k = 0; k < 9; k++) {
            // 检查行
            if (board[row][k] == c) {
                return false;
            }
            // 检查列
            if (board[k][col] == c) {
                return false;
            }
            // 检查 3×3 宫格
            int boxRow = (row / 3) * 3 + k / 3;
            int boxCol = (col / 3) * 3 + k % 3;
            if (board[boxRow][boxCol] == c) {
                return false;
            }
        }
        return true;
    }
}

func solveSudoku(board [][]byte) {
    backtrack(board)
}

func backtrack(board [][]byte) bool {
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if board[i][j] != '.' {
                continue
            }
            // 对当前空格尝试填入 '1'~'9'
            for c := byte('1'); c <= '9'; c++ {
                if isValid(board, i, j, c) {
                    board[i][j] = c
                    if backtrack(board) {
                        return true
                    }
                    // 回溯
                    board[i][j] = '.'
                }
            }
            // 当前空格所有数字均不合法，返回失败
            return false
        }
    }
    return true
}

func isValid(board [][]byte, row, col int, c byte) bool {
    for k := 0; k < 9; k++ {
        // 检查行
        if board[row][k] == c {
            return false
        }
        // 检查列
        if board[k][col] == c {
            return false
        }
        // 检查 3×3 宫格
        boxRow := (row/3)*3 + k/3
        boxCol := (col/3)*3 + k%3
        if board[boxRow][boxCol] == c {
            return false
        }
    }
    return true
}

相似题目

题目	难度	考察点
51. N 皇后	困难	回溯、约束检验
52. N 皇后 II	困难	回溯、计数
36. 有效的数独	中等	哈希表、矩阵
79. 单词搜索	中等	回溯、DFS
212. 单词搜索 II	困难	回溯、字典树
22. 括号生成	中等	回溯、字符串
17. 电话号码的字母组合	中等	回溯、哈希表

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/33258688