Hard

题目描述

编写一个程序来解决数独谜题，通过填充空白单元格。

数独解决方案必须满足以下所有规则：

  • 数字 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] 是一位数字或者 '.'
  • 题目数据 保证 输入数独仅有一个解

解题思路

数独求解是经典的回溯算法问题，核心思路是尝试填充每个空格，如果发现无法继续则回退重新尝试。

解题思路：

  1. 回溯法：对于每个空格(’.’) ，依次尝试放入数字1-9，如果当前数字满足数独规则，则继续递归求解剩余格子；如果无法继续，则回退到上一步重新尝试其他数字。

  2. 有效性检查：需要检查三个条件：

    • 当前行是否已存在该数字
    • 当前列是否已存在该数字
    • 当前3×3宫格是否已存在该数字

  3. 优化策略：

    • 预处理优化：使用哈希表记录每行、每列、每个宫格已使用的数字，避免重复遍历
    • 选择策略优化：优先填充候选数字较少的格子，减少搜索空间
    • 位运算优化：使用位运算快速判断数字是否可用

推荐解法：使用预处理+回溯的方法，时间复杂度较优且代码清晰易懂。

代码实现

class Solution {
public:
    vector<vector<bool>> rows, cols, boxes;
    
    void solveSudoku(vector<vector<char>>& board) {
        rows = vector<vector<bool>>(9, vector<bool>(10, false));
        cols = vector<vector<bool>>(9, vector<bool>(10, false));
        boxes = vector<vector<bool>>(9, vector<bool>(10, false));
        
        // 预处理：记录已填数字
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    rows[i][num] = true;
                    cols[j][num] = true;
                    boxes[i / 3 * 3 + j / 3][num] = true;
                }
            }
        }
        
        backtrack(board, 0, 0);
    }
    
    bool backtrack(vector<vector<char>>& board, int row, int col) {
        if (row == 9) return true; // 填完所有格子
        
        int nextRow = (col == 8) ? row + 1 : row;
        int nextCol = (col == 8) ? 0 : col + 1;
        
        if (board[row][col] != '.') {
            return backtrack(board, nextRow, nextCol);
        }
        
        for (int num = 1; num <= 9; num++) {
            int boxIndex = row / 3 * 3 + col / 3;
            if (!rows[row][num] && !cols[col][num] && !boxes[boxIndex][num]) {
                board[row][col] = '0' + num;
                rows[row][num] = true;
                cols[col][num] = true;
                boxes[boxIndex][num] = true;
                
                if (backtrack(board, nextRow, nextCol)) {
                    return true;
                }
                
                // 回溯
                board[row][col] = '.';
                rows[row][num] = false;
                cols[col][num] = false;
                boxes[boxIndex][num] = false;
            }
        }
        
        return false;
    }
};

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]
        
        # 预处理：记录已填数字
        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    num = board[i][j]
                    rows[i].add(num)
                    cols[j].add(num)
                    boxes[i // 3 * 3 + j // 3].add(num)
        
        def backtrack(row, col):
            if row == 9:
                return True
            
            next_row = row + 1 if col == 8 else row
            next_col = 0 if col == 8 else col + 1
            
            if board[row][col] != '.':
                return backtrack(next_row, next_col)
            
            for num in '123456789':
                box_index = row // 3 * 3 + col // 3
                if num not in rows[row] and num not in cols[col] and num not in boxes[box_index]:
                    board[row][col] = num
                    rows[row].add(num)
                    cols[col].add(num)
                    boxes[box_index].add(num)
                    
                    if backtrack(next_row, next_col):
                        return True
                    
                    # 回溯
                    board[row][col] = '.'
                    rows[row].remove(num)
                    cols[col].remove(num)
                    boxes[box_index].remove(num)
            
            return False
        
        backtrack(0, 0)

public class Solution {
    private bool[][] rows, cols, boxes;
    
    public void SolveSudoku(char[][] board) {
        rows = new bool[9][];
        cols = new bool[9][];
        boxes = new bool[9][];
        
        for (int i = 0; i < 9; i++) {
            rows[i] = new bool[10];
            cols[i] = new bool[10];
            boxes[i] = new bool[10];
        }
        
        // 预处理：记录已填数字
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    rows[i][num] = true;
                    cols[j][num] = true;
                    boxes[i / 3 * 3 + j / 3][num] = true;
                }
            }
        }
        
        Backtrack(board, 0, 0);
    }
    
    private bool Backtrack(char[][] board, int row, int col) {
        if (row == 9) return true;
        
        int nextRow = col == 8 ? row + 1 : row;
        int nextCol = col == 8 ? 0 : col + 1;
        
        if (board[row][col] != '.') {
            return Backtrack(board, nextRow, nextCol);
        }
        
        for (int num = 1; num <= 9; num++) {
            int boxIndex = row / 3 * 3 + col / 3;
            if (!rows[row][num] && !cols[col][num] && !boxes[boxIndex][num]) {
                board[row][col] = (char)('0' + num);
                rows[row][num] = true;
                cols[col][num] = true;
                boxes[boxIndex][num] = true;
                
                if (Backtrack(board, nextRow, nextCol)) {
                    return true;
                }
                
                // 回溯
                board[row][col] = '.';
                rows[row][num] = false;
                cols[col][num] = false;
                boxes[boxIndex][num] = false;
            }
        }
        
        return false;
    }
}

var solveSudoku = function(board) {
    function isValid(board, row, col, num) {
        for (let i = 0; i < 9; i++) {
            if (board[row][i] === num || board[i][col] === num) {
                return false;
            }
        }
        
        const boxRow = Math.floor(row / 3) * 3;
        const boxCol = Math.floor(col / 3) * 3;
        for (let i = boxRow; i < boxRow + 3; i++) {
            for (let j = boxCol; j < boxCol + 3; j++) {
                if (board[i][j] === num) {
                    return false;
                }
            }
        }
        
        return true;
    }
    
    function solve() {
        for (let row = 0; row < 9; row++) {
            for (let col = 0; col < 9; col++) {
                if (board[row][col] === '.') {
                    for (let num = '1'; num <= '9'; num++) {
                        if (isValid(board, row, col, num)) {
                            board[row][col] = num;
                            if (solve()) {
                                return true;
                            }
                            board[row][col] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    solve();
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(9^m)，其中m是空格数量，最坏情况下需要尝试每个空格的9种可能
空间复杂度O(1)，使用固定大小的辅助数组，递归深度最多81层

相关题目