数独问题的研究---【附注】POJ 2676 解题报告

被人bs的感觉真的很不爽啊。

对于这道题，主要是不明白转换的问题。
看了czyuan给的源程序，确切的是，我并没有看完，看了怎么转换的就已经很明白了 czyuan给的代码的作者看来功力非凡的，能把在我看来是很difficult的问题，一个式子就给OK了。
就是怎样从每一个小方格定位到每一个小方块区域的问题：

1、mg[i][j]定位方法：i/3*3+j/3 就这一个式子就OK了。真是佩服，其实这个东西用代码应该很容易想出来的，无奈，也许是人老了吧。
2、另一个需要注意的是每一个小方格本身的定位可以用i*9+j来唯一的标识，这个比较简单，每一个人只要不傻就能看出来。
3、还有就是，可以把每一个需要填写的数字用数组保存起来，这样的优点也很明显，以后在DFS的时候，不用在到mg[][]里面瞎逛了。

给我拍块砖吧，我现在真是不行了吧

Source Code

Problem: 2676		User: omycle
Memory: 268K		Time: 532MS
Language: C++		Result: Accepted

• Source Code
  

  #include <iostream>
  using namespace std;
  int mg[9][9];
  /*
  int mg[9][9]={1,0,3,0,0,0,5,0,9,\
  0,0,2,1,0,9,4,0,0,\
  0,0,0,7,0,4,0,0,0,\
  3,0,0,5,0,2,0,0,6,\
  0,6,0,0,0,0,0,5,0,\
  7,0,0,8,0,3,0,0,4,\
  0,0,0,4,0,1,0,0,0,\
  0,0,9,2,0,5,8,0,0,\
  8,0,4,0,0,0,1,0,7};
  */
  bool flagrow[10][10];//给每一行都开了1～9
  bool flagcol[10][10];//每一列的都开了1～9
  bool flagz[10][10];//给每个小单元格开了1~9 ，每一行代表一个小单元格
  int shuzu[81];//保存的是从第一行第一列开始的所有为0的单元格的位置，的是从1－81
  bool flag=false;
  int TotalCount=0;//总的个数
  void Init()
  {
  memset(flagrow,false,sizeof(flagrow));
  memset(flagcol,false,sizeof(flagcol));
  memset(flagz,false,sizeof(flagz));
  memset(shuzu,0,sizeof(shuzu));
  int c=0;
  for(int i=0;i<9;i++)
  {
  for(int j=0;j<9;j++)
  {
  if(mg[i][j]==0)
  {
      shuzu[c++]=i*9+j;//把每一个位置保存下来－－经过了一下加工，这样很省空间滴！再为我的聪明鼓掌！
  }
  else
  {
      flagrow[i][mg[i][j]]=true;//把每一行的flag处理好
      flagcol[mg[i][j]][j]=true;//把每一列的flag处理好
      flagz[(i/3)*3+(j/3)][mg[i][j]]=true;//把每一个单元格的flag也处理好
  /*hah,其实，我还是很聪明的啊～*/
  }
  }
  }
   TotalCount=c-1;
  }
  void Sousuo(int i)
  {
  if(i>TotalCount)
  {
    flag=true;
  return ;
  }
  int temp=shuzu[i];//取一个值出来
  int row=temp/9;
  int col=temp%9;//将行列值变幻了过来，哈哈
  for(int num=1;num<=9;num++)
  {//如果，行列，及小方格中没有这个数值，那么就填进去，如果有，就算了啊，试试其他的呵呵。
  if(flagrow[row][num])
  continue;
  if(flagcol[num][col])
  continue;
  if(flagz[(row/3)*3+(col/3)][num])
  continue;
    mg[row][col]=num;
    flagrow[row][num]=true;
    flagcol[num][col]=true;
    flagz[(row/3)*3+(col/3)][num]=true;
  Sousuo(i+1);
  if(flag)
  break;
    mg[row][col]=0;
    flagrow[row][num]=false;
    flagcol[num][col]=false;
    flagz[(row/3)*3+(col/3)][num]=false;
  }
  }
  int main()
  {
  int n;
   cin>>n;
  char a[9];
  while(n--)
  {
  int i=0;
  for(i=0;i<9;i++)
  {
     cin>>a;
  for(int j=0;j<9;j++)
  {
      mg[i][j]=a[j]-'0';
  }
  }
    flag=false;
  Init();
  Sousuo(0);
  for(i=0;i<9;i++)
  {
  for(int j=0;j<9;j++)
  {
      cout<<mg[i][j];
  }
     cout<<endl;
  }
  }
  return 1;
  }