4.3.4 Sudoku Killer

Problem Description

自从2006年3月10日至11日的首届数独世界锦标赛以后，数独这项游戏越来越受到人们的喜爱和重视。
据说，在2008北京奥运会上，会将数独列为一个单独的项目进行比赛，冠军将有可能获得的一份巨大的奖品———HDU免费七日游外加lcy亲笔签名以及同hdu acm team合影留念的机会。
所以全球人民前仆后继，为了奖品日夜训练茶饭不思。当然也包括初学者linle，不过他太笨了又没有多少耐性，只能做做最最基本的数独题，不过他还是想得到那些奖品，你能帮帮他吗？你只要把答案告诉他就可以，不用教他是怎么做的。

数独游戏的规则是这样的：在一个9x9的方格中，你需要把数字1-9填写到空格当中，并且使方格的每一行和每一列中都包含1-9这九个数字。同时还要保证，空格中用粗线划分成9个3x3的方格也同时包含1-9这九个数字。比如有这样一个题，大家可以仔细观察一下，在这里面每行、每列，以及每个3x3的方格都包含1-9这九个数字。

例题：

答案：

Input

本题包含多组测试，每组之间由一个空行隔开。每组测试会给你一个 9*9 的矩阵，同一行相邻的两个元素用一个空格分开。其中1-9代表该位置的已经填好的数，问号（?）表示需要你填的数。

Output

对于每组测试，请输出它的解，同一行相邻的两个数用一个空格分开。两组解之间要一个空行。
对于每组测试数据保证它有且只有一个解。

Sample Input

7 1 2 ? 6 ? 3 5 8
? 6 5 2 ? 7 1 ? 4
? ? 8 5 1 3 6 7 2
9 2 4 ? 5 6 ? 3 7
5 ? 6 ? ? ? 2 4 1
1 ? 3 7 2 ? 9 ? 5
? ? 1 9 7 5 4 8 6
6 ? 7 8 3 ? 5 1 9
8 5 9 ? 4 ? ? 2 3

Sample Output

7 1 2 4 6 9 3 5 8
3 6 5 2 8 7 1 9 4
4 9 8 5 1 3 6 7 2
9 2 4 1 5 6 8 3 7
5 7 6 3 9 8 2 4 1
1 8 3 7 2 4 9 6 5
2 3 1 9 7 5 4 8 6
6 4 7 8 3 2 5 1 9
8 5 9 6 4 1 7 2 3

Author

linle

Source

ACM暑期集训队练习赛（三）

Recommend

思路：dfs

好慢啊我写的，本来是排序想加快点速度，结果没想到更慢了！

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 using namespace std;
  5 
  6 struct qq
  7 {
  8     int x,y,tot;
  9     bool friend operator < (const qq &a,const qq &b)
 10     {
 11         return a.tot<b.tot;
 12     }
 13 } b[90];
 14 
 15 char s[10][10][2];
 16 int a[10][10];
 17 int n,cnt=0,x1,x2,y1,y2,amount=0,num=0;
 18 
 19 bool judge(int now,int k)
 20 {
 21 for (int i=1;i<=9;i++)
 22 {
 23     if (a[b[now].x][i]==k) return false;  //横
 24     if (a[i][b[now].y]==k) return false;  //竖
 25 }
 26 x1=(b[now].x-1)/3; y1=(b[now].y-1)/3; // 九宫格左上角的坐标
 27 x2=x1*3+1; y2=y1*3+1;
 28 for (int i=x2;i<=x2+2;i++)
 29 {
 30    for (int j=y2;j<=y2+2;j++)
 31    {
 32         if (a[i][j]==k) return false;
 33     }
 34 }
 35 return true;
 36 }
 37 
 38 void dfs(int k)
 39 {
 40 if (k==cnt+1)
 41 {
 42     if (num==cnt)
 43     {
 44     for (int i=1;i<=9;i++)
 45              {
 46                  for (int j=1;j<=8;j++)
 47                  {
 48                      printf("%d ",a[i][j]);
 49                  }
 50                 printf("%d\n",a[i][9]);
 51              }
 52     }
 53    return ;
 54 }
 55     for (int i=1;i<=9;i++)
 56     {
 57         if (judge(k,i))
 58         {
 59             a[b[k].x][b[k].y]=i;
 60             num++;
 61             dfs(k+1);
 62             num--;
 63             a[b[k].x][b[k].y]=0;
 64         }
 65     }
 66 }
 67 
 68 
 69 void init()
 70 {
 71 int x=1,y=1,case1=0;;
 72     while (scanf("%s",s[x][y])!=EOF)
 73      {
 74          y++; amount++; 
 75          memset(b,0,sizeof(b));
 76          if (y==10) { x++; y=1; }
 77          if (amount==81)
 78          {
 79             if (case1!=0) printf("\n");
 80             case1++;
 81              amount=0; num=0;
 82              for (int i=1;i<=9;i++)
 83              {
 84                  for (int j=1;j<=9;j++)
 85                  {
 86                      if (s[i][j][0]=='?')
 87                      {
 88                          a[i][j]=0;
 89                      }
 90                      else a[i][j]=s[i][j][0]-48;
 91                  }
 92              }
 93              for (int i=1;i<=9;i++)
 94              {
 95                  for (int j=1;j<=9;j++)
 96                  {
 97                      if (s[i][j][0]=='?')
 98                      {
 99                          cnt++;
100                          b[cnt].x=i; b[cnt].y=j;
101                          for (int k=1;k<=9;k++)
102                          {
103                              if (judge(cnt,k))
104                                b[cnt].tot++;
105                          }
106                      }
107                  }
108               }
109          sort(b+1,b+cnt+1);
110          dfs(1);
111          cnt=0;
112          x=1,y=1;
113          }
114     }
115 }                
116 
117 int main ()
118 {
119 
120 init();
121 return 0;
122 }