搜索(DLX)： POJ 3074 3076 Sudoku

POJ 3074 :

Description

In the game of Sudoku, you are given a large 9 × 9 grid divided into smaller 3 × 3 subgrids. For example,

. 2 7 3 8 . . 1 .

. 1 . . . 6 7 3 5

. . . . . . . 2 9

3 . 5 6 9 2 . 8 .

. . . . . . . . .

. 6 . 1 7 4 5 . 3

6 4 . . . . . . .

9 5 1 8 . . . 7 .

. 8 . . 6 5 3 4 .

Given some of the numbers in the grid, your goal is to determine the remaining numbers such that the numbers 1 through 9 appear exactly once in (1) each of nine 3 × 3 subgrids, (2) each of the nine rows, and (3) each of the nine columns.

Input

The input test file will contain multiple cases. Each test case consists of a single line containing 81 characters, which represent the 81 squares of the Sudoku grid, given one row at a time. Each character is either a digit (from 1 to 9) or a period (used to indicate an unfilled square). You may assume that each puzzle in the input will have exactly one solution. The end-of-file is denoted by a single line containing the word “end”.

Output

For each test case, print a line representing the completed Sudoku puzzle.

Sample Input
.2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534.
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end
Sample Output
527389416819426735436751829375692184194538267268174593643217958951843672782965341
416837529982465371735129468571298643293746185864351297647913852359682714128574936

POJ 3076：

Description

A Sudoku grid is a 16x16 grid of cells grouped in sixteen 4x4 squares, where some cells are filled with letters from A to P (the first 16 capital letters of the English alphabet), as shown in figure 1a. The game is to fill all the empty grid cells with letters from A to P such that each letter from the grid occurs once only in the line, the column, and the 4x4 square it occupies. The initial content of the grid satisfies the constraints mentioned above and guarantees a unique solution.

Write a Sudoku playing program that reads data sets from a text file.

Input

Each data set encodes a grid and contains 16 strings on 16 consecutive lines as shown in figure 2. The i-th string stands for the i-th line of the grid, is 16 characters long, and starts from the first position of the line. String characters are from the set {A,B,…,P,-}, where – (minus) designates empty grid cells. The data sets are separated by single empty lines and terminate with an end of file.

Output

The program prints the solution of the input encoded grids in the same format and order as used for input.

Sample Input
--A----C-----O-I
-J--A-B-P-CGF-H-
--D--F-I-E----P-
-G-EL-H----M-J--
----E----C--G---
-I--K-GA-B---E-J
D-GP--J-F----A--
-E---C-B--DP--O-
E--F-M--D--L-K-A
-C--------O-I-L-
H-P-C--F-A--B---
---G-OD---J----H
K---J----H-A-P-L
--B--P--E--K--A-
-H--B--K--FI-C--
--F---C--D--H-N-
Sample Output
FPAHMJECNLBDKOGI
OJMIANBDPKCGFLHE
LNDKGFOIJEAHMBPC
BGCELKHPOFIMAJDN
MFHBELPOACKJGNID
CILNKDGAHBMOPEFJ
DOGPIHJMFNLECAKB
JEKAFCNBGIDPLHOM
EBOFPMIJDGHLNKCA
NCJDHBAEKMOFIGLP
HMPLCGKFIAENBDJO
AKIGNODLBPJCEFMH
KDEMJIFNCHGAOPBL
GLBCDPMHEONKJIAF
PHNOBALKMJFIDCEG
IAFJOECGLDPBHMNK

　　这两道题几乎一样的，就是要你求一个数独矩阵。

　　难得有这样一道接近生活的信息题啊~~~

