题意就是做一个4*4的数独，之前做过9*9的，没什么取巧的，也就是用深搜
比较不一样的是，这道题在有多组解得时候要把解都输出，要用到回溯法
时间还是有点长的，勉强过了吧
#include #include #include #include using namespace std;
const int N=8;
int mp[N][N];
bool solve(int val ,int pel, int x)
{
bool flag[5];
memset(flag,false,sizeof(flag));
for(int i=0 ;i<4; ++i)
{
if(mp[val][i]!=-1)
flag[ mp[val][i] ] = true;
if(mp[i][pel]!=-1)
flag[ mp[i][pel] ] = true;
}
int va = val /2,pe = pel / 2;
for(int i = va*2; i<=va*2+1; ++i)
{
for(int j=pe*2; j<=pe*2+1; ++j)
{
if(mp[i][j]!=-1)
flag[ mp[i][j] ] = true;
}
}
if(flag[ x ] == false)
return true;
return false;
}
void print()
{
for(int i=0;i<4;++i)
{
for(int j=0;j<4;++j)
printf("%d",mp[i][j]);
puts("");
}
}
void dfs(int cal, int pel)
{
if(cal==4 && pel == 0)
{
print();return ;
}
int cal_next = cal,pel_next = pel;
if(pel==3)
++cal_next,pel_next = 0;
else
++pel_next;
if(mp[cal][pel] == -1)
{
for(int i=1;i<=4;++i)
{
if(solve(cal,pel,i)){
mp[cal][pel] = i;
dfs(cal_next, pel_next);
}
}
mp[cal][pel] = -1;
}
else
dfs(cal_next,pel_next);
}
int main()
{
int T;
scanf("%d",&T);
for(int cas = 1; cas <=T; ++cas)
{
string s[5];
for(int i=0;i<4;++i)
cin>>s[i];
for(int i=0; i<4; ++i)
{
for(int j=0; j<4; ++j)
{
char c = s[i][j];
if(c!='*')
mp[i][j] = (c-'0');
else
mp[i][j] = -1;
}
}
printf("Case #%d:\n",cas);
dfs(0,0);
}
return 0;
}
