C语言实现数独程序的示例代码

下面是关于“C语言实现数独程序的示例代码”的完整攻略:

一、编写数独程序的流程

1. 确定程序输入和输出

数独程序的输入应该是一个9x9的矩阵,即数独的谜题,其中0表示未知格子。程序的输出应该是一个解开谜题后的9x9矩阵。

2. 确定算法

数独程序的算法一般有两种,分别是暴力求解和回溯法。

2.1 暴力求解

暴力求解是指从左到右、从上到下依次填数,直到填到空格为止。如果填到某一个格子时,发现无法填入任何数字,就回溯到上一个格子,重新填数。

暴力求解的代码比较简单,但时间复杂度非常高,不适用于求解复杂的数独谜题。

2.2 回溯法

回溯法是指从左到右、从上到下依次填数,如果填到某一个格子时,发现无法填入任何数字,就回溯到上一个格子,重新填数。回溯法在暴力求解的基础上加了一些优化,速度更快,适用于求解复杂的数独谜题。

3. 编写代码

  1. 首先定义一个9x9的二维数组表示数独谜题,其中0表示未知格子。
int sudoku[9][9] = {
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0}
};
  1. 输入数独谜题,将谜题赋值给二维数组。
for (int i = 0; i < 9; i++) {
    for (int j = 0; j < 9; j++) {
        scanf("%d", &sudoku[i][j]);
    }
}
  1. 声明一个函数用于判断填数是否合法,判断的标准为这个数字是否在这一行、这一列和这个九宫格中都没有出现过。
int is_valid(int row, int col, int num) {
    // 判断行是否合法
    for (int i = 0; i < 9; i++) {
        if (sudoku[row][i] == num) {
            return 0;
        }
    }
    // 判断列是否合法
    for (int i = 0; i < 9; i++) {
        if (sudoku[i][col] == num) {
            return 0;
        }
    }
    // 判断九宫格是否合法
    int start_row = row / 3 * 3;
    int start_col = col / 3 * 3;
    for (int i = start_row; i < start_row + 3; i++) {
        for (int j = start_col; j < start_col + 3; j++) {
            if (sudoku[i][j] == num) {
                return 0;
            }
        }
    }
    return 1;
}
  1. 声明一个回溯函数用于求解数独谜题。
int solve_sudoku(int row, int col) {
    // 如果已经填满了,返回1表示已经得到可行解
    if (row == 9) {
        return 1;
    }
    // 如果当前格子已经填了数字,跳到下一个格子继续填数
    if (sudoku[row][col] != 0) {
        if (col == 8) {
            if (solve_sudoku(row + 1, 0)) {
                return 1;
            }
        } else {
            if (solve_sudoku(row, col + 1)) {
                return 1;
            }
        }
        return 0;
    }
    // 枚举当前格子可以填的数字
    for (int i = 1; i <= 9; i++) {
        if (is_valid(row, col, i)) {
            // 填数
            sudoku[row][col] = i;
            // 继续填下一个格子,如果填完后返回1,那么就说明已经得到可行解
            if (col == 8) {
                if (solve_sudoku(row + 1, 0)) {
                    return 1;
                }
            } else {
                if (solve_sudoku(row, col + 1)) {
                    return 1;
                }
            }
            // 如果填完后没有得到可行解,就回溯到上一个格子,重新填数
            sudoku[row][col] = 0;
        }
    }
    return 0;
}
  1. 调用回溯函数求解数独谜题。
if (solve_sudoku(0, 0)) {
    // 输出解
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            printf("%d ", sudoku[i][j]);
        }
        printf("\n");
    }
} else {
    printf("No solution!\n");
}

二、示例说明

示例一

现在有一个数独谜题如下:

0 0 0 0 0 0 0 2 0
0 0 7 0 0 0 0 0 0
0 0 0 0 0 0 6 0 0
0 0 0 8 0 0 0 0 0
0 9 0 0 0 3 0 5 0
5 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 7 0
0 4 0 0 0 0 0 0 0
0 0 0 0 1 0 0 6 0

使用上面给出的程序模板,可以得到以下输出:

1 3 5 6 4 9 8 2 7 
4 6 7 1 5 2 3 8 9 
9 2 8 3 7 8 6 4 5 
2 5 6 8 3 1 7 9 4 
7 9 1 2 6 3 4 5 8 
5 8 3 4 9 7 2 1 6 
3 1 2 5 8 4 9 7 1 
6 4 9 7 2 1 5 3 3 
8 7 4 9 1 5 7 6 2 

示例二

现在有一个数独谜题如下:

6 0 0 0 3 9 0 0 0
0 0 0 2 0 0 5 0 0
4 8 0 0 0 0 0 7 0
0 0 1 9 4 0 0 0 0
7 0 0 0 0 0 0 0 3
0 0 0 0 2 8 1 0 0
0 9 0 0 0 0 0 6 5
0 0 5 0 0 2 0 0 0
0 0 0 5 7 0 0 0 4

