最近试着写了恶心搜索题之Sudoku，就是数独啦，写了615行，而且包括其拓展

最原始的数独是(3^2)^2的，我参考了一些资料，加了六个剪枝和一个枚举过程，在zju上很轻松过了,然后又到pku上去试了试，把几乎全部名字里带Sudoku的都轻松过了。

然后我进行了Sudoku的拓展，成为了可以计算(n^2)^2的代码，自己试了一下，收获不少。

后来发现zju这个数独题目的数据真是很弱，我有一个回溯上的错误在zoj2580上没有测出来（应该说n=3都测不出来），我用那个n=4的样例数据一测试就发现问题了。我估计按照这些剪枝在zoj上基本只剩下多解的情况，那些回溯大体上都省掉了，而且数值非常小。

1、不是剪枝越多效率越高的，Sudoku就很明显，六个剪枝我去掉了几个时间效率会高一点，但是我估计zju的数据都很弱小，并不是那种很强的数值，我试过我的代码跑法国数独竞赛决赛试题，速度超快，我估计那些剪枝会在比如n比较大的时候显示效果吧！^_^

2、对于n比较小的时候，使用位操作是不错的选择，我的代码里面就用一个整数来代替了bool数组，那个枚举某个格子可能情况的bool数组用一个整数就可以搞定了，而且在清空这个数组时候，对于整数只要赋值为0就可以了，十分的方便。当然，这种做法还是有局限性的，就是整数的位数，这个在n>=6的时候就体现出来了，因为6*6=36>32已经超出32位机子上int范围了，但是对于6以上的模块，估计时间是主要问题。但是总的说来，位操作是强大的。

3、Sudoku的复杂度不仅仅看给定数值的多少，那些难题的划分标准并没有一个严格的说法，据我所知Sudoku也作为了刚刚结束的数模美国赛的题目出现，题目要求就是难度的衡量，那些数值少的并不一定是很难的题目，那些无法确定的情况往往成为了解题的关键点，这时候就需要枚举了，我想这也许是人脑的计算机的区别啊，计算机可以开堆栈记录状态，枚举，而人脑则不擅长这个。我的程序在那些极端情况下（板上没有一个数值）也能瞬间给出解答。

写好代码后就把格式改了一下，对于各种情形弄成通用的方法，那个EMP常量表示的是字符阵中表示空的字符，然后那两个to_char和to_num函数很明显是数值和字符的互换的过程，这样各个题目都通用了。stack是用来暂记状态用来回溯的，sn记录的是剩余个数，然后top表示栈顶，从0开始，can则是标记是否出现矛盾的bool变量。

做完Sudoku有种释然的感觉，但是我看到了有一篇论文中介绍了更好的算法，据说代码200+，而且效率更高，下个阶段就研究一下吧。

代码嘛就小发一下啦！^_^

