C语言如何判断数独是否正确

创作时间:

作者:

@小白创作中心

C语言如何判断数独是否正确

引用

来源

https://docs.pingcode.com/baike/1048069

本文将详细介绍如何使用C语言判断数独是否正确。通过行、列和子宫检查数独的正确性、使用哈希表或布尔数组进行验证、有效率和减少代码复杂度。其中，使用哈希表或布尔数组进行验证是实现数独校验的有效方法。哈希表或布尔数组可以帮助我们快速确定某个数字是否已经出现在当前行、列或子宫中，从而提高代码的可读性和执行效率。

一、数独简介和问题分析

数独是一种逻辑谜题，玩家需要根据9×9的网格和给定的数字，填入1到9，使得每一行、每一列和每一个3×3的子宫中都包含1到9的所有数字且没有重复。判断数独是否正确，就是确保数独中所有行、列和子宫都满足上述条件。

数独的基本规则

行规则：每一行必须包含数字1到9，没有重复。
列规则：每一列必须包含数字1到9，没有重复。
子宫规则：每一个3×3的子宫必须包含数字1到9，没有重复。

问题分析

为了判断数独是否正确，我们需要对数独的每一行、每一列和每一个3×3子宫进行检查。我们可以采用以下步骤：

行检查：遍历每一行，检查是否包含重复的数字。
列检查：遍历每一列，检查是否包含重复的数字。
子宫检查：遍历每一个3×3子宫，检查是否包含重复的数字。

二、使用哈希表进行数独校验

哈希表的概念

哈希表是一种数据结构，它通过键值对的方式存储数据，能够在常数时间复杂度内进行插入和查找操作。对于数独校验，我们可以使用一个布尔数组来模拟哈希表，从而快速判断某个数字是否已经出现。

实现步骤

初始化布尔数组：创建三个布尔数组，分别用于行、列和子宫的检查。
遍历数独网格：遍历整个数独网格，对于每一个数字，更新布尔数组。
检查重复：在更新布尔数组的同时，检查是否存在重复的数字。

代码实现

#include <stdio.h>
#include <stdbool.h>
#define N 9

bool isValidSudoku(int grid[N][N]) {
    bool rows[N][N] = {false};
    bool cols[N][N] = {false};
    bool boxes[N][N] = {false};

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (grid[i][j] != 0) {
                int num = grid[i][j] - 1;
                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() {
    int sudoku[N][N] = {
        {5, 3, 0, 0, 7, 0, 0, 0, 0},
        {6, 0, 0, 1, 9, 5, 0, 0, 0},
        {0, 9, 8, 0, 0, 0, 0, 6, 0},
        {8, 0, 0, 0, 6, 0, 0, 0, 3},
        {4, 0, 0, 8, 0, 3, 0, 0, 1},
        {7, 0, 0, 0, 2, 0, 0, 0, 6},
        {0, 6, 0, 0, 0, 0, 2, 8, 0},
        {0, 0, 0, 4, 1, 9, 0, 0, 5},
        {0, 0, 0, 0, 8, 0, 0, 7, 9}
    };

    if (isValidSudoku(sudoku)) {
        printf("The Sudoku is valid.\n");
    } else {
        printf("The Sudoku is invalid.\n");
    }
    return 0;
}

三、使用布尔数组进行优化

优化思路

使用布尔数组进行优化的核心思想是减少重复检查，提高代码的执行效率。我们可以在一次遍历中同时检查行、列和子宫，从而减少代码的复杂度。

优化步骤

创建布尔数组：创建三个布尔数组，分别用于行、列和子宫的检查。
一次遍历检查：在一次遍历中，同时更新三个布尔数组。
提前终止：在发现重复数字时，提前终止检查，返回结果。

代码优化

#include <stdio.h>
#include <stdbool.h>
#define N 9

bool isValidSudokuOptimized(int grid[N][N]) {
    bool rows[N][N] = {false};
    bool cols[N][N] = {false};
    bool boxes[N][N] = {false};

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (grid[i][j] != 0) {
                int num = grid[i][j] - 1;
                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() {
    int sudoku[N][N] = {
        {5, 3, 0, 0, 7, 0, 0, 0, 0},
        {6, 0, 0, 1, 9, 5, 0, 0, 0},
        {0, 9, 8, 0, 0, 0, 0, 6, 0},
        {8, 0, 0, 0, 6, 0, 0, 0, 3},
        {4, 0, 0, 8, 0, 3, 0, 0, 1},
        {7, 0, 0, 0, 2, 0, 0, 0, 6},
        {0, 6, 0, 0, 0, 0, 2, 8, 0},
        {0, 0, 0, 4, 1, 9, 0, 0, 5},
        {0, 0, 0, 0, 8, 0, 0, 7, 9}
    };

    if (isValidSudokuOptimized(sudoku)) {
        printf("The Sudoku is valid.\n");
    } else {
        printf("The Sudoku is invalid.\n");
    }
    return 0;
}