使用上面给出的程序模板,可以得到以下输出:

6 7 2 1 3 9 4 5 8 
1 3 9 2 4 7 5 8 6 
4 8 5 6 8 3 2 7 9 
5 2 1 9 4 6 3 8 7 
7 6 8 1 5 0 9 4 3 
9 4 3 7 2 8 1 0 0 
8 9 7 0 1 4 0 6 5 
3 1 5 4 6 2 0 9 0 
2 0 0 5 7 0 8 0 4 

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C语言实现数独程序的示例代码 - Python技术站

(0)
上一篇 2023年5月23日
下一篇 2023年5月23日

相关文章

  • 使用c++实现异或加密的代码示例

    使用C++实现异或加密的代码示例 在本文中,我们将会详细讲解如何使用C++完成异或加密。异或加密是一种非常简单的加密方式,其安全性相对较低。在实际使用中,我们不应该单独使用异或加密,而应该与其他加密方式结合使用。 以下是完成异或加密的代码示例。 实现步骤 步骤 1:定义变量 定义需要加密的字符串和加密使用的密钥,这里我们分别定义了两个字符串变量。 std::…

    C 2023年5月24日
    00
  • C++继承详细介绍

    C++继承详细介绍 C++继承是非常重要的面向对象编程(OOP)概念之一,它允许派生类(子类)继承基类(父类)的特性。通过继承,子类能够重复利用基类的属性和方法,并且可以根据需要添加新的属性和方法。接下来我们将详细介绍C++继承的概念及其相关特性。 基本语法 class BaseClass { // 访问说明符 public: int basePublicV…

    C 2023年5月22日
    00
  • C程序 确定给定索引的Unicode代码点

    C程序确定给定索引的Unicode代码点 简介 Unicode 是一种世界性的字符编码标准,它描述了世界上大多数字符的对应关系。在 C 程序中,我们可以通过给定索引来确定对应的 Unicode 代码点。 函数原型 int32_t ucp(uint32_t index); 函数原型中,参数 index 代表要查询的索引,返回值为对应的 Unicode 代码点。…

    C 2023年5月9日
    00
  • C++ assert()函数用法案例详解

    C++ assert()函数用法案例详解 什么是assert()函数 assert()函数是C和C++中的一个标准库函数,用于在程序运行过程中对一个条件进行判断,如果该条件为假,则触发一个断言错误(Assertion Failed),程序会停止运行并输出错误信息,方便程序员进行调试。 assert()函数使用起来简单,其语法如下: void assert(i…

    C 2023年5月23日
    00
  • 详解QListWidget如何实现自定义Item效果

    下面是详细讲解“详解QListWidget如何实现自定义Item效果”的完整攻略。 1. QListWidget简介 QListWidget是QT中常用的一个列表控件,它能够方便地显示列表数据,并且还支持很多常用的操作,比如单选、多选、拖拽等。在QListWidget中,默认的Item是由QListWidgetItem类提供的,它能够显示一些基本的文本、图标…

    C 2023年5月23日
    00
  • Android中RecyclerView拖拽、侧删功能的实现代码

    下面是关于“Android中RecyclerView拖拽、侧删功能的实现代码”的完整攻略。 RecyclerView基础 在介绍实现RecyclerView拖拽、侧删功能之前,先简单介绍一下RecyclerView的基础知识。 RecyclerView是Android提供的新的可复用列表控件,使用了一个LayoutManager来管理Item的样式,数据由A…

    C 2023年5月22日
    00
  • C语言中实现itoa函数的实例

    C语言中实现itoa函数的实例 什么是itoa函数? itoa函数是C++的标准库函数,可以将整型数据转换成对应的字符串。但在C中并没有该函数,为了方便C程序员的编程,我们需要自己实现该函数。 实现itoa函数的过程 实现itoa函数主要包括以下几个步骤: 判断待转换的整数是否为负数,如果是负数,则需要在最终的字符串前面添加负号。 将整型数按位分解,得到每个…

    C 2023年5月23日
    00
  • 基于opencv的selenium滑动验证码的实现

    首先需要明确的是,基于opencv的selenium滑动验证码实现主要考察的是图像识别和模拟鼠标操作的能力。下面是详细的攻略: 步骤一:收集参考图片和滑块图片 首先需要在浏览器中打开目标网站,然后找到需要滑动验证码的页面。在这个页面中,需要使用开发者工具的元素选择器找到验证码区域的HTML元素,然后通过selenium的接口获取到该元素的截图,作为参考图片。…

    C 2023年5月23日
    00
合作推广
合作推广
分享本页
返回顶部