软件工程个人项目之数独工程(二)
软件工程个人项目之数独工程(二)
上一篇我们的问题卡到了只能输出十万个,一百万个就是不可能。
解决方案
为了解决这个非常重要的问题,我就百度了一下数独这个终局的特点,哇,我发现我真的是想得太简单了,大家的想法真的非常好,但是我是肯定不会修改我之前写过的代码,于是我就发现了数独有个非常重要的特点:在特定的区域内,我们可以交换行和列,这样数独就生成新的了,那我的想法很简单,我就让我的回溯生成十万个,对于每一个,我让他变换,一个能变幻出来很多的终局,只要进行行列的交换,于是有了下面的代码:
void tianshu(int row,int line,int sum,ofstream &file1)//,row line==next
{
//ofstream file1("终局.txt");
int templ[9] = {0};//模板,每次清0,查看是否十个数都已经遍历过
int sym =check(row, line, templ);
int i,j,i1,i2,j2,j3,j1;
while (sym--)
{
for (i = 0; i < 9; i++)
{
if (templ[i] == 0)
{
templ[i] = 1;
zhongju[line][row] = i + 1;
break;
}
}
if (row==8)
{
if (line==8)
{
//Print(zhongju);
//num++;
if (Znum == sum)
flag = 0;
//接下来是进行代码改进
int hang[9] = { 0,1,2,3,4,5,6,7,8 }, lie[9] = {0,1,2,3,4,5,6,7,8};//这两个数组可以帮助我们制作出更多的矩阵!刚开始都是默认的顺序
for (i = 1; i <=2; i++)
{
if (flag == 0)
break;
for (j = 0; j <= 2; j++)
{
if (i != 0 && j == 0)
continue;
if (flag == 0)
break;
for (int spec = 1; spec <= 2; spec++)
{
hang[spec] = spec;
}
if (((i + j) % 3) < (i % 3))
{
break;
}
else
{
int h;//容器
h = hang[i];
hang[i] = hang[i + j];
hang[i + j] = h;
for (i1 = 0; i1 <= 2; i1++)
{
if (flag == 0)
break;
for (j1 = 0; j1 <= 2; j1++)
{
if (i1 != 0 && j1 == 0)
continue;
if (flag == 0)
break;
for (int spec = 0; spec <= 2; spec++)
{
hang[3+spec] = 3+spec;
}
if (((i1 + j1) % 3) < (i1 % 3))
{
break;
}
else
{
h = hang[3+i1];
hang[3+i1] = hang[3+i1 + j1];
hang[3+i1 + j1] = h;
for (i2 = 0; i2 <= 2; i2++)
{
if (flag == 0)
break;
for (j3 = 0; j3 <= 2; j3++)
{
if (i2 != 0 && j3 == 0)
continue;
if (flag == 0)
break;
/*for (int spec = 0; spec <= 2; spec++)
{
hang[6+spec] = 6+spec;
}*/
if (((i2 + j3) % 3) < (i2 % 3))
{
break;
}
else
{
//行的变换结束了,接下来是列的变换
int h;//容器
h = lie[i2];
lie[i2] = lie[i2 + j3];
lie[i2 + j3] = h;
for (i = 1; i <= 2; i++)
{
if (flag == 0)
break;
for (j = 0; j <= 2; j++)
{
if (i != 0 && j == 0)
continue;
if (flag == 0)
break;
for (int spec = 1; spec <= 2; spec++)
{
lie[spec] = spec;
}
if (((i + j) % 3) < (i % 3))
{
break;
}
else
{
int h;//容器
h = lie[i];
lie[i] = lie[i + j];
lie[i + j] = h;
for ( i1 = 0; i1 <= 2; i1++)
{
if (flag == 0)
break;
for (j1 = 0; j1 <= 2; j1++)
{
if (i1 != 0 && j1 == 0)
continue;
if (flag == 0)
break;
for (int spec = 0; spec <= 2; spec++)
{
lie[3 + spec] = 3 + spec;
}
if (((i1 + j1) % 3) < (i1 % 3))
{
break;
}
else
{
h = lie[3 + i1];
lie[3 + i1] = lie[3 + i1 + j1];
lie[3 + i1 + j1] = h;
for ( i2 = 0; i2 <= 2; i2++)
{
if (flag == 0)
break;
for (j3 = 0; j3 <= 2; j3++)
{
if (i2 != 0 && j3 == 0)
continue;
if (flag == 0)
break;
for (int spec = 0; spec <= 2; spec++)
{
lie[6 + spec] = 6 + spec;
}
if (((i2 + j3) % 3) <(i2 % 3))
{
break;
}
else
{
h = lie[6+i2];
lie[6+i2] = lie[6+i2 + j3];
lie[6+i2 + j3] = h;
for (int drawline = 0; drawline < 9; drawline++)
{
for (int drawrow = 0; drawrow < 9; drawrow++)
{
file1 << zhongju[hang[drawline]][lie[drawrow]]<<" ";
}
file1 << "\n";
}
file1 << "\n";
Znum++;
if (Znum == sum)
flag = 0;
/*for (int drawline = 0; drawline < 9; drawline++)
{
hang[drawline] = drawline;
lie[drawline] = drawline;
}*/
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
return;
}
else
{
//row = 0;
//line++;
tianshu(0, line+1,sum,file1);
i = 0;
}
}
else
{
//row++;
tianshu(row+1, line,sum,file1);
i = 0;
}
if (flag == 0)
break;
}
}
我把这个代码放出来的目的就是想让大家看看我的代码风格多么地差劲,而且看看我的这种实现方式多么的可笑,你也看到了,多少个循环,我把这个函数测试的时候,他竟然还是只能输出100000个,为此,我放弃了在原有基础上添加这种嵌套循环的办法,不过我先声明一点,上述代码,没有错误,他确确实实能运行,只是大家都不接受。
再次改进:
我现在已经有了十万个,那我就让每一个再变换出来十个不就行了?
于是我就在主函数里面,初始化了是个数组,(这种办法虽然看起来不太好,但是实现效果真的不差):
int hang1[9] = { 0,1,2,3,4,5,6,8,7 };
hang[0] = hang1;
int hang2[9] = { 0,1,2,3,4,5,8,6,7 };
hang[1] = hang2;
int hang3[9] = { 0,1,2,3,5,4,6,8,7 };
hang[2] = hang3;
int hang4[9] = { 0,1,2,4,3,5,8,6,7 };
hang[3] = hang4;
int hang5[9] = { 0,2,1,3,4,5,6,8,7 };
hang[4] = hang5;
int hang6[9] = { 0,1,2,5,4,3,8,6,7 };
hang[5] = hang6;
int hang7[9] = { 0,1,2,3,4,5,6,7,8 };
hang[6] = hang7;
int hang8[9] = { 0,1,2,4,3,5,7,6,8 };
hang[7] = hang8;
int hang9[9] = { 0,2,1,3,5,4,6,7,8 };
hang[8] = hang9;
int hang10[9] = { 0,2,1,3,4,5,6,8,7 };
hang[9] = hang10;
这才叫真的空间换时间,对于每一个数组,都是对我回溯生成的那个数组的行的输出顺序,
给大家看一下最后的tianshu():
void tianshu(int row, int line, int sum)//,row line==next
{
//ofstream file1("终局.txt");
int templ[9] = { 0 };//模板,每次清0,查看是否十个数都已经遍历过
int sym = check(row, line, templ);
int i, j, i1, i2, j2, j3, j1;
while (sym--)
{
for (i = 0; i < 9; i++)
{
if (templ[i] == 0)
{
templ[i] = 1;
zhongju[line][row] = i + 1;
break;
}
}
if (row == 8)
{
if (line == 8)
{
Print(zhongju);
Znum++;
if (Znum == sum)
flag = 0;
for (int i = 0; i < 10; i++)
{
for (int i1 = 0; i1 < 9; i1++)
{
for (int j1 = 0; j1 < 9; j1++)
{
//file1 << zhongju[hang[i][i1]][j1] << " ";
fputc(zhongju[hang[i][i1]][j1] + '0', file1);
fputc(' ', file1);
}
//file1 << "\n";
fputc('\n',file1);
}
//file1 << "\n";
fputc('\n', file1);
Znum++;
if (Znum == sum)
{
flag = 0;
break;
}
}
}
else
{
//row = 0;
//line++;
tianshu(0, line + 1, sum);
i = 0;
}
}
else
{
//row++;
tianshu(row + 1, line, sum);
i = 0;
}
if (flag == 0)
break;
}
}
我把输出直接放在里面了,因为便于我进行测试,最后我发现,就是懒,这样放着不错,但是有失代码的耦合,我觉得不好。
上面这个函数就是我最终的生成函数。
里面只调用了check这个函数。
这虽然是最终的版本,但是我在之前还是经历了一个夭折的版本,问题是什么,就是输出。
本来我是写了输出的函数,给大家看一下:
void Print(int x[9][9])
{//ofstream file1("终局.txt");
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9;j++)
{
//file1<< x[i][j]<<" ";
fputc(x[i][j] + '0', file1);
fputc(' ', file1);
}
//file1<<"\n";
fputc('\n', file1);
}
//file1<<"\n";
fputc('\n', file1);
//file1.close();
}
我之所以没有用这个函数,是因为这个函数之前不是这样的,这是我修改之后的,在第一次写的时候,我输入文件的办法利用的是文件流ofstream,事实证明,这个非常不好用,我在性能分析里发现这个函数,也就是输出部分,占用了我整个运算过程的时间的百分之九十多,于是我在网上找了另外一个办法,经过我得测试,真的得到了很大的改进。
这是我改进之后的测试,可以看到,这两个输出就占用了我百分之八十!
当然了,这是修改之后的,我为什么没有放出来修改之前的是因为我根本就没有办法让这个运行停止(太慢了,我等了五分钟!)
那么对于生成数独终局的所有解释就到这里结束啦,下面我要给大家讲一下解数独的问题!请参考下一个博客!