POJ 3074：

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 using namespace std;
  5 const int maxnode=100010;
  6 const int maxn=755;
  7 const int maxm=345;
  8 struct DLX
  9 {
 10     int L[maxnode],R[maxnode],U[maxnode],D[maxnode],Row[maxnode],Col[maxnode],C[maxm],H[maxn],cnt;
 11     bool used[maxn];
 12     void Init(int n,int m)
 13     {
 14         for(int i=0;i<=m;i++)
 15         {
 16             L[i]=i-1;R[i]=i+1;
 17             U[i]=D[i]=i;C[i]=0;
 18         }
 19         cnt=m;L[0]=m;R[m]=0;
 20 
 21         for(int i=1;i<=n;i++)
 22             H[i]=0,used[i]=false;
 23     }
 24     void Link(int x,int y)
 25     {
 26         C[Col[++cnt]=y]++;
 27         Row[cnt]=x;
 28 
 29         U[cnt]=y;
 30         U[D[y]]=cnt;
 31         D[cnt]=D[y];
 32         D[y]=cnt;
 33 
 34         if(H[x])
 35             L[R[H[x]]]=cnt,R[cnt]=R[H[x]],R[H[x]]=cnt,L[cnt]=H[x];
 36         else
 37             H[x]=L[cnt]=R[cnt]=cnt;
 38     }
 39 
 40     void Delete(int c)
 41     {
 42         L[R[c]]=L[c];R[L[c]]=R[c];
 43         for(int i=D[c];i!=c;i=D[i])
 44             for(int j=R[i];j!=i;j=R[j])
 45                 --C[Col[j]],U[D[j]]=U[j],D[U[j]]=D[j];
 46     }
 47 
 48     void Resume(int c)
 49     {
 50         L[R[c]]=c;R[L[c]]=c;
 51         for(int i=U[c];i!=c;i=U[i])
 52             for(int j=L[i];j!=i;j=L[j])
 53                 ++C[Col[j]],U[D[j]]=j,D[U[j]]=j;
 54     }
 55 
 56     bool Solve()
 57     {
 58         if(!R[0])return true;
 59         int p=R[0];
 60         for(int i=R[p];i;i=R[i])
 61             if(C[p]>C[i])
 62                 p=i;
 63         Delete(p);
 64         for(int i=D[p];i!=p;i=D[i]){
 65             used[Row[i]]=true;
 66             for(int j=R[i];j!=i;j=R[j])
 67                 Delete(Col[j]);
 68             if(Solve())
 69                 return true;
 70             used[Row[i]]=false;
 71             for(int j=L[i];j!=i;j=L[j])
 72                 Resume(Col[j]);
 73         }
 74         Resume(p);
 75         return false;
 76     }
 77     void Print()
 78     {
 79         for(int i=1;i<=81;i++)
 80             for(int j=(i-1)*9+1;j<=i*9;j++)
 81                 if(used[j]){
 82                     int Color=j-(i-1)*9;
 83                     printf("%d",Color);
 84                 }
 85         printf("
");        
 86     }
 87 }DLX;
 88 
 89 int Area(int x,int y)
 90 {
 91     if(x<=3&&y<=3)return 0;
 92     if(x<=3&&y<=6)return 1;
 93     if(x<=3)return 2;
 94     if(x<=6&&y<=3)return 3;
 95     if(x<=6&&y<=6)return 4;
 96     if(x<=6)return 5;
 97     if(y<=3)return 6;
 98     if(y<=6)return 7;
 99     return 8;
100 }
101 
102 char str[110];
103 int main()
104 {
105     int x,y;
106     while(~scanf("%s",str+1))
107     {
108         if(!strcmp(str+1,"end"))break;
109         DLX.Init(729,324);x=1;y=1;
110         for(int i=1;i<=81;i++)
111         {
112             for(int j=(i-1)*9+1;j<=i*9;j++)
113             {
114                 int Color=j-(i-1)*9;
115                 if(str[i]!='.'&&str[i]-'0'!=Color)
116                     continue;
117 
118                 DLX.Link(j,(x-1)*9+Color); //行中对应颜色
119                 DLX.Link(j,81+(y-1)*9+Color); //列中对应颜色 
120                 DLX.Link(j,162+Area(x,y)*9+Color);//块中对应颜色 
121                 DLX.Link(j,243+i); //矩阵中对应位置
122             }
123             y++;x+=y/10;y=(y-1)%9+1;
124         }
125         DLX.Solve();
126         DLX.Print();
127     }
128     return 0;
129 }

POJ 3076：

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 using namespace std;
  5 const int maxnode=500010;
  6 const int maxn=4100;
  7 const int maxm=1030;
  8 struct DLX
  9 {
 10     int L[maxnode],R[maxnode],U[maxnode],D[maxnode],Row[maxnode],Col[maxnode],C[maxm],H[maxn],cnt;
 11     bool used[maxn];
 12     void Init(int n,int m)
 13     {
 14         for(int i=0;i<=m;i++)
 15         {
 16             L[i]=i-1;R[i]=i+1;
 17             U[i]=D[i]=i;C[i]=0;
 18         }
 19         cnt=m;L[0]=m;R[m]=0;
 20 
 21         for(int i=1;i<=n;i++)
 22             H[i]=0,used[i]=false;
 23     }
 24     void Link(int x,int y)
 25     {
 26         C[Col[++cnt]=y]++;
 27         Row[cnt]=x;
 28 
 29         U[cnt]=y;
 30         U[D[y]]=cnt;
 31         D[cnt]=D[y];
 32         D[y]=cnt;
 33 
 34         if(H[x])
 35             L[R[H[x]]]=cnt,R[cnt]=R[H[x]],R[H[x]]=cnt,L[cnt]=H[x];
 36         else
 37             H[x]=L[cnt]=R[cnt]=cnt;
 38     }
 39 
 40     void Delete(int c)
 41     {
 42         L[R[c]]=L[c];R[L[c]]=R[c];
 43         for(int i=D[c];i!=c;i=D[i])
 44             for(int j=R[i];j!=i;j=R[j])
 45                 --C[Col[j]],U[D[j]]=U[j],D[U[j]]=D[j];
 46     }
 47 
 48     void Resume(int c)
 49     {
 50         L[R[c]]=c;R[L[c]]=c;
 51         for(int i=U[c];i!=c;i=U[i])
 52             for(int j=L[i];j!=i;j=L[j])
 53                 ++C[Col[j]],U[D[j]]=j,D[U[j]]=j;
 54     }
 55 
 56     bool Solve()
 57     {
 58         if(!R[0])return true;
 59         int p=R[0];
 60         for(int i=R[p];i;i=R[i])
 61             if(C[p]>C[i])
 62                 p=i;
 63         Delete(p);
 64         for(int i=D[p];i!=p;i=D[i]){
 65             used[Row[i]]=true;
 66             for(int j=R[i];j!=i;j=R[j])
 67                 Delete(Col[j]);
 68             if(Solve())
 69                 return true;
 70             used[Row[i]]=false;
 71             for(int j=L[i];j!=i;j=L[j])
 72                 Resume(Col[j]);
 73         }
 74         Resume(p);
 75         return false;
 76     }
 77     void Print()
 78     {
 79         for(int i=1;i<=256;i++){
 80             for(int j=(i-1)*16+1;j<=i*16;j++)
 81                 if(used[j]){
 82                     int Color=j-(i-1)*16;
 83                     printf("%c",'A'+Color-1);
 84                     break;
 85                 }
 86             if(i%16==0)
 87                 printf("
");    
 88         }
 89         printf("
");
 90     }
 91 }DLX;
 92 
 93 int Area(int x,int y)
 94 {
 95     if(x<=4&&y<=4)return 0;
 96     if(x<=4&&y<=8)return 1;
 97     if(x<=4&&y<=12)return 2;
 98     if(x<=4)return 3;
 99     
100     if(x<=8&&y<=4)return 4;
101     if(x<=8&&y<=8)return 5;
102     if(x<=8&&y<=12)return 6;
103     if(x<=8)return 7;
104     
105     if(x<=12&&y<=4)return 8;
106     if(x<=12&&y<=8)return 9;
107     if(x<=12&&y<=12)return 10;
108     if(x<=12)return 11;
109     
110     if(y<=4)return 12;
111     if(y<=8)return 13;
112     if(y<=12)return 14;
113     return 15;
114 }
115 
116 char str[260],s[17];
117 int main()
118 {
119     while(true){
120         int x=1,y=1;
121         DLX.Init(4096,1024);
122         for(int i=1;i<256;i+=16){
123             if(not~scanf("%s",s))return 0;
124             for(int j=i;j<i+16;j++)
125                 str[j]=s[j-i];
126         }
127         for(int i=1;i<=256;i++)
128         {
129             for(int j=(i-1)*16+1;j<=i*16;j++)
130             {
131                 int Color=j-(i-1)*16;
132                 if(str[i]!='-'&&str[i]-'A'+1!=Color)
133                     continue;
134     
135                 DLX.Link(j,(x-1)*16+Color); //行中对应颜色
136                 DLX.Link(j,256+(y-1)*16+Color); //列中对应颜色 
137                 DLX.Link(j,512+Area(x,y)*16+Color);//块中对应颜色 
138                 DLX.Link(j,768+i); //矩阵中对应位置
139             }
140             y++;x+=y/17;y=(y-1)%16+1;
141         }
142         DLX.Solve();
143         DLX.Print();
144     }
145     return 0;
146 }

尽最大的努力，做最好的自己！

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

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

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