个人项目之数独的生成与数独残局求解——C语言实现
2024-09-24 14:09:39
1、对项目的分析与初步计划:
- 起初拿到这个项目是非常懵逼的,因为涉及到很多个人的知识盲区,诸如:C语言文件的操作、命令行参数、Code Quality Analysis工具、性能分析工具Studio Profiling Tools、GitHub……。可以说在这之前根本就没有接触过这些东西。
- 虽然什么都不会,但不能什么都不做,于是我制定了以下计划:
- 什么都不管,先写好代码再说。
- 翻开《C 程序设计(第四版) 谭浩强》学习C文件的基本操作。
- 百度了解命令行参数。
- 其他的太缥缈了,走一步看一步啦。
2、具体实现过程:
- 根据项目要求,我把代码分成“生成数独终局”和“求解数独残局”两部分。
Creat_ShuDu(argv[]);//生成数独终局
Solve_shuDu(argv[]);//求解数独残局
- 生成数独终局:
- 对于这一部分,我先生成了一个叫“First line.txt”的文本文件。这个文件用来存储所有可能的数独第一排数据,当需要生成数独终局时,就从这个文件里挑一组数据出来完成数独第一行。(写完这句话我才发现我这不是多此一举吗?!根本没必要啊!)
- 如何生成一个完成的数独终局,这是一个问题。百度上给了多种方法,考虑到自己的能力,最终选择了暴力回溯法。
- 对于数独中的每一个小格,它只能填写1~9这9个数字,并且每两个小格间都存在着一定的联系,这给我们的回溯提供了依据。
- 项目要求生成足够的数独数目。一次性生成多个数独,我可以先写只生成一个数独终局的代码。
- 从某一小格的某一种可能出发, 搜索从这种情况出发所能达到的所有可能, 当这一条路走到” 尽头 “或者这条路失败的时候, 再倒回到上一步, 从另一个可能出发, 继续搜索. 直到得到足够的终局。
- 求解数独残局:
- 其实写完了“生成数独终局”,再写求解部分是非常简单的,因为他们的主要算法都是回溯。唯一的不同就是求解的时候,有些位置已经有了确定的数字。
3、关键代码说明:
在整个项目代码中最重要的代码当属judge(int i, int j)函数。
int judge(int i, int j) //搜索第( i , j )位置处可以存储的数字,找到解则返回1,否则返回0 { || j > ) ;//搜索结束 ; k <= ; k++) { ; // can 变量用于记录数字k能否放在 ( i , j ) 处 ; m < i; m++) // 检查同一列是否出现过数字k { if (shuDu[m][j] == k) //该列出现过数字k { can = ; break; } } ) { ; n < j; n++) // 检查同一行是否出现过数字k { if (shuDu[i][n] == k) //该行出现过数字k { can = ; break; } } } ) // 检查在3×3的小方格中是否出现了同一个数字 { ) * + ; // (i,j)方格所在的3×3小方格i坐标的上限 ) * + ; // (i,j)方格所在的3×3小方格在j坐标的上限 == ) up1 = i; //这是针对特殊情况的处理 == ) up2 = j; ; p <= up1; p++) /* 检查在3×3的小方格中是否出现了同一个数字 */ { ; q <= up2; q++) { if (shuDu[p][q] == k) { can = ; break; } } } } ) //can==1说明数字k可以放在该位置上 { shuDu[i][j] = k; ) { ) == ) ; /* 到同一行的下一位置开始搜索 */ } else { ) { , ) == ) ; /* 到下一行的第一个空格开始搜索 */ } else { num++; if (num<numbers) { Print_shuDu(num); } else { Print_shuDu(num); ; /* i >= 9 && j >= 9 , 搜索结束 */ } } } shuDu[i][j] = ; /* 关键这一步:找不到解就要回复原状,否则会对下面的搜索造成影响 */ } else continue;//继续尝试其他数字 } ; /* 1到9都尝试过都不行,则返回递归的上一步 */ }
这段代码使用的是典型的回溯法。弄懂了这个函数,再写求解数独残局的函数就变的相当简单了。
4、代码优化:
- 因为我使用的是暴力回溯法,所以能够优化的地方确实不多。我主要优化的是“数独输出函数”。
void Print_shuDu(int n) //数独输出函数
- 起初我通过 fprintf() 函数将数据输出到文件,测试时输出1000000个数独终局需要近2分钟的时间。
- 后来我将这个函数改成 fputc()的输出方式,运行速度大大加快,对于1000000个数独只需 30左右,缩短了近四分之三的时间。
- 对此,我特意百度了一下原因。感兴趣的伙伴可以看看。https://blog.csdn.net/slimfox/article/details/1092709
5、后期各种测试:
- 性能分析如下:
- CPU使用率如下:
6、项目收获:
最大的收获当然是第一次基本独立完成了一个项目,虽然项目很小,做出来的东西很辣鸡。
- 将该文一开始提到的各种知识盲区大致熟悉了一遍,为以后的学习提供了方便。
- get到了一些小东西:
- fputc()比fprintf()快
- 在VS中scanf要写成scanf_s,为了更安全
- 在VS中输入一个字符串应写成 scanf_s("%s",s1,sizeof(s1));
- 在VS中打开一个文件应这样写 fopen_s(&fp, "sudoku.txt", "w");
附:PSP2.1表格
PSP2.1 |
Personal Software Process Stages |
预估耗时(分钟) | 实际耗时(分钟) |
Planning | 计划 | 60 | 120 |
.Estimate | 估计这个任务需要多少时间 | 2000 | 1500 |
Development | 开发 | 200 | 300 |
.Analysis | 需求分析(包括学习新技术) | 30 | 60 |
.Design Spec | 生成设计文档 | 60 | 40 |
.Design Review | 设计复审(和同事审核设计文档) | 60 | 30 |
.Coding Standard | 代码规范(为目前的开发指定合适的规范) | 120 | 100 |
.Design | 具体设计 | 60 | 60 |
.Coding | 具体编码 | 200 | 300 |
.00Coed Review | 代码复审 | 30 | 60 |
.Test | 测试(自我测试,修改代码,提交修改) | 60 | 180 |
Reporting | 报告 | 60 | 120 |
.Test Report | 测试报告 | 30 | 60 |
.Size Measurement | 计算工作量 | 30 | 40 |
.Postmortem & Process Improvement Plan |
事后总结,并提出过程改进计划 | 30 | 30 |
合计 | 3030 | 3000 |
最新文章
- XCodeGhost表明:为了安全,开发工具应该从官方网站下载
- BZOJ-3225 立方体覆盖 线段树+扫描线+乱搞
- (进阶篇)浅谈COOKIE和SESSION关系和区别
- Nginx - HTTP Configuration, Module Directives
- Scala学习笔记(三)类层级和特质
- 在WIN7系统下用Quartus ii 11.1 NIOS II 11.1 有时候会出现Nios II 的Run as hardware 中报错:Downloading ELF Process failed
- android中handler使用应该注意的问题(解决由handler引起的OOM内存泄漏)
- (重要) html概念之 input:name与id详解
- JRE与JDK
- too many open files linux服务器 golang java
- Caused by: java.lang.IllegalStateException: RedisConnectionFactory is required
- Linux 中改变主机名的 4 种方法
- Oracle优化器基础知识之访问数据的方法
- fzu1050 Number lengths(对数公式)
- hihocoder 1343 : Stable Members【拓扑排序】
- AngularJS转换请求内容
- Use GDB to debug a C++ program called from a shell script
- python之递归锁【Rlock】
- Android Studio 快速实现上传项目到Github(详细步骤)
- SQL---->;mySQl数据库1------表内容的增删改查
热门文章
- Ubuntu matplotlib显示中文乱码的解决方法
- MyEclipse2016项目内复制一个项目,如何更改项目的访问路径
- oracle函数 BFILENAME(dir,file)
- win10 uwp httpClient 登陆CSDN
- iptables 伪装(Masquerading)
- 2016年开源软件排名TOP50,最受IT公司欢迎的50款开源软件
- 我爱自然语言处理bert ner chinese
- 微信小程序下拉刷新真机无法弹回
- 2015-2016 ACM-ICPC Southwestern Europe Regional Contest (SWERC 15)
- Adam那么棒,为什么还对SGD念念不忘 (3)—— 优化算法的选择与使用策略