10天没写代码了啊。，一个这样的搜索写了两小时。。我擦。。
搜索部分没什么好说的。。主要就是visited标记位。。申明类型为int。以后每次visited就+1，回溯就-1。。这样就可以避免交叉的问题出现（感谢春哥的方法。）
#include<iostream>
using namespace std;
int map[10][10];
int visited[10][10][10];
void init()
{
memset(visited,0,sizeof(visited));
}
bool dfs(int num)
{
int i,j;
int k;
i=num/9;
j=num%9;
while(num<=80&&map[i][j]!=-1)
{
num++;
i=num/9;
j=num%9;
}
i=num/9;
j=num%9;
if(num>=81)
{
return 1;
}
for(k=1;k<=9;k++)
{
if(!visited[i][j][k])
{
visited[i][j][k]=1;
map[i][j]=k;
int l;
for(l=0;l<=8;l++)
{
visited[i][l][map[i][j]]++;
visited[l][j][map[i][j]]++;
visited[(i/3)*3+l/3][(j/3)*3+l%3][map[i][j]]++;
//cout<<(i/3)*3+l/3<<"|"<<(j/3)*3+l%3<<endl;
}
if((dfs(num+1)))
{
return 1;
}else
{
int l;
for(l=0;l<=8;l++)
{
visited[i][l][map[i][j]]--;
visited[l][j][map[i][j]]--;
visited[(i/3)*3+l/3][(j/3)*3+l%3][map[i][j]]--;
}
visited[i][j][k]=0;
map[i][j]=-1;
}
}
}
return 0;
}
int main()
{
int t;
cin>>t;
bool tag=0;
bool tag2=0;
while(t--)
{
if(tag2)
{
char fuck[44];
cin>>fuck;
}
tag2=1;
int i,j;
int done=0;
init();
for(i=0;i<=8;i++)
{
for(j=0;j<=8;j++)
{
char c;
cin>>c;
if(c=='?')
{
map[i][j]=-1;
}else
{
map[i][j]=c-'0';
done++;
int k;
for(k=0;k<=8;k++)
{
visited[i][k][map[i][j]]++;
visited[k][j][map[i][j]]++;
visited[(i/3)*3+k/3][(j/3)*3+k%3][map[i][j]]++;
//cout<<(i/3)*3+k/3<<"|"<<(j/3)*3+k%3<<endl;
}
}
}
}
if(dfs(0))
{
if(tag)
{
cout<<"---"<<endl;
}
for(i=0;i<=8;i++)
{
for(j=0;j<=8;j++)
{
cout<<map[i][j];
}
cout<<endl;
}
tag=1;
}else
{
if(tag)
{
cout<<"---"<<endl;
}
cout<<"impossible"<<endl;
tag=1;
}
}
return 0;
}