软件工程2019第三次作业

GitHub地址

https://github.com/Aurora-gloam/031702411

题目

百度百科简介：
数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。
实现一个命令行程序，不妨称之为Sudoku。

PSP表格

PSP2.1	Personal Software Process Stages	预计耗时（分钟）	实际耗时（分钟）
Planning	计划(估计这个任务需要多少时间)	60	60
Development	开发	905	785
Analysis	需求分析（包括学习新技术）	120	90
Design Spec	生成设计文档	60	30
Design Review	设计复审	30	10
Coding Standard	代码规范（为目前的开发制定合适的规范）	5	5
Designt	具体设计	60	40
Coding	具体编码	480	360
Code Review	代码复审	30	10
Test	测试（自我测试、修改代码，提交修改）	120	240
Reporting	报告	290	230
Test Repor	测试报告	30	30
Size Measurement	计算工作量	20	20
Postmortem&Process Improvement Plan	事后总结并提出过程改进计划	240	180
合计		1255	1075

###解题思路   一开始看到作业要求是**解数独**，我首先想了想我自己会怎么去解一个数独。我应该会在需要填入数值的空格所在的那一行、那一列、那一宫看出现了哪些数字，这些数字被排除在可填入的可能性中。接下来在剩下可以填入的数字中选一个先填入，然后考虑下一个需要填数的空格，考虑的过程与上一个相同。一直如此，直到填完所有空格，或是出现无数字可填入的情况。如果那个空格所在的行、列、宫已经出现所有的数字，那么就回到上一个填入数字的空格处填入其他的可填入的数字。然后在接着往下一个个空格填写。如果填完了所有空格。那么就解出了这个数独。然后我就想我的程序能够依照相同的方式来解数独。 ###设计思路 - 首先，建了一个类**sudoku**表示数独盘面中需要我们填写的空格，包含该空格所在的行*row*、列*col*、可能填入的值*val*、可能数字的个数*sum*以及对应数据成员的设置与获取函数。 - 其次，设计一个查看空格所在行、列、宫所出现过的数字的函数**check**。用一个数组*a*存储结果，数组的下标表示出现的数字，数组的值表示该下标所代表的数字出现的次数。 - 再次，设计一个返回上一空格重新填数字的函数**back**。对类中的*sum*进行判断，如有多种可能则填入存储的*val*值；否则继续调用*back*函数。 - 最后，定义一个二维数组*su*存放一个数独盘面。将类对象*s*、存放盘面的二维数组*su*以及存放出现数字的数组*a*设为全局变量。

代码说明

1.类sudoku

class sudoku
{
private:
	int row;
	int col;
	int sum;// 为val数组可达到的最大下标 
	int val[9];
public:
	void setrow_col(int r, int c);
	void setsum();
	void setval_sum(int num);
	int getval(int t);
	int getsum();
	int getrow();
	int getcol();
};
void sudoku::setrow_col(int r, int c)//对数据成员行、列进行赋值 
{
	col = c;
	row = r;
}
void sudoku::setsum()//每回到一次此空格重新填入，数值减1 
{
	sum = sum - 1;
}
void sudoku::setval_sum(int num)//将该空格可能的数值填入val数组中 ；num为数独阶数  
{
	int i, j = 0;
	for (i = 1; i <= num; i++)
	{
		if (a[i] == 0)
		{
			val[j] = i;
			j++;
		}
	}
	sum = j - 1;
}
//获取数据成员
int sudoku::getval(int t)
{
	return val[t];
}
int sudoku::getsum()
{
	return sum;
}
int sudoku::getcol()
{
	return col;
}
int sudoku::getrow()
{
	return row;
}

2.查看出现数字的函数check