#include<stdio.h>
#include<memory.h>
#include<algorithm>
const int N=3;
const int N_2=N*N;
const int N_2_2=2*N_2;
const int N_2_3=3*N_2;
const int N_4=N_2*N_2;
const char EMP='0';
struct node
{
int pos[N_2][N_2];
int left[N_2][N_2];
char map[N_2][N_2+1];
int sn;
int x;
int y;
int k;
}stack[N_4];
int ti,i,left[N_2][N_2],pos[N_2][N_2],q[N_4][2],s,e,sn,top;
char map[N_2][N_2+1];
bool can;
inline int to_num(char ch)
{
return ch-'0';
}
inline char to_char(int s)
{
return s+'0';
}
void initial()//初始化
{
int i,j;
sn=N_4;
top=-1;
for (i=0;i<N_2;i++)
   for (j=0;j<N_2;j++)
    if (map[i][j]==EMP)
    {
     left[i][j]=N_2;
     pos[i][j]=((1<<N_2)-1)<<1;
    }
    else
    {
     left[i][j]=1;
     pos[i][j]=1<<to_num(map[i][j]);
    }
}
void fix(int x,int y)//确定x,y位置的数值
{
int i,j,k,sr,sc;
sn--;
for (i=1;i<=N_2;i++)
   if (pos[x][y]&(1<<i)) break;
map[x][y]=to_char(i);
left[x][y]=pos[x][y]=0;
for (j=0;j<N_2;j++)
{
   if (pos[j][y]&(1<<i))
   {
    pos[j][y]-=(1<<i);
    left[j][y]--;
    if (left[j][y]==1)
    {
     e++;
     q[e][0]=j;
     q[e][1]=y;
    }
   }
}
for (j=0;j<N_2;j++)
{
   if (pos[x][j]&(1<<i))
   {
    pos[x][j]-=(1<<i);
    left[x][j]--;
    if (left[x][j]==1)
    {
     e++;
     q[e][0]=x;
     q[e][1]=j;
    }
   }
}
sr=x/N*N;sc=y/N*N;
for (j=0;j<N;j++)
   for (k=0;k<N;k++)
   {
    if (pos[sr+j][sc+k]&(1<<i))
    {
     pos[sr+j][sc+k]-=(1<<i);
     left[sr+j][sc+k]--;
     if (left[sr+j][sc+k]==1)
     {
      e++;
      q[e][0]=sr+j;
      q[e][1]=sc+k;
     }
    }
   }
}
bool check_unit()//以队列形式确定可以填上的数值
{
int i,j;
s=0;e=-1;
for (i=0;i<N_2;i++)
   for (j=0;j<N_2;j++)
    if (left[i][j]==1)
    {
     e++;
     q[e][0]=i;
     q[e][1]=j;
    }
    else
     if (left[i][j]==0&&map[i][j]==EMP)
     {
      can=false;
      return false;
     }
while (s<=e)
{
   if (!left[q[s][0]][q[s][1]])
   {
    can=false;
    return false;
   }
   fix(q[s][0],q[s][1]);
   s++;
}
return sn==0;
}
bool check_block()//检测块中只存在单一可能位置的数值
{
bool ret=false;
int i,j,k,m,n;
for (i=0;i<N_2;i++)
   for (j=1;j<=N_2;j++)
   {
    m=0;
    for (k=0;k<N_2;k++)
     if (pos[i][k]&(1<<j))
     {
      m++;
      if (m==1) n=k;
      else break;
     }
    if (m==1)
    {
     ret=true;
     left[i][n]=1;
     pos[i][n]=(1<<j);
    }
   }
for (i=0;i<N_2;i++)
   for (j=1;j<=N_2;j++)
   {
    m=0;
    for (k=0;k<N_2;k++)
     if (pos[k][i]&(1<<j))
     {
      m++;
      if (m==1) n=k;
      else break;
     }
    if (m==1)
    {
     ret=true;
     left[n][i]=1;
     pos[n][i]=(1<<j);
    }
   }
for (i=0;i<N_2;i++)
   for (j=1;j<=N_2;j++)
   {
    m=0;
    for (k=0;k<N_2;k++)
     if (pos[i/N*N+k/N][i%N*N+k%N]&(1<<j))
     {
      m++;
      if (m==1) n=k;
      else break;
     }
    if (m==1)
    {
     ret=true;
     left[i/N*N+n/N][i%N*N+n%N]=1;
     pos[i/N*N+n/N][i%N*N+n%N]=(1<<j);
    }
   }
return ret;
}
bool check_area()//可能值位于同一块的同一区时，清除可能值在可影响的其他区的作用
{
bool ret=false,area[N<<1];
int i,j,k,l,m,mt,n,nt;
for (i=0;i<N_2;i++)
   for (j=1;j<=N_2;j++)
   {
    memset(area,false,sizeof(area));
    m=0;
    for (k=0;k<N_2;k++)
     if ((pos[i][k]&(1<<j))&&!area[k/N])
     {
      area[k/N]=true;
      m++;
      if (m==1) n=k/N*N;
      else break;
     }
    if (m==1)
    {
     m=i/N*N;
     for (k=0;k<N;k++)
      if (k+m!=i)
       for (l=0;l<N;l++)
        if (pos[k+m][n+l]&(1<<j))
        {
         ret=true;
         pos[k+m][n+l]-=(1<<j);
         left[k+m][n+l]--;
        }
    }
   }
for (i=N_2;i<N_2_2;i++)
   for (j=1;j<=N_2;j++)
   {
    memset(area,false,sizeof(area));
    m=0;
    for (k=0;k<N_2;k++)
     if ((pos[k][i-N_2]&(1<<j))&&!area[k/N])
     {
      area[k/N]=true;
      m++;
      if (m==1) n=k/N*N;
      else break;
     }
    if (m==1)
    {
     m=(i-N_2)/N*N;
     for (k=0;k<N;k++)
      if (k+m!=i-N_2)
       for (l=0;l<N;l++)
        if (pos[n+l][k+m]&(1<<j))
        {
         ret=true;
         pos[n+l][k+m]-=(1<<j);
         left[n+l][k+m]--;
        }
    }
   }
for (i=N_2_2;i<N_2_3;i++)
   for (j=1;j<=N_2;j++)
   {
    memset(area,false,sizeof(area));
    m=mt=0;
    for (k=0;k<N_2;k++)
     if (pos[(i-N_2_2)/N*N+k/N][(i-N_2_2)%N*N+k%N]&(1<<j))
     {
      if (m!=2&&!area[k/N])
      {
       area[k/N]=true;
       m++;
       n=k/N;
      }
      if (mt!=N&&!area[k%N+N])
      {
       area[k%N+N]=true;
       mt++;
       nt=k%N;
      }
     }
    if (m==1)
    {
     m=(i-N_2_2)%N*N;
     for (k=0;k<N;k++)
      if (k/N!=n&&(pos[(i-N_2_2)/N*N+k/N][m+k%N]&(1<<j)))
      {
       ret=true;
       pos[(i-N_2_2)/N*N+k/N][m+k%N]-=(1<<j);
       left[(i-N_2_2)/N*N+k/N][m+k%N]--;
      }
    }
    if (mt==1)
    {
     mt=(i-N_2_2)/N*N;
     for (k=0;k<N_2;k++)
      if (k%N!=nt&&(pos[mt+k/N][(i-N_2_2)%N*N+k%N]&(1<<j)))
      {
       ret=true;
       pos[mt+k/N][(i-N_2_2)%N*N+k%N]-=(1<<j);
       left[mt+k/N][(i-N_2_2)%N*N+k%N]--;
      }
    }
   }
return ret;
}
bool check_unit_pair()//两个格的合集为两个元素，则这两个格占有这两个元素
{
bool ret=false;
int i,j,k,l,st[N_2+1][3];
for (i=0;i<N_2;i++)
{
   st[0][0]=0;
   for (j=0;j<N_2;j++)
    if (left[i][j]==2)
    {
     st[++st[0][0]][0]=j;
     l=0;
     for (k=1;k<=N_2;k++)
      if (pos[i][j]&(1<<k)) st[st[0][0]][++l]=k;
    }
   for (j=1;j<st[0][0];j++)
    for (k=j+1;k<=st[0][0];k++)
     if (st[j][1]==st[k][1]&&st[j][2]==st[k][2])
     {
      for (l=0;l<N_2;l++)
       if (l!=st[j][0]&&l!=st[k][0])
       {
        if (pos[i][l]&(1<<st[j][1]))
        {
         ret=true;
         pos[i][l]-=(1<<st[j][1]);
         left[i][l]--;
        }
        if (pos[i][l]&(1<<st[j][2]))
        {
         ret=true;
         pos[i][l]-=(1<<st[j][2]);
         left[i][l]--;
        }
       }
     }
}
for (j=N_2;j<N_2_2;j++)
{
   st[0][0]=0;
   for (i=0;i<N_2;i++)
    if (left[i][j-N_2]==2)
    {
     st[++st[0][0]][0]=i;
     l=0;
     for (k=1;k<=N_2;k++)
      if (pos[i][j-N_2]&(1<<k)) st[st[0][0]][++l]=k;
    }
   for (i=1;i<st[0][0];i++)
    for (k=i+1;k<=st[0][0];k++)
     if (st[i][1]==st[k][1]&&st[i][2]==st[k][2])
     {
      for (l=0;l<N_2;l++)
       if (l!=st[i][0]&&l!=st[k][0])
       {
        if (pos[l][j-N_2]&(1<<st[i][1]))
        {
         ret=true;
         pos[l][j-N_2]-=(1<<st[i][1]);
         left[l][j-N_2]--;
        }
        if (pos[l][j-N_2]&(1<<st[i][2]))
        {
         ret=true;
         pos[l][j-N_2]-=(1<<st[i][2]);
         left[l][j-N_2]--;
        }
       }
     }
}
for (i=N_2_2;i<N_2_3;i++)
{
   st[0][0]=0;
   for (j=0;j<N_2;j++)
    if (left[(i-N_2_2)/N*N+j/N][(i-N_2_2)%N*N+j%N]==2)
    {
     st[++st[0][0]][0]=j;
     l=0;
     for (k=1;k<=N_2;k++)
      if (pos[(i-N_2_2)/N*N+j/N][(i-N_2_2)%N*N+j%N]&(1<<k)) st[st[0][0]][++l]=k;
    }
   for (j=1;j<st[0][0];j++)
    for (k=j+1;k<=st[0][0];k++)
     if (st[j][1]==st[k][1]&&st[j][2]==st[k][2])
     {
      for (l=0;l<N_2;l++)
       if (l!=st[j][0]&&l!=st[k][0])
       {
        if (pos[(i-N_2_2)/N*N+l/N][(i-N_2_2)%N*N+l%N]&(1<<st[j][1]))
        {
         ret=true;
         pos[(i-N_2_2)/N*N+l/N][(i-N_2_2)%N*N+l%N]-=(1<<st[j][1]);
         left[(i-N_2_2)/N*N+l/N][(i-N_2_2)%N*N+l%N]--;
        }
        if (pos[(i-N_2_2)/N*N+l/N][(i-N_2_2)%N*N+l%N]&(1<<st[j][2]))
        {
         ret=true;
         pos[(i-N_2_2)/N*N+l/N][(i-N_2_2)%N*N+l%N]-=(1<<st[j][2]);
         left[(i-N_2_2)/N*N+l/N][(i-N_2_2)%N*N+l%N]--;
        }
       }
     }
}
return ret;
}
bool check_num_group()//一个块中n个数值恰好出现在n个格子里，则删除这n个格子里的其他可能
{
bool ret=false;
int i,j,k,st[N_2+1];//记录状态的数组，低5位表示数值k，中间N_2位表示块中的格集合，5位高表示格的个数
for (i=0;i<N_2;i++)
{
   for (k=1;k<=N_2;k++) st[k]=k;
   for (j=0;j<N_2;j++)
    for (k=1;k<=N_2;k++)
     if (pos[i][j]&(1<<k))
     {
      st[k]|=(1<<(j+5));
      st[k]+=(1<<(N_2+5));
     }
   std::sort(st+1,st+N_2+1);
   for (j=1;j+(st[j]>>(N_2+5))<=N_2+1;j++)
    if ((st[j]>>5)==(st[j+(st[j]>>(N_2+5))]>>5))
     for (k=0;k<N_2;k++)
      if (st[j]&(1<<(k+5)))
      {
       if (left[i][k]!=(st[j]>>(N_2+5))) ret=true;
       pos[i][k]=0;
       for (left[i][k]=0;left[i][k]<(st[j]>>(N_2+5));left[i][k]++)
        pos[i][k]+=(1<<(st[j+left[i][k]]&31));
      }
}
for (j=N_2;j<N_2_2;j++)
{
   for (k=1;k<=N_2;k++) st[k]=k;
   for (i=0;i<N_2;i++)
    for (k=1;k<=N_2;k++)
     if (pos[i][j-N_2]&(1<<k))
     {
      st[k]|=(1<<(i+5));
      st[k]+=(1<<(N_2+5));
     }
   std::sort(st+1,st+N_2+1);
   for (i=1;i+(st[i]>>(N_2+5))<=N_2+1;i++)
    if ((st[i]>>5)==(st[i+(st[i]>>(N_2+5))]>>5))
     for (k=0;k<N_2;k++)
      if (st[i]&(1<<(k+5)))
      {
       if (left[k][j-N_2]!=(st[i]>>(N_2+5))) ret=true;
       pos[k][j-N_2]=0;
       for (left[k][j-N_2]=0;left[k][j-N_2]<(st[i]>>(N_2+5));left[k][j-N_2]++)
        pos[k][j-N_2]+=(1<<(st[i+left[k][j-N_2]]&31));
      }
}
for (i=N_2_2;i<N_2_3;i++)
{
   for (k=1;k<=N_2;k++) st[k]=k;
   for (j=0;j<N_2;j++)
    for (k=1;k<=N_2;k++)
     if (pos[(i-N_2_2)/N*N+j/N][(i-N_2_2)%N*N+j%N]&(1<<k))
     {
      st[k]|=(1<<(j+5));
      st[k]+=(1<<(N_2+5));
     }
   std::sort(st+1,st+N_2+1);
   for (j=1;j+(st[j]>>(N_2+5))<=N_2+1;j++)
    if ((st[j]>>5)==(st[j+(st[j]>>(N_2+5))]>>5))
     for (k=0;k<N_2;k++)
      if (st[j]&(1<<(k+5)))
      {
       int x=(i-N_2_2)/N*N+k/N,y=(i-N_2_2)%N*N+k%N;
       if (left[x][y]!=(st[j]>>(N_2+5))) ret=true;
       pos[x][y]=0;
       for (left[x][y]=0;left[x][y]<(st[j]>>(N_2+5));left[x][y]++)
        pos[x][y]+=(1<<(st[j+left[x][y]]&31));
      }
}
return ret;
}
bool check_line_pair()//两行（列）中有一数值只出现在某两列（行）中，删除这两列（行）其他这个数值的出现
{
bool ret=false;
int i,j,k,l,m,st[N_2][N_2+1];
for (i=0;i<N_2;i++)
{
   memset(st[i],0,sizeof(st[i]));
   for (j=0;j<N_2;j++)
    for (k=1;k<=N_2;k++)
     if (pos[i][j]&(1<<k))
     {
      st[i][k]|=1<<j;
      st[i][k]+=(1<<N_2);
     }
}
for (k=1;k<=N_2;k++)
   for (i=0;i<N_2-1;i++)
    if ((st[i][k]>>N_2)==2)
     for (j=i+1;j<N_2;j++)
      if (st[j][k]==st[i][k])
       for (l=0;l<N_2;l++)
        if (st[i][k]&(1<<l))
         for (m=0;m<N_2;m++)
          if (m!=i&&m!=j&&(pos[m][l]&(1<<k)))
          {
           ret=true;
           left[m][l]--;
           pos[m][l]-=(1<<k);
          }
for (j=0;j<N_2;j++)
{
   memset(st[j],0,sizeof(st[j]));
   for (i=0;i<N_2;i++)
    for (k=1;k<=N_2;k++)
     if (pos[i][j]&(1<<k))
     {
      st[j][k]|=1<<i;
      st[j][k]+=(1<<N_2);
     }
}
for (k=1;k<=N_2;k++)
   for (i=0;i<N_2-1;i++)
    if ((st[i][k]>>N_2)==2)
     for (j=i+1;j<N_2;j++)
      if (st[j][k]==st[i][k])
       for (l=0;l<N_2;l++)
        if (st[i][k]&(1<<l))
         for (m=0;m<N_2;m++)
          if (m!=i&&m!=j&&(pos[l][m]&(1<<k)))
          {
           ret=true;
           left[l][m]--;
           pos[l][m]-=(1<<k);
          }
return ret;
}
void assume()//假设枚举过程
{
int i,j,k,cnt[N_2][N_2];
if (!can)
{
   can=true;
   while (true)
   {
    for (stack[top].k++;stack[top].k<=N_2&&!(stack[top].pos[stack[top].x][stack[top].y]&(1<<stack[top].k));stack[top].k++);
    if (stack[top].k!=N_2+1) break;
    top--;
   }
   memcpy(left,stack[top].left,sizeof(left));
   memcpy(map,stack[top].map,sizeof(map));
   memcpy(pos,stack[top].pos,sizeof(pos));
   sn=stack[top].sn;
   left[stack[top].x][stack[top].y]=1;
   pos[stack[top].x][stack[top].y]=(1<<stack[top].k);
}
else
{
   top++;
   memset(cnt,0,sizeof(cnt));
   memcpy(stack[top].left,left,sizeof(left));
   memcpy(stack[top].pos,pos,sizeof(pos));
   memcpy(stack[top].map,map,sizeof(map));
   stack[top].sn=sn;
   for (i=0;i<N_2;i++)
    for (j=0;j<N_2;j++)
     if (map[i][j]==EMP)
     {
      for (k=0;k<N_2;k++)
      {
       cnt[i][k]++;
       cnt[k][j]++;
       cnt[i/N*N+k/N][i%N*N+k%N]++;
      }
      cnt[i][j]-=3;
     }
   stack[top].x=stack[top].y=-1;
   for (i=0;i<N_2;i++)
    for (j=0;j<N_2;j++)
     if (map[i][j]==EMP&&(stack[top].x==-1||left[i][j]<left[stack[top].x][stack[top].y]||
      (left[stack[top].x][stack[top].y]==left[i][j]&&cnt[i][j]>cnt[stack[top].x][stack[top].y])))
     {
      stack[top].x=i;
      stack[top].y=j;
     }
   for (stack[top].k=1;!(stack[top].pos[stack[top].x][stack[top].y]&(1<<stack[top].k));stack[top].k++);
   pos[stack[top].x][stack[top].y]=(1<<stack[top].k);
   left[stack[top].x][stack[top].y]=1;
}
}
void Sudoku()
{
initial();
can=true;
while (true)
{
   if (check_unit()) return;
   if (!can)
   {
    assume();
    continue;
   }
   if (check_block()) continue;
   if (check_area()) continue;
   if (check_unit_pair()) continue;
   if (check_num_group()) continue;
   if (check_line_pair()) continue;
   assume();
}
}
int main()
{
scanf("%d",&ti);
while (ti--)
{
   for (i=0;i<N_2;i++)
    scanf("%s",map[i]);
   Sudoku();
   for (i=0;i<N_2;i++)
    printf("%s\n",map[i]);
}
return 0;
}