大家好,欢迎来到IT知识分享网。
Github地址:https://github.com/BLLeen/SoftObject
项目需求
利用程序随机构造出N个已解答的数独棋盘 。
输入
数独棋盘题目个数N(0<N<=1000000)
输出
随机生成N个 不重复 的 已解答完毕的 数独棋盘,并输出到sudoku.txt中,输出格式见下输出示例。
[2017.9.4 新增要求] 在生成数独矩阵时,左上角的第一个数为:(学号后两位相加)% 9 + 1。例如学生A学号后2位是80,则该数字为(8+0)% 9 + 1 = 9,那么生成的数独棋盘应如下(x表示满足数独规则的任意数字)
解题思路
大多数数独的生成方法就是暴力生成,一个个进行尝试判断是否满足数独条件这种算法的准确性高但是运算速度比较慢,发现一个算法较为快速方便,即将数独枚举生成改为原始数独通过随机变换生成变型后的数独。这种生成算法的思路就是将一个成型数独进行随机的变换。这个装换过程就是依照随机数组进行改改变,可以是将成型数独依照1-9的随机排列数组进行变换。
即在原始数独上从第一个到最后一个进行遍历,每一个数字对应随机数组该数字所在位置后面几位如一位进行变换,因为每个数字的变换的都是同时变换且不重复的进行变换,所以原来的数组9宫格里面不一样,改变后必定不一样,原来的在行里面不一样,变换后的行必定不一样,原来的列里面的不一样,变换后必定不一样。即一个数独有8!
(为什么不是9!因为要求每个数独第一个是9我的学号换算是9所以有捆绑,即X9捆绑在一起)个变换,即40320个变换,所以有25个原始数独即可生成1000000+的数独。
设计实现
step1
生成随机数组并对每个不同的原始数独产生符合的条件的数组
x是每个原始数组的第一个数字
int RandomArr(int x)//生成1-9的随机数组,且x的后面是9
{
int a_position;
int a[9]={1,2,3,4,5,6,7,8,9};
int r=9;
int step;
for(int i=0;i<9;i++)
{
a_position= rand()%r;
a1[i]=a[a_position];
a[a_position]=a[r-1];
r--;
}//生成随机数组
int find_x_next;
int find_spe;
for(int i=0;i<9;i++)
{
if(a1[i]==x)find_x_next=(i+1)%9;
if(a1[i]==spe)find_spe=i;
}
a1[find_spe]=a1[find_x_next];//将x后面的数与spe所在的位置调换
a1[find_x_next]=spe;//将数组改为满足条件的
}
step2
对26个原始数独进行变换一个变换输出一个
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
{
int GetSelfArr=SelfArr[x][i][j];
for(int k=0;k<9;k++)
{
if(a1[k]==GetSelfArr)
{
_creatarr[i][j]=a1[(k+1)%9];
break;
}
}
}
step3
对“sudoku.exe -c 1000”cmd命令进行判断报错
http://bbs.csdn.net/topics/391939057
学习这个论坛帖子进行学习argc,args所表示的含义及带有参数的main函数
可以得出main函数的两个参数用于接收命令行的参数,第一个是命令行参数的个数,第二个一个字符串数组用于访问命令行的参数
(该命令args=3
argv[0]=”sudoku.exe”
argv[1]=”-c”
argv[2]=”10000″)。
主函数部分代码及对命令行的
int main(int argc,char *argv[]){
int N=0;
/**
判断输入格式
1.三位,如果不是直接跳出
2.是否符合'-c'
3.后面的N是否是数字1-1000000
**/
if(argc!=3)
{
cout<<"输入错误!"<<endl;
return 0;
}
string str1=argv[1];
string str=argv[2];
if(str1!="-c")
{
cout<<"请使用'-c'"<<endl;
return 0;
}
int wei=0;
int leng=str.length();
while(leng>0)
{
if(48<=str[leng-1]&&str[leng-1]<=57)
{
N+=(str[leng-1]-48)*pow(10,wei);
wei++;
}
else
{
cout<<"请输入正确的N"<<endl;
return 0;
}
leng--;
}
测试运行
程序在cmd运行下的结果
运行时间挺快的,N=1000000的情况下运行时间是30s左右
输出结果
相对于枚举法生成数独来说这个方法生成的数独在较大数量时会产生1-2次重复的数独所以准确性有待提高
总结
PSP2.1 | Personal Software Process Stages | 预估耗时(分钟) | 实际耗时(分钟) |
---|---|---|---|
Planning | 计划 | ||
· Estimate | · 估计这个任务需要多少时间 | 10 | 20 |
Development | 开发 | ||
· Analysis | · 需求分析 (包括学习新技术) | 60 | 45 |
· Design Spec | · 生成设计文档 | 30 | 30 |
· Design Review | · 设计复审 (和同事审核设计文档) | 20 | 10 |
· Coding Standard | · 代码规范 (为目前的开发制定合适的规范) | 30 | 30 |
· Design | · 具体设计 | 40 | 40 |
· Coding | · 具体编码 | 100 | 300 |
· Code Review | · 代码复审 | 20 | 40 |
· Test | · 测试(自我测试,修改代码,提交修改) | 20 | 50 |
Reporting | 报告 | ||
· Test Report | · 测试报告 | 60 | 100 |
· Size Measurement | · 计算工作量 | 10 | 10 |
· Postmortem & Process Improvement Plan | · 事后总结, 并提出过程改进计划 | 30 | 50 |
合计 | 430 | 725 | |
大部分时间是在于对代码的查错对代码的检查,这次的项目有3个get到的技能 |
-对随机数的种子的设定一个程序里面一个 就够了,多次会出现错误
-对给github的应用
-c/c++main(int args ,*argv[])的应用
学习进度条
第N周 | 新增代码(行) | 累计代码(行) | 本周学习耗时(小时 ) | 累计学习耗时(小时) | 重要成长 |
---|---|---|---|---|---|
第一周 | 100 | 100 | 725 | 725 | github的使用,项目分析技巧等 |
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/33572.html