老老老老老題..能繼續(xù)剪枝的..但是我懶..
就不剪了..
1y.我喜歡木陷阱的題...
#include <iostream>
#include <vector>
using namespace std;
int c[10][10];
int ca;
struct node
{
int x,y,value;
};
vector<node> v;
bool h[10][10],l[10][10];
bool mat[10][10];
bool ok;
int getPos(int x,int y)
{
return (x-1)/3*3+(y-1)/3+1;
}
void dfs(int pos)
{
if (pos==v.size())
{
for (int i=1;i<=9;i++)
{
for (int j=1;j<=9;j++)
{
cout<<c[i][j];
}
cout<<endl;
}
ok=true;
return;
}
node p=v[pos];
int x=p.x;
int y=p.y;
for (int i=1;i<=9&&(!ok);i++)
{
if (h[x][i]) continue;
if (l[i][y]) continue;
if (mat[getPos(x,y)][i]) continue;
h[x][i]=true;
l[i][y]=true;
mat[getPos(x,y)][i]=true;
c[x][y]=i;
dfs(pos+1);
h[x][i]=false;
l[i][y]=false;
mat[getPos(x,y)][i]=false;
}
}
int main()
{
cin>>ca;
while(ca--)
{
v.clear();
memset(h,false,sizeof(h));
memset(l,false,sizeof(l));
memset(mat,false,sizeof(mat));
ok=false;
char ch;
for (int i=1;i<=9;i++)
for (int j=1;j<=9;j++)
{
cin>>ch;
c[i][j]=ch-'0';
if (c[i][j]==0)
{
node p;
p.x=i;
p.y=j;
p.value=0;
v.push_back(p);
}
else
{
h[i][c[i][j]]=true;
l[c[i][j]][j]=true;
mat[getPos(i,j)][c[i][j]]=true;
}
}
dfs(0);
// solve();
}
//system("pause");
return 0;
}