数独的生成和求解
2019-12-22 本文已影响0人
董泽平
1.代码托管地址
https://github.com/dong199903/suDu
2.耗费时间
| 列表 | Personal Software Process Stages | 预计耗时 | 实际耗时 |
|---|---|---|---|
| Planning | 计划 | 60 | 30 |
| Estimate | 估计这个任务需要的时间 | 500 | 300 |
| Development | 开发 | 140 | 100 |
| Analysit | 需求分析 | 100 | 150 |
| Design Spec | 生成设计文档 | 100 | 100 |
| Coding Standard | 代码规范 | 90 | 100 |
| Design | 具体设计 | 70 | 60 |
| Codeing | 具体编码 | 1800 | 2000 |
| Code Review | 代码复审 | 100 | 90 |
| Test | 测试 | 90 | 80 |
| Reporting | 报告 | 80 | 90 |
| Test Report | 测试报告 | 50 | 50 |
| Size Measure | 计算工作量 | 60 | 40 |
| Postmotre | 事后总结 | 50 | 40 |
| 合计 | 3150 | 3010 |
3.需求分析
- 用熟悉的编程语言实现数独的题目
- 总体分为生成不重复的数独文件，并求解数独文件的数独程序
- 要求按照软件工程规范来设计，且数独的第一个是按照学号计算来的
- 要求数独可以用两种命令去实现对应的功能
- 要求列出程序的性能图
4.解题思想
- 按照题目要求，大致分为两个模块去分别实现，所以我初步设计两个类，一个是Sudu_Construct类，一个是Sudu_Deal类分别处理数独，其中Sudu_Construct类就是用户可以通过-r 行数的方式构造出数独，并将数独文件写在suduku.txt里面。另外一个Sudu_Deal类是求解对应数独文件，求出数独的解过程。
- 首先要求构造数独，且不能重复，那我开始还很犹豫用什么写，于是搜集网上各种建议，并通过test文件测试这些方法，决定用全排列也就是回溯的方法去解决问题。
5.设计过程
- 大体固定两个类，一个构造数独的类，一个求解数独的类。
- 结合网络资料，从模仿学习到自己的独立去完整实现。
- 不断优化各类程序解决的复杂，保证程序健壮性，符合软件工程代码规范
- 将每次改进和代码优化以及文档的编写，都去逐步完善。
6.程序性能时间
1.jpg
7.代码说明
首先是两个类的定义
- Sudu_Construct类的定义
#pragma once
//构造数独
class Sudu_Construct
{
private:
int count;//个数
public:
Sudu_Construct(int num);//构造函数
~Sudu_Construct();
void getSudu();
int getCount();
};
- Sudu_Deal类的定义
#pragma once
class Sudu_Deal {
public:
int data[10][10];
int biaoji[10][10];
public:
Sudu_Deal();
void deal();
int find(int x,int y);
~Sudu_Deal();
};
- 构造数独的核心过程
//构造数独
void Sudu_Construct::getSudu()
{
int count = 0,temp;
int port[10] = { 0,0,6,5,4,3,2,1,7,8 };
char str[10] = { '9','3','1','2','7','4','5','6','8','9' };
if (count < this->count)
{
for (int a = 0; a < 6; a++)
{
if (count == this->count)
break;
if (a)
next_permutation(port + 4, port + 6);
for (int b = 0; b < 6; b++)
{
if (b)
next_permutation(port + 7, port + 9);
int t = 0;
//char kong = ' ';
do {
if (t)
next_permutation(str + 2, str + 9);
for (int i = 1; i <= 9; i++)
{
for (int j = 1; j <= 9; j++)
{
if (j - port[i] >= 0)
temp = j - port[i];
else
temp = j - port[i] + 9;
//putchar(str[temp % 9]);
cout << str[temp % 9];
if (j < 9)
//putchar(' ');
cout << " ";
}
cout << endl;
}
count++;
t++;
if (count == this->count)
break;
else
cout << endl;
} while (t<40320);
if (count == this->count)
break;
}
}
}
}
- 处理数独
int Sudu_Deal::find(int x, int y)
{
if (x > 9 || y > 9) return 1;
if (biaoji[x][y])
{
if (y < 9)
{
if (find(x, y + 1))
return 1;
}
else
{
if (x < 9)
{
if (find(x + 1, 1))
return 1;
}
else
return 1;
}
}
else
{
for (int n1 = 1; n1 <= 9; n1++)
{
int slogan = 1;
for (int i = 1; i <= 9; i++)//看列有没有
{
if (this->data[i][y] == n1)
{
slogan = 0;
break;
}
}
if (slogan)//看行有没有
{
for (int j = 1; j <= 9; j++)
{
if (this->data[x][j] == n1)
{
slogan = 0;
break;
}
}
}
if (slogan)
{
int rawtop, columntop;
if (x % 3 == 0)
rawtop = x;
else
rawtop = (x / 3) * 3 + 3;
if (y % 3 == 0)
columntop = y;
else
columntop = (y / 3) * 3 + 3;
for (int i = rawtop - 2; i <= rawtop; i++)
{
for (int j = columntop - 2; j <= columntop; j++)
{
if (this->data[i][j] == n1)
{
slogan = 0;
break;
}
}
if (!slogan)
break;
}
}
if (slogan)//判断过后看1-9放哪一个
{
this->data[x][y] = n1;
if (y < 9)
{
if (find(x, y + 1))
return 1;
}
else
{
if (x < 9)
{
if (find(x + 1, 1))
return 1;
}
else
return 1;
}
this->data[x][y] = 0;
}
}
}
return 0;
}
总结
通过本次个人项目数独程序的完成，我用软件工程中的需求分析，和代码规范去理解问题，组织程序，到最后的实现完成，整个过程其实还是磕磕绊绊的，因为回溯法没理解深刻，上手code也比较费劲，最后通过网上阅读回溯，和问同学，完成了整个基本流程。
