有效的数独（C语言解法）

力扣第36题：有效的数独（C语言解法）

题目描述

判断一个 9x9 的数独是否有效。只需要根据以下规则验证：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 子数独中只能出现一次。

注意：

• 数独部分空白的格子用 '.' 表示。
• 一个有效的数独（部分填充）不一定是可解的。
• 数组中的字符只能是 1-9 和 '.'。

示例：

输入:
[
  ["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"]
]
输出: true

解题思路

我们可以用三个布尔二维数组来记录数字是否在行、列或 3x3 子方块中出现过：

1. rows[9][9]：记录每行是否出现过某个数字。
2. cols[9][9]：记录每列是否出现过某个数字。
3. boxes[9][9]：记录每个 3x3 子方块是否出现过某个数字。

对于每个数字，确定它属于哪个 3x3 子方块可以通过以下公式：

• 子方块索引为 (i / 3) * 3 + j / 3，其中 i 是行索引，j 是列索引。

如果在遍历过程中，某个数字已经出现在对应的行、列或子方块中，则说明数独无效，返回 false。否则，将该数字标记为已出现。

C语言代码实现

#include <stdbool.h>

bool isValidSudoku(char board[9][9]) {
    bool rows[9][9] = {false};
    bool cols[9][9] = {false};
    bool boxes[9][9] = {false};
    
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] != '.') {
                int num = board[i][j] - '1';  // 将字符数字转为0-8的整数
                int boxIndex = (i / 3) * 3 + j / 3;
                
                // 检查是否在行、列或子方块中已出现过
                if (rows[i][num] || cols[j][num] || boxes[boxIndex][num]) {
                    return false;  // 若已出现则无效
                }
                
                // 标记行、列和子方块中该数字已出现
                rows[i][num] = true;
                cols[j][num] = true;
                boxes[boxIndex][num] = true;
            }
        }
    }
    return true;
}

int main() {
    char board[9][9] = {
        {'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'}
    };
    
    if (isValidSudoku(board)) {
        printf("有效的数独\n");
    } else {
        printf("无效的数独\n");
    }
    
    return 0;
}

代码解析

1. 初始化布尔数组

定义 rows[9][9]、cols[9][9] 和 boxes[9][9] 三个二维布尔数组，用于标记数独的每一行、每一列和每个 3x3 子方块中数字 1-9 是否已经出现。

bool rows[9][9] = {false};
bool cols[9][9] = {false};
bool boxes[9][9] = {false};

2. 遍历数独表格

使用双重循环遍历每一个格子，i 表示行，j 表示列。

for (int i = 0; i < 9; i++) {
    for (int j = 0; j < 9; j++) {
        ...
    }
}

3. 跳过空格

如果 board[i][j] 是 '.'，说明当前格子为空，直接跳过。

if (board[i][j] != '.') {
    ...
}

4. 计算数字和 3x3 子方块索引

将当前字符数字 board[i][j] 转换为整数索引 num，并计算其所在的 3x3 子方块索引 boxIndex。

int num = board[i][j] - '1';  // 将字符数字转为0-8的整数
int boxIndex = (i / 3) * 3 + j / 3;

5. 检查是否有重复

检查 rows[i][num]、cols[j][num] 和 boxes[boxIndex][num] 是否已经为 true，若为 true，则返回 false，表示数独无效。

if (rows[i][num] || cols[j][num] || boxes[boxIndex][num]) {
    return false;
}

6. 标记已出现

如果未重复，将 rows[i][num]、cols[j][num] 和 boxes[boxIndex][num] 标记为 true，表示该数字已在当前行、列或 3x3 子方块中出现。

rows[i][num] = true;
cols[j][num] = true;
boxes[boxIndex][num] = true;

7. 返回结果

遍历结束后，如果没有发现冲突，则返回 true。

时间复杂度

由于数独表格大小固定为 $9\times 9$，即 81 个格子，因此算法时间复杂度为$O(1)$，对每个格子判断只需常数时间。