//遍历该空格所在行、列、宫中出现的数
//su是全局变量，一个二维数组，用来存放数独盘面。
void cheak(int r,int c,int num)//r是所在行号，c是所在列号，num是数独盘面的阶数
{
	int i,j,x,y;
	for(i=0;i<10;i++)//a数组中存放下标所示数字在行、列、宫中出现的次数；每对一个空格查看出现过的数，需要对数组重置为0
	{
		a[i]=0;
	}
	for(i=0;i<num;i++)//查看所在行出现的数 
	{
		if(su[r][i]!=0)
		a[su[r][i]]=a[su[r][i]]+1;
	} 
	for(i=0;i<num;i++)//查看所在列出现的数 
	{
		if(su[i][c]!=0)
		a[su[i][c]]=a[su[i][c]]+1;
	} 
//查看所在宫出现的数
//x,y是用来标识空格所在宫的位置
	if(num==4) 
	{
		x=r/2;
		y=c/2;	
		for(i=x*2;i<=(x*2+1);i++)
		{
			for(j=y*2;j<=(y*2+1);j++)
			{
				if(su[i][j]!=0)
				a[su[i][j]]=a[su[i][j]]+1;
			}
		}
	} 
	else if(num==6)
	{
		x=r/2;
		y=c/3;	
		for(i=x*2;i<=(x*2+1);i++)
		{
			for(j=y*3;j<=(y*3+2);j++)
			{
				if(su[i][j]!=0)
				a[su[i][j]]=a[su[i][j]]+1;
			}
		}		
	}
	else if(num==8)
	{
		x=r/4;
		y=c/2;	
		for(i=x*4;i<=(x*4+3);i++)
		{
			for(j=y*2;j<=(y*2+1);j++)
			{
				if(su[i][j]!=0)
				a[su[i][j]]=a[su[i][j]]+1;
			}
		}		
	}
	else if(num==9)
	{
		x=r/3;
		y=c/3;	
		for(i=x*3;i<=(x*3+2);i++)
		{
			for(j=y*3;j<=(y*3+2);j++)
			{
				if(su[i][j]!=0)
				a[su[i][j]]=a[su[i][j]]+1;
			}
		}		
	}
 } 

其中对宫的查询已出现数字思路是先确定空格所在的宫的位置，再从宫的首格开始查看并记录出现的数字。宫的首格通过将空格所在的位置除以宫格的规格，将商再乘上宫格规模来得到，如六宫格是x=r/2,y=c/3；空格所在宫的第一格位置为2*x,3*y，其他阶数的宫类似操作。如下图， 

**3.重新填入下一可能值的函数back **

int back(int t)//重置该空格的值 
{
	if(s[t].getsum()>=0)//判断该空格是否还有其他未填入可能数字。若有，填入该值且该空格可能数字个数减1；若无，将本格中数字置0，继续调用back函数回到上一个空格。
	{
		su[s[t].getrow()][s[t].getcol()]=s[t].getval(s[t].getsum());
		s[t].setsum(); 
	} 
	else
	{
		su[s[t].getrow()][s[t].getcol()]=0;
		t=back(t-1);
	}
	return t;
}

4.主函数

int main(int argc, char** argv)
{
	int i, j, p = 0, n, m;
	ifstream ifp;
	ofstream ofp;
	m = atoi(argv[2]);//宫阶数 
	n = atoi(argv[4]);//盘面数 
	ifp.open(argv[6]);
	if (!ifp.is_open())//判断文件是否成功打开
		cout << "文件打开失败" << endl;
	ofp.open(argv[8]);
	if (!ofp.is_open())
		cout << "文件打开失败" << endl;
	while (n > 0)
	{
		for (i = 0; i < m; i++)//输入数独盘面 
		{
			for (j = 0; j < m; j++)
			{
				ifp >> su[i][j];
			}
		}
		p = 0;
		for (i = 0; i < m; i++)//解数独 
		{
			for (j = 0; j < m; j++)
			{
				if (su[i][j] == 0)//判断是否为需要填数的空格 
				{
					s[p].setrow_col(i, j);
					cheak(i, j, m);
					s[p].setval_sum(m);
					if (s[p].getsum() >= 0)//如该空格存在可能填入的数字，则填入空格 
					{
						su[i][j] = s[p].getval(s[p].getsum());
						s[p].setsum();
						p++;
					}
					else//如不存在可能，则回到上一个空格处 
					{
						p = p - 1;
						p = back(p);
						j = s[p].getcol();
						i = s[p].getrow();
						p++;
					}
				}
			}
		}
		for (i = 0; i < m; i++)//输出解出的数独 
		{
			for (j = 0; j < m; j++)
			{
				if (j < (m - 1))
					ofp << su[i][j] << " ";
				else
					ofp << su[i][j];
			}
			ofp << endl;
		}
		ofp << endl;
		n--;
	}
	ifp.close();//关闭文件
	ofp.close();
	return 0;
}

运行结果

利用助教收集的数独盘面以及自己在网络上找的数独盘面，输入后结果如下：

性能分析

心路历程和收获

  经过这次的个人编程作业，我学习到了很多。学会了在命令行中对主函数传参数，学会了读取文件的操作，学会了在GitHub上上传文件......现在的自己还有很多的东西需要去学习，还要努力才可以。加油！