[POJ 2676] Sudoku【DLX】
Problem:
Time Limit: 2000MS | Memory Limit: 65536K | Special Judge |
Description

Input
Output
Sample Input
1 103000509 002109400 000704000 300502006 060000050 700803004 000401000 009205800 804000107
Sample Output
143628579 572139468 986754231 391542786 468917352 725863914 237481695 619275843 854396127
Source
Solution:
一道经典的搜索 DLX。
我们将数独转换为精确覆盖模型:
- 9 行 9 列中每格有且只有一个数 ⇒ 第 1 ~ 81 列
- 9 行中每行有且只有各一个 1 ~ 9 ⇒ 第 82 ~ 162 列
- 9 列中每列有且只有各一个 1 ~ 9 ⇒ 第 163 ~ 243 列
- 9 宫中每宫有且只有各一个 1 ~ 9 ⇒ 第 244 ~ 324 列
对于每个已确定的格子,插入 1 行,共 4 列,分别对应上述四个条件。
否则插入 9 行,每行 4 列,对应四个条件中分别填入 1 ~ 9 的情况。
用 Dancing Links 对这个至多 729 行 324 列 2916 个点的矩阵求精确覆盖即可。
详解可参考:http://blog.csdn.net/bl0ss0m/article/details/17918705。
这种方法一眨眼就能解出世界最难数独哦 ~~ ^O^ ~~
还有,POJ 这道题数据实在太弱了,写错了交上去还是 AC 的。。
Code: O(玄学) [828K, 0MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<cassert> #include<iostream> #include<algorithm> using namespace std; const int pal[10][10] = { {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 1, 1, 2, 2, 2, 3, 3, 3}, {0, 1, 1, 1, 2, 2, 2, 3, 3, 3}, {0, 1, 1, 1, 2, 2, 2, 3, 3, 3}, {0, 4, 4, 4, 5, 5, 5, 6, 6, 6}, {0, 4, 4, 4, 5, 5, 5, 6, 6, 6}, {0, 4, 4, 4, 5, 5, 5, 6, 6, 6}, {0, 7, 7, 7, 8, 8, 8, 9, 9, 9}, {0, 7, 7, 7, 8, 8, 8, 9, 9, 9}, {0, 7, 7, 7, 8, 8, 8, 9, 9, 9} }; inline int getgrid(){ char ch; while(!isdigit(ch = getchar())); return ch - '0'; } int T, sdk[10][10]; int col[5]; struct Dancing_Link{ int S[5000], C[5000]; int U[5000], D[5000], L[5000], R[5000]; int topv; int x[5000], y[5000], v[5000]; inline void init(const int &col_num){ topv = col_num; memset(S, 0, sizeof(S)); for(register int i = 0; i <= col_num; i++) C[i] = U[i] = D[i] = i, L[i] = i - 1, R[i] = i + 1; L[0] = col_num, R[col_num] = 0; } inline void del(const int &c){ L[R[c]] = L[c], R[L[c]] = R[c]; for(register int i = D[c]; i != c; i = D[i]) for(register int j = R[i]; j != i; j = R[j]) U[D[j]] = U[j], D[U[j]] = D[j], S[C[j]]--; } inline void add(const int &c){ L[R[c]] = R[L[c]] = c; for(register int i = U[c]; i != c; i = U[i]) for(register int j = L[i]; j != i; j = L[j]) U[D[j]] = D[U[j]] = j, S[C[j]]++; } inline void addline(int *col, const int &col_size, const int &_row, const int &_col, const int &_val){ if(!col_size) return; // There may be empty lines for(register int i = 1; i <= col_size; i++){ int &c = col[i]; C[++topv] = c; L[topv] = topv - 1, R[topv] = topv + 1; U[topv] = U[c], D[U[c]] = topv; D[topv] = c, U[c] = topv; S[c]++; x[topv] = _row, y[topv] = _col, v[topv] = _val; // Record the original information } L[topv - col_size + 1] = topv, R[topv] = topv - col_size + 1; } inline void addstatus(const int &_row, const int &_col, const int &_val){ col[1] = (_row - 1) * 9 + _col; col[2] = 81 + (_row - 1) * 9 + _val; col[3] = 162 + (_col - 1) * 9 + _val; col[4] = 243 + (pal[_row][_col] - 1) * 9 + _val; addline(col, 4, _row, _col, _val); } inline bool dance(){ if(R[0] == 0) return 1; int c = R[0]; for(register int i = R[c]; i; i = R[i]) if(S[i] < S[c]) c = i; del(c); for(register int i = D[c]; i != c; i = D[i]){ sdk[x[i]][y[i]] = v[i]; for(register int j = R[i]; j != i; j = R[j]) del(C[j]); if(dance()) return 1; for(register int j = L[i]; j != i; j = L[j]) add(C[j]); } add(c); return 0; } } dl; int main(){ scanf("%d", &T); while(T--){ dl.init(324); for(register int i = 1; i <= 9; i++) for(register int j = 1; j <= 9; j++){ sdk[i][j] = getgrid(); if(sdk[i][j]) dl.addstatus(i, j, sdk[i][j]); else for(register int k = 1; k <= 9; k++) dl.addstatus(i, j, k); } if(!dl.dance()) continue; for(register int i = 1; i <= 9; i++){ for(register int j = 1; j <= 9; j++) printf("%d", sdk[i][j]); puts(""); } } return 0; }
发表评论