51isoft's ACM Journey

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  5 随笔 :: 0 文章 :: 0 评论 :: 0 Trackbacks
Sudoku
Time Limit: 10000MS
Memory Limit: 65536K
Total Submissions: 638
Accepted: 304

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

Source




题意就是数独啦,数独可以转换成n*n*n行4*n*n列的精确覆盖问题。
每一行对应每一格的一种填法
每一列代表一个状态(类似于八皇后里面的行、列、斜)

9行,每行9个数的状态——》81
9列——》81
9块——》81
81个格,每格只能有一个数——》81
所以列数为n*n*4。

对应每一格每一种填法,必定覆盖某4列(行、列、区域、格子)
用DLX过了一堆数独…………

  1 #include <stdio.h>
  2 #include <string.h>
  3 
  4 const int n=16;
  5 const int len=4;
  6 
  7 const int maxrow=n*n*n; //row, col, value
  8 const int maxcol=4*n*n; //row, col, block, cell
  9 
 10 struct Node {
 11     int row,col,num;
 12     Node *left, *right, *up, *down;
 13 };
 14 
 15 Node head,row[maxrow+10],col[maxcol+10],node[maxrow*maxcol+2000];
 16 int nodenum;
 17 int count[maxcol+10];
 18 int result[maxrow+10];
 19 char temp[2000];
 20 
 21 void linkinit()
 22 {
 23     memset(count,0,sizeof(count));
 24     nodenum=0;
 25     head.col=head.row=0;
 26     head.right=head.left=head.up=head.down=&head;
 27     for (int i=0;i<maxcol;i++) {
 28         col[i].left=head.left;
 29         head.left=&col[i];
 30         col[i].right=&head;
 31         col[i].num=0;
 32         col[i].col=i;
 33         col[i].up=col[i].down=&col[i];
 34         col[i].left->right=&col[i];col[i].right->left=&col[i];
 35     }
 36     for (int i=0;i<maxrow;i++) {
 37         row[i].up=head.up;
 38         head.up=&row[i];
 39         row[i].row=i;
 40         row[i].down=&head;
 41         row[i].left=row[i].right=&row[i];
 42         row[i].up->down=&row[i];row[i].down->up=&row[i];
 43     }
 44 }
 45 
 46 void link(int r,int c,int num,int coln)
 47 {
 48     int rown=r*n*n+c*n+num;
 49     count[coln]++;
 50     node[nodenum].row=rown;node[nodenum].col=coln;
 51     node[nodenum].up=&col[coln];
 52     node[nodenum].down=col[coln].down;
 53     col[coln].down->up=&node[nodenum];
 54     col[coln].down=&node[nodenum];
 55     node[nodenum].left=&row[rown];
 56     node[nodenum].right=row[rown].right;
 57     row[rown].right->left=&node[nodenum];
 58     row[rown].right=&node[nodenum];
 59     nodenum++;
 60 }
 61 
 62 void removerowhead()
 63 {
 64     for (int i=0;i<maxrow;i++) {
 65         row[i].left->right=row[i].right;
 66         row[i].right->left=row[i].left;
 67     }
 68 }
 69 
 70 void remove(int coln)
 71 {
 72     col[coln].left->right=col[coln].right;
 73     col[coln].right->left=col[coln].left;
 74     for (Node * curr=col[coln].down;curr!=&col[coln];curr=curr->down)
 75     {
 76         for (Node * tmp=curr->right;tmp!=curr;tmp=tmp->right)
 77         {
 78             count[tmp->col]--;
 79             tmp->up->down=tmp->down;
 80             tmp->down->up=tmp->up;
 81         }
 82         curr->left->right=curr->right;
 83         curr->right->left=curr->left;
 84     }
 85 }
 86 
 87 void resume(int coln)
 88 {
 89     for (Node * curr=col[coln].down;curr!=&col[coln];curr=curr->down)
 90     {
 91         curr->right->left=curr;
 92         curr->left->right=curr;
 93         for (Node * tmp=curr->left;tmp!=curr;tmp=tmp->left)
 94         {
 95             tmp->up->down=tmp;
 96             tmp->down->up=tmp;
 97             count[tmp->col]++;
 98         }
 99     }
100     col[coln].left->right=&col[coln];
101     col[coln].right->left=&col[coln];
102 }
103 
104 bool solve(int k)
105 {
106     if (head.right==&head) return true;
107     int min=2*n,rec;
108     for (Node * curr=head.right;curr!=&head;curr=curr->right) {
109         if (min>count[curr->col]) {
110             min=count[curr->col];
111             rec=curr->col;
112             if (min<=1break;
113         }
114     }
115     if (min==0return false;
116     remove(rec);
117     for (Node * curr=col[rec].down;curr!=&col[rec];curr=curr->down) {
118         result[k]=curr->row;
119         curr->left->right=curr;
120         for (Node * tmp=curr->right;tmp!=curr;tmp=tmp->right) {
121             remove(tmp->col);
122         }
123         curr->left->right=curr->right;
124         if (solve(k+1)) return true;
125         curr->right->left=curr;
126         for (Node * tmp=curr->left;tmp!=curr;tmp=tmp->left)
127         {
128             resume(tmp->col);
129         }
130         curr->right->left=curr->left;
131     }
132     resume(rec);
133     return false;
134 }
135 
136 void probinit()
137 {
138     int r,c,b;
139     for (int i=0;i<n*n;i++) {
140         r=i/n;c=i%n;b=(r/len)*len+(c/len);
141         if (temp[i]=='-') {
142             for (int j=0;j<n;j++) {
143                 link(r,c,j,r*n+j);//row
144                 link(r,c,j,n*n+c*n+j);//column
145                 link(r,c,j,n*n*2+b*n+j);//block
146                 link(r,c,j,n*n*3+i);//cell
147             }
148         }
149         else {
150             int j=temp[i]-'A';
151             link(r,c,j,r*n+j);//row
152             link(r,c,j,n*n+c*n+j);//column
153             link(r,c,j,n*n*2+b*n+j);//block
154             link(r,c,j,n*n*3+i);//cell
155         }
156     }
157 }
158 
159 void printres()
160 {
161     int r,c,num;
162     int numb[n*n+10]={0};
163     for (int i=0;i<n*n;i++)
164     {
165         r=result[i]/(n*n);
166         c=(result[i]-r*n*n)/n;
167         num=result[i]%n;
168         numb[r*n+c]=num+1;
169     }
170     for (int i=0;i<n*n;i++) {
171         printf("%c",numb[i]+'A'-1);
172         if ((i+1)%n==0) printf("\n");
173     }
174     printf("\n");
175 }
176 
177 int main()
178 {
179     char tmpp[100];
180     while(scanf("%s",tmpp)!=EOF)
181     {
182         memset(temp,0,sizeof(temp));
183         strcat(temp,tmpp);
184         for (int i=1;i<n;i++) {
185             scanf("%s",tmpp);
186             strcat(temp,tmpp);
187         }
188         linkinit();
189         probinit();
190         removerowhead();
191         solve(0);
192         printres();
193     }
194     return 0;
195 }
196 



posted on 2009-07-28 02:37 51isoft 阅读(1710) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理