数独

[编程题]数独

热度指数：11751 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

请编写一个程序，给数独中的剩余的空格填写上数字

空格用字符'.'表示

假设给定的数独只有唯一的解法

这盘数独的解法是：

红色表示填上的解

示例1

输入

[[.,.,9,7,4,8,.,.,.],[7,.,.,.,.,.,.,.,.],[.,2,.,1,.,9,.,.,.],[.,.,7,.,.,.,2,4,.],[.,6,4,.,1,.,5,9,.],[.,9,8,.,.,.,3,.,.],[.,.,.,8,.,3,.,2,.],[.,.,.,.,.,.,.,.,6],[.,.,.,2,7,5,9,.,.]]

输出

[[5,1,9,7,4,8,6,3,2],[7,8,3,6,5,2,4,1,9],[4,2,6,1,3,9,8,7,5],[3,5,7,9,8,6,2,4,1],[2,6,4,3,1,7,5,9,8],[1,9,8,5,2,4,3,6,7],[9,7,5,8,6,3,1,2,4],[8,3,2,4,9,1,7,5,6],[6,4,1,2,7,5,9,8,3]]

算法知识视频讲解

轻妙淡写一纸碎月

include #include bool isValid(char** board

#include <stdbool.h>
#include <stdio.h>

bool isValid(char** board, int row, int col, char c) {
    for (int i = 0; i < 9; i++) {
        // 检查行、列
        if (board[row][i] == c) return false;
        if (board[i][col] == c) return false;
        // 检查3x3小方格
        int boxRow = 3 * (row / 3) + i / 3;
        int boxCol = 3 * (col / 3) + i % 3;
        if (board[boxRow][boxCol] == c) return false;
    }
    return true;
}

bool dfs(char** board) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == '.' || board[i][j] == '0') {
                for (char c = '1'; c <= '9'; c++) {
                    if (isValid(board, i, j, c)) {
                        board[i][j] = c;
                        if (dfs(board)) return true;
                        board[i][j] = '.';
                    }
                }
                return false; // 9个都不行，回溯
            }
        }
    }
    return true; // 填满了
}

void solveSudoku(char** board, int boardRowLen, int* boardColLen) {
    dfs(board);
}

, int row, int col, char c) { for (int i = 0; i

发表于 2025-08-29 11:42:25 回复(0)