#include"Linkqueue.h"
# include<fstream>
# include<iostream>
using namespace std;
LinkQueue LQ;
int inputnumber[9][9]={0};//输入数据
int lastinputnumber[9][9]={0};//记录上次输入的数据
int count=0;//统计解得个数
bool isfirstnumber[9][9]={0};//记录是否为题中所给定的初始数据
bool isrow[9][9]={0},iscolumn[9][9]={0},isgird[9][9]={0};// 记录行列宫格是否有重复值，决定该行列宫格能填入的值
int defgird(int i,int j);
void getnumber(char *a);
bool back(int &i,int &j);
bool advance(int &i,int &j);
void holdresult();
void function();
int main(int argc, char *argv[])
{
InitQueue(LQ);
ofstream foutput(argv[2]);
getnumber(argv[1]);
function();
foutput<<count<<endl;
for(int i=1;i<=count;i++)
{
for(int m=0;m<9;m++)
{
for(int n=0;n<9;n++)
{
foutput<<OutQueue(LQ);
}
foutput<<endl;
}
foutput<<endl;
}
foutput.close();
return 0;
}
int defgird(int i,int j)//将9*9宫格，化成9个3*3小宫格
{
if(i<=2) i=0;
else if(i<=5) i=1;
else if(i<=8) i=2;
if(j<=2) j=0;
else if(j<=5) j=1;
else if(j<=8) j=2;
switch(i*10+j)
{
case 0:return 0;
case 1:return 1;
case 2:return 2;
case 10:return 3;
case 11:return 4;
case 12:return 5;
case 20:return 6;
case 21:return 7;
case 22:return 8;
}
}
void getnumber(char *a)//从输入文件中给到数据
{
ifstream finput(a);
int i=0,j=0;
char q;
int p=0 ;//用来暂存数据
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
finput>>q;
p=static_cast<int>(q)-48;
inputnumber[i][j]=p;
if(p!=0)//判断是否是初始化输入的数据
{
isfirstnumber[i][j]=1;//标志为初始化数据
isrow[i][p-1]=1;//表示这一行不能填写数据p;
iscolumn[j][p-1]=1;//表示这一列不能填写数据p;
isgird[defgird(i,j)][p-1]=1;//该小宫格也不能填写数据p;
}
}
}
finput.close();
}
bool back(int &i,int &j)//行列的回退，同时修改i,j的值(变量i,j为引用)
{
if(i==0&&j==0)//若不能回退了，说明所有的结果已经求解完毕
{
return 0;
}
if(j==0)//后退一行
{
j=8;
i--;
}
else//后退一列
j--;
return 1;
}
bool advance(int &i,int &j)//行列的前进，同时修改i,j的值
{
if(i==8&&j==8)
return 0;//不能前进
if(j==8)//前进一行
{
j=0;
i++;
}
else//前进一列
{
j++;
}
return 1;
}
void holdresult()
{
count++;
int i,j;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
EnQueue(LQ,inputnumber[i][j]);
}
void function()//采用逐个试探，回溯的办法
{
int i=0,j=0,p=0;
int isback=0;//用来标识是否为通过回溯来的数据
while(i<9)
{
while(j<9)
{
if(isfirstnumber[i][j]==1)//如果为初始化得数据，则该宫格不能填数据
{
if(isback==1)//若是回退回来的数据,那么就继续回退
{
if(back(i,j)==0)
return ;//如果不能后退，则说明已经求解完毕，退出函数
p=0;//否则，继续回退
continue;
}
else//向前进一步
{
if(advance(i,j)==0)//若不能向前进，则说明已经到了9宫格的底部，可以得到一个解
{ isback=1;//回退标识
holdresult();
}
continue;
}
}
else//否则，可以填写数据
{
if(p==0)
p=inputnumber[i][j]+1;
else
p++;
if(p==10)
{
if(lastinputnumber[i][j]!=0)//撤销行列小宫格不能填上一个p的限制
{
isrow[i][lastinputnumber[i][j]-1]=0,
iscolumn[j][lastinputnumber[i][j]-1]=0,
isgird[defgird(i,j)][lastinputnumber[i][j]-1]=0;
}
lastinputnumber[i][j]=0;//初始化
inputnumber[i][j]=0;
if(back(i,j)==0)
return ;//不能回退，则退出函数
p=0;
isback=1;
}
else
{
if (isrow[i][p-1]==0&&iscolumn[j][p-1]==0&&isgird[defgird(i,j)][p-1]==0)
{
if(p!=1&&lastinputnumber[i][j]!=0)//撤销行列小宫格不能填上一个p的限制
{
isrow[i][lastinputnumber[i][j]-1]=0,
iscolumn[j][lastinputnumber[i][j]-1]=0,
isgird[defgird(i,j)][lastinputnumber[i][j]-1]=0;
}
inputnumber[i][j]=p;
lastinputnumber[i][j]=p;
isrow[i][p-1]=1;
iscolumn[j][p-1]=1;
isgird[defgird(i,j)][p-1]=1;
if(i==8&&j==8)//若填到了最后一个宫格，则所有的结果已经出来
{
holdresult();
}
advance(i,j);
p=0;
isback=0;
}
}
}
}
}
}
