首页 > 代码库 > POJ 3076 数独（DLX算法）
POJ 3076 数独（DLX算法）
Sudoku
| Time Limit: 10000MS | Memory Limit: 65536K | |
| Total Submissions: 4439 | Accepted: 2160 |
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.
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-JD-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----HK---J----H-A-P-L--B--P--E--K--A--H--B--K--FI-C----F---C--D--H-N-
Sample Output
FPAHMJECNLBDKOGIOJMIANBDPKCGFLHELNDKGFOIJEAHMBPCBGCELKHPOFIMAJDNMFHBELPOACKJGNIDCILNKDGAHBMOPEFJDOGPIHJMFNLECAKBJEKAFCNBGIDPLHOMEBOFPMIJDGHLNKCANCJDHBAEKMOFIGLPHMPLCGKFIAENBDJOAKIGNODLBPJCEFMHKDEMJIFNCHGAOPBLGLBCDPMHEONKJIAFPHNOBALKMJFIDCEGIAFJOECGLDPBHMNK
题目意思：
给出一个16*16数独，平时的数独是数字，而这个是A--P字母组成，16*16的格子又分成16个4*4的块，要求用A--P填充给出格子中‘-’的部分，使得大块中每行每列都有A--P，且不重复，每个小块中也是A--P不重复，输出填充好的块。
思路：
DLX模板题了，建完图后贴模板就行了。
代码：
1 #include<cstdio> 2 #include<cstring> 3 #define N 4099 4 #define M 1029 5 6 const int m=4,n=16; 7 int tt,H=4*n*n,cnt,size[M],ans[20][20]; 8 //char str[100]; 9 10 struct Node 11 { 12 int r,c; 13 Node *U,*D,*L,*R; 14 }node[N*M],row[N],col[M],head; 15 16 void init(int r,int c) 17 { 18 int i; 19 cnt=0; 20 head.r=r; 21 head.c=c; 22 head.L=head.R=head.U=head.D=&head; 23 for(i=0;i<c;i++) 24 { 25 col[i].r=r; 26 col[i].c=i; 27 col[i].L=&head; 28 col[i].R=head.R; 29 col[i].U=col[i].D=col[i].L->R=col[i].R->L=&col[i]; 30 size[i]=0; 31 } 32 for(i=r-1;i>=0;i--) 33 { 34 row[i].r=i; 35 row[i].c=c; 36 row[i].U=&head; 37 row[i].D=head.D; 38 row[i].L=row[i].R=row[i].U->D=row[i].D->U=&row[i]; 39 } 40 } 41 42 void insert(int r,int c) 43 { 44 Node *p=&node[cnt++]; 45 p->r=r; 46 p->c=c; 47 p->R=&row[r]; 48 p->L=row[r].L; 49 p->L->R=p->R->L=p; 50 p->U=&col[c]; 51 p->D=col[c].D; 52 p->U->D=p->D->U=p; 53 ++size[c]; 54 } 55 void delLR(Node *p) 56 { 57 p->L->R=p->R; 58 p->R->L=p->L; 59 } 60 void delUD(Node *p) 61 { 62 p->U->D=p->D; 63 p->D->U=p->U; 64 } 65 66 void resumeLR(Node *p) 67 {p->L->R=p->R->L=p;} 68 69 void resumeUD(Node *p) 70 {p->U->D=p->D->U=p;} 71 72 void cover(int c) 73 { 74 if(c==H) 75 return; 76 Node *R,*C; 77 delLR(&col[c]); 78 for(C=col[c].D;C!=&col[c];C=C->D) 79 for(R=C->L;R!=C;R=R->L) 80 { 81 --size[R->c]; 82 delUD(R); 83 } 84 } 85 void resume(int c) 86 { 87 if(c==H) 88 return; 89 Node *R,*C; 90 for(C=col[c].U;C!=&col[c];C=C->U) 91 for(R=C->R;R!=C;R=R->R) 92 { 93 ++size[R->c]; 94 resumeUD(R); 95 } 96 resumeLR(&col[c]); 97 } 98 int num,tar,block[20][20]; 99 char map[N][N];100 101 int dfs(int k) 102 { 103 if(head.L==&head) 104 { 105 num++; 106 if(num)107 return 1; 108 return 0; 109 } 110 int INF=-1u>>1,r,c=-1; 111 Node *p,*rc; 112 for(p=head.L;p!=&head;p=p->L) 113 if(size[p->c]<INF) 114 INF=size[c=p->c]; 115 if(!INF) 116 return 0; 117 cover(c); 118 for(p=col[c].D;p!=&col[c];p=p->D) 119 { 120 for(rc=p->L;rc!=p;rc=rc->L) 121 cover(rc->c); 122 r=p->r-1; 123 if(num==0) 124 ans[r/(n*n)][r/n%n]=r%n; 125 if(dfs(k+1)) 126 return 1; 127 for(rc=p->R;rc!=p;rc=rc->R) 128 resume(rc->c); 129 } 130 resume(c); 131 return 0; 132 } 133 134 void insert(int i,int j,int k) 135 { 136 int r=(i*n+j)*n+k; 137 insert(r,i*n+k-1); 138 insert(r,n*n+j*n+k-1); 139 insert(r,2*n*n+block[i][j]*n+k-1); 140 insert(r,3*n*n+i*n+j); 141 } 142 void Sudoku() 143 { 144 int i,j,k; 145 init(n*n*n+1,H); 146 k=0;147 for(i=1;i<n;i++) 148 scanf("%s",map[i]);149 150 151 num=0; 152 for(i=0;i<n;i++) 153 for(j=0;j<n;j++) {154 if(i<4&&j<4){155 block[i][j]=0;156 }157 else if(i<4&&j<8){158 block[i][j]=1;159 }160 else if(i<4&&j<12){161 block[i][j]=2;162 }163 else if(i<4&&j<16){164 block[i][j]=3;165 }166 else if(i<8&&j<4){167 block[i][j]=4;168 }169 else if(i<8&&j<8){170 block[i][j]=5;171 }172 else if(i<8&&j<12){173 block[i][j]=6;174 }175 else if(i<8&&j<16){176 block[i][j]=7;177 }178 else if(i<12&&j<4){179 block[i][j]=8;180 }181 else if(i<12&&j<8){182 block[i][j]=9;183 }184 else if(i<12&&j<12){185 block[i][j]=10;186 }187 else if(i<12&&j<16){188 block[i][j]=11;189 }190 else if(i<16&&j<4){191 block[i][j]=12;192 }193 else if(i<16&&j<8){194 block[i][j]=13;195 }196 else if(i<16&&j<12){197 block[i][j]=14;198 }199 else if(i<16&&j<16){200 block[i][j]=15;201 }202 }203 for(i=0;i<n;i++) 204 for(j=0;j<n;j++) 205 { 206 if(map[i][j]!=‘-‘) 207 insert(i,j,map[i][j]-‘A‘+1); 208 else 209 for(k=1;k<=n;k++) 210 insert(i,j,k); 211 } 212 num=0; 213 dfs(0); 214 215 216 for(i=0;i<n;i++) 217 { 218 for(j=0;j<n;j++) 219 printf("%c",(char)ans[i][j]+‘A‘); 220 printf("\n");221 } 222 printf("\n");223 } 224 int main() 225 { 226 int t; 227 while(scanf("%s",map[0])!=EOF)228 Sudoku(); 229 230 }
POJ 3076 数独（DLX算法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。