题解 | 数独_牛客博客

解题思路

这是一个经典的回溯算法问题。需要通过尝试不同的数字来填充空格，直到找到一个合法的解。

关键点：

使用回溯算法尝试每个空格的可能数字
检查行、列、3x3小方格是否合法
优化搜索策略，提前剪枝
找到解后立即返回

算法步骤：

找到一个空格（值为0的位置）
尝试填入1-9的数字
检查是否合法
递归求解下一个空格
如果无法填入，回溯并尝试其他数字

代码

cpp
java
python

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    bool is_valid(vector<vector<int>>& board, int row, int col, int num) {
        // 检查行
        for (int x = 0; x < 9; x++) {
            if (board[row][x] == num) return false;
        }
        
        // 检查列
        for (int x = 0; x < 9; x++) {
            if (board[x][col] == num) return false;
        }
        
        // 检查3x3方格
        int start_row = 3 * (row / 3);
        int start_col = 3 * (col / 3);
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[start_row + i][start_col + j] == num) {
                    return false;
                }
            }
        }
        
        return true;
    }
    
    bool solve_sudoku(vector<vector<int>>& board) {
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (board[row][col] == 0) {
                    for (int num = 1; num <= 9; num++) {
                        if (is_valid(board, row, col, num)) {
                            board[row][col] = num;
                            if (solve_sudoku(board)) {
                                return true;
                            }
                            board[row][col] = 0;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
public:
    void solve(vector<vector<int>>& board) {
        solve_sudoku(board);
    }
};

int main() {
    vector<vector<int>> board(9, vector<int>(9));
    
    // 读取输入
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> board[i][j];
        }
    }
    
    Solution solution;
    solution.solve(board);
    
    // 输出结果
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cout << board[i][j] << (j == 8 ? "\n" : " ");
        }
    }
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        private int[][] board;
        
        // 检查在指定位置放置数字是否合法
        private boolean isValid(int row, int col, int num) {
            // 检查行
            for (int x = 0; x < 9; x++) {
                if (board[row][x] == num) {
                    return false;
                }
            }
            
            // 检查列
            for (int x = 0; x < 9; x++) {
                if (board[x][col] == num) {
                    return false;
                }
            }
            
            // 检查3x3方格
            int startRow = row - row % 3;
            int startCol = col - col % 3;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (board[i + startRow][j + startCol] == num) {
                        return false;
                    }
                }
            }
            
            return true;
        }
        
        // 使用回溯法解数独
        private boolean solveSudoku() {
            int row = -1;
            int col = -1;
            boolean isEmpty = false;
            
            // 找到一个空位置
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (board[i][j] == 0) {
                        row = i;
                        col = j;
                        isEmpty = true;
                        break;
                    }
                }
                if (isEmpty) {
                    break;
                }
            }
            
            // 如果没有空位置，说明解决完成
            if (!isEmpty) {
                return true;
            }
            
            // 尝试填入1-9
            for (int num = 1; num <= 9; num++) {
                if (isValid(row, col, num)) {
                    board[row][col] = num;
                    if (solveSudoku()) {
                        return true;
                    }
                    board[row][col] = 0;
                }
            }
            
            return false;
        }
        
        public void solve(int[][] sudokuBoard) {
            this.board = sudokuBoard;
            solveSudoku();
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[][] board = new int[9][9];
        
        // 读取输入
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                board[i][j] = sc.nextInt();
            }
        }
        
        Solution solution = new Solution();
        solution.solve(board);
        
        // 输出结果
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(board[i][j]);
                if (j < 8) {
                    System.out.print(" ");
                }
            }
            System.out.println();
        }
        
        sc.close();
    }
}

class Solution:
    def solve(self, board: list) -> bool:
        def is_valid(row: int, col: int, num: int) -> bool:
            # 检查行
            for x in range(9):
                if board[row][x] == num:
                    return False
            
            # 检查列
            for x in range(9):
                if board[x][col] == num:
                    return False
            
            # 检查3x3方格
            start_row, start_col = 3 * (row // 3), 3 * (col // 3)
            for i in range(3):
                for j in range(3):
                    if board[start_row + i][start_col + j] == num:
                        return False
            
            return True
        
        def solve_sudoku() -> bool:
            # 找到一个空格
            for row in range(9):
                for col in range(9):
                    if board[row][col] == 0:
                        # 尝试填入1-9
                        for num in range(1, 10):
                            if is_valid(row, col, num):
                                board[row][col] = num
                                if solve_sudoku():
                                    return True
                                board[row][col] = 0
                        return False
            return True
        
        solve_sudoku()
        return board

# 读取输入
board = []
for _ in range(9):
    row = list(map(int, input().split()))
    board.append(row)

solution = Solution()
result = solution.solve(board)

# 输出结果
for row in result:
    print(' '.join(map(str, row)))

算法及复杂度

时间复杂度

最坏情况： $O(9^{81})$ ，需要尝试每个格子的所有可能
实际情况：由于剪枝和约束传播，运行时间远小于理论上限

空间复杂度

递归深度最大为81： $O(81)$ = $O(1)$
总空间复杂度： $O(1)$

优化策略

优先填充约束最多的格子
使用位运算优化状态检查
使用数组预存储每行、列、方格的可用数字
使用Dancing Links算法（精确覆盖问题）