解题思路

这是一个数独求解问题。使用回溯法，对每个空格位置尝试填入1-9的数字，直到找到一个合法解。

关键点：

  1. 判断数字在行、列、方格中是否合法
  2. 使用回溯法尝试填充空格
  3. 找到一个解即可返回
  4. 使用二维数组存储数独

算法步骤：

  1. 读入数独矩阵
  2. 找到空格位置
  3. 尝试填入数字
  4. 验证解的合法性

代码

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

class Solution {
private:
    bool isValid(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 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;
    }
    
    bool solve(vector<vector<int>>& board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == 0) {
                    for (int num = 1; num <= 9; num++) {
                        if (isValid(board, i, j, num)) {
                            board[i][j] = num;
                            if (solve(board)) return true;
                            board[i][j] = 0;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
public:
    void solveSudoku(vector<vector<int>>& board) {
        solve(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.solveSudoku(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 boolean isValid(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 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 solve(int[][] board) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (board[i][j] == 0) {
                        for (int num = 1; num <= 9; num++) {
                            if (isValid(board, i, j, num)) {
                                board[i][j] = num;
                                if (solve(board)) return true;
                                board[i][j] = 0;
                            }
                        }
                        return false;
                    }
                }
            }
            return true;
        }
        
        public void solveSudoku(int[][] board) {
            solve(board);
        }
    }
    
    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.solveSudoku(board);
        
        // 输出结果
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(board[i][j] + (j == 8 ? "\n" : " "));
            }
        }
        
        sc.close();
    }
}

class Solution:
    def solve_sudoku(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 = row - row % 3
            start_col = col - col % 3
            for i in range(3):
                for j in range(3):
                    if board[i + start_row][j + start_col] == num:
                        return False
            
            return True
        
        def solve() -> bool:
            # 找到一个空位置
            for i in range(9):
                for j in range(9):
                    if board[i][j] == 0:
                        # 尝试填入1-9
                        for num in range(1, 10):
                            if is_valid(i, j, num):
                                board[i][j] = num
                                if solve():
                                    return True
                                board[i][j] = 0
                        return False
            return True
        
        solve()
        return board

if __name__ == "__main__":
    # 读入数独
    board = []
    for _ in range(9):
        row = list(map(int, input().split()))
        board.append(row)
    
    solution = Solution()
    result = solution.solve_sudoku(board)
    
    # 输出结果
    for row in result:
        print(' '.join(map(str, row)))

算法及复杂度

  • 算法：回溯法
  • 时间复杂度：，其中 是空格数量
  • 空间复杂度：，使用固定大小的数组