「POJ3076」Sudoku TJ
为什么要用DLX呢？
DFS他不香吗！
题意：
略去不讲（数独还没玩过？滚回去玩吧！）
思路：
DFS，判断方案是否可行。
\(9 \times 9\) 的数独问题中，我们采用的策略是：
- 优先填合法位置最少的地方；
- 全局变量记录当前状态，及时还原现场；
- 到达边界（不能填时）返回不合法，否则返回合法
- 位运算
卡常优化时间复杂度
然而，在 \(16 \times 16\) 的数独问题，你这么写会T到飞起。。。
没有关系，因为上述算法还有极大的优化空间：
- 首先可以发现的是，某些位置在某一时刻已经确定了唯一可以填写的数，可以直接填写减少递归开销
- 然后，我们还可以发现，对于一个局面，可能存在某个局部无解的情况，可以直接回溯，如下图所示：
- 最后，这么乱搞下来，我们发现位运算卡常之后还原不是那么方便，所以干脆复制原数组乱搞即可。
于是有了如下数组：
char s[16][16];//数独局面
int cnt[1<<16];//cnt[i]表示i所代表的二进制数有几位是1
int f[1<<16];//f[1<<i]等于i（应该知道f是拿来干啥的了吧）
int vis[16][16];//vis[i][j]存当前数独局面下，位置(i,j)能填的值的二进制表示
vector<int> c[1<<16];//c[i]存i表示的所有能填的值
然后可以抛开 vis及 s，先试着写写另几个数组的预处理。
好了，让我们来看看预处理代码：
inline int get_cnt(int i){
int k=i&-i;
c[i].push_back(f[k]);
for(int j=0;j<c[i-k].size();j++) c[i].push_back(c[i-k][j]);
return cnt[i-k]+1;
}
//在main函数中：
for(int i=0;i<16;i++) f[1<<i]=i;
for(int i=1;i<(1<<16);i++) cnt[i]=get_cnt(i);
根本不需要暴力，直接 lowbit位运算搞定(比去掉 lowbit时多了当前位为一的状态)。
同时，我们可以用位运算来维护我们的 vis数组
inline void work(int i,int j,int k){//(i,j)位置填写k的影响
for(int t=0;t<16;t++) vis[i][t]&=~(1<<k),vis[t][j]&=~(1<<k);//影响行、列
int x=i/4*4,y=j/4*4;
for(int ti=0;ti<4;ti++) for(int tj=0;tj<4;tj++) vis[x+ti][y+tj]&=~(1<<k);//影响十六宫格
}
随后DFS,我们可以分别考虑全局可行性、每行可行性、每列可行性、每个 \(4 \times 4\) 数独可行性，并进行求解。在最后，我们再按照“选择合法选项最少的位置递归”的思路求解。
接下来给出DFS框架,并附上全局可行性判断与每行可行性判断的代码，请尝试自己补充剩余部分:
void dfs(int cnt){//当前还剩cnt个代填位
if(!ans) return 1;//已有答案,直接返回
int pre[16][16];//暂存数组
memcpy(pre,vis,sizeof pre);//拷贝数组
//考虑全局的可行性
for(int i=0;i<16;i++)//枚举每一行
for(int j=0;j<16;j++)//考虑每个位置
if(s[i][j]=='-'){//为空
if(!vis[i][j]) return 0;//此处没有合法选择
if(cnt[vis[i][j]]==1){//此次仅有一个合法选择
s[i][j]=f[vis[i][j]]+'A';//填写
work(i,j,f[vis[i][j]]);//维护
if(dfs(ans-1)) return 1;//合法直接返回
s[i][j]='-';
memcpy(vis,pre,sizeof(vis));//还原现场
return 0;//由于此处仅有一个选项，不合法则直接无解
}
}
//考虑每一行的可行性
for(int i=0;i<16;i++){
int w[16],o=0;//o记录所在行（可能）出现的选项
memset(w,0,sizeof(w));//w记录选项对于当前位置是否合法及合法方案数
for(int j=0;j<16;j++)
if(s[i][j]=='-'){//待填写
o|=vis[i][j];//当前位置所有可能填写选项的都是可能的
for(int k=0;k<c[vis[i][j]].size();k++) w[c[vis[i][j]][k]]++;
}
else{
o|=(1<<(s[i][j]-'A'));//可能选项只有填上的这个了
w[f[1<<(s[i][j]-'A')]]=-1;//那这个也不能填了
}
if(o!=(1<<16)-1) return 0;//这一行凑不满就废了
for(int k=0;k<16;k++)//考虑每个选项
if(w[k]==1)//方案数为1，立即填写
for(int j=0;j<16;j++)
if(s[i][j]=='-'&&((vis[i][j]>>k)&1)){//如果是我们要填的位置
s[i][j]=k+'A';//跟上面的一样了
work(i,j,k);
if(dfs(ans-1)) return 1;
s[i][j]='-';
memcpy(vis,pre,sizeof(vis));
return 0;
}
}
//......
}
好了，经过一小会儿码代码，你应该成功写出来169行左右的码量并成功AC。
然后没有DLX狗跑得快。。。
不过没有关系，我们要知道：
“算法思维能力的训练远比学习几个能直接拿来解决问题的数据结构重要”
完整代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
int x=0,f=1;char ch=getchar();
while('0'>ch||'9'<ch){if(ch=='-') f=-f;ch=getchar();}
while('0'<=ch&&'9'>=ch)x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
char s[16][16];
int cnt[1<<16],f[1<<16],vis[16][16];
vector<int> c[1<<16];
inline void work(int i,int j,int k){
for(int t=0;t<16;t++) vis[i][t]&=~(1<<k),vis[t][j]&=~(1<<k);
int x=i/4*4,y=j/4*4;
for(int ti=0;ti<4;ti++) for(int tj=0;tj<4;tj++) vis[x+ti][y+tj]&=~(1<<k);
}
inline bool dfs(int ans){
if(!ans) return 1;
int pre[16][16];
memcpy(pre,vis,sizeof(pre));
for(int i=0;i<16;i++)
for(int j=0;j<16;j++)
if(s[i][j]=='-'){
if(!vis[i][j]) return 0;
if(cnt[vis[i][j]]==1){
s[i][j]=f[vis[i][j]]+'A';
work(i,j,f[vis[i][j]]);
if(dfs(ans-1)) return 1;
s[i][j]='-';
memcpy(vis,pre,sizeof(vis));
return 0;
}
}
for(int i=0;i<16;i++){
int w[16],o=0;
memset(w,0,sizeof(w));
for(int j=0;j<16;j++)
if(s[i][j]=='-'){
o|=vis[i][j];
for(int k=0;k<c[vis[i][j]].size();k++) w[c[vis[i][j]][k]]++;
}
else{
o|=(1<<(s[i][j]-'A'));
w[f[1<<(s[i][j]-'A')]]=-1;
}
if(o!=(1<<16)-1) return 0;
for(int k=0;k<16;k++)
if(w[k]==1)
for(int j=0;j<16;j++)
if(s[i][j]=='-'&&((vis[i][j]>>k)&1)){
s[i][j]=k+'A';
work(i,j,k);
if(dfs(ans-1)) return 1;
s[i][j]='-';
memcpy(vis,pre,sizeof(vis));
return 0;
}
}
for(int j=0;j<16;j++){
int w[16],o=0;
memset(w,0,sizeof(w));
for(int i=0;i<16;i++)
if(s[i][j]=='-'){
o|=vis[i][j];
for(int k=0;k<c[vis[i][j]].size();k++) w[c[vis[i][j]][k]]++;
}
else{
o|=(1<<(s[i][j]-'A'));
w[f[1<<(s[i][j]-'A')]]=-1;
}
if(o!=(1<<16)-1) return 0;
for(int k=0;k<16;k++)
if(w[k]==1)
for(int i=0;i<16;i++)
if(s[i][j]=='-'&&((vis[i][j]>>k)&1)){
s[i][j]=k+'A';
work(i,j,k);
if(dfs(ans-1)) return 1;
s[i][j]='-';
memcpy(vis,pre,sizeof(vis));
return 0;
}
}
for(int i=0;i<16;i+=4)
for(int j=0;j<16;j+=4){
int w[16],o=0;
memset(w,0,sizeof(w));
for(int x=0;x<4;x++)
for(int y=0;y<4;y++)
if(s[i+x][j+y]=='-'){
o|=vis[i+x][j+y];
for(int k=0;k<c[vis[i+x][j+y]].size();k++) w[c[vis[i+x][j+y]][k]]++;
}
else{
o|=(1<<(s[i+x][j+y]-'A'));
w[f[1<<(s[i+x][j+y]-'A')]]=-1;
}
if(o!=(1<<16)-1) return 0;
for(int k=0;k<16;k++)
if(w[k]==1)
for(int x=0;x<4;x++)
for(int y=0;y<4;y++)
if(s[i+x][j+y]=='-'&&((vis[i+x][j+y]>>k)&1)){
s[i+x][j+y]=k+'A';
work(i+x,j+y,k);
if(dfs(ans-1)) return 1;
s[i+x][j+y]='-';
memcpy(vis,pre,sizeof(vis));
return 0;
}
}
int k=17,x,y;
for(int i=0;i<16;i++)
for(int j=0;j<16;j++)
if(s[i][j]=='-'&&cnt[vis[i][j]]<k) k=cnt[vis[i][j]],x=i,y=j;
for(int i=0;i<c[vis[x][y]].size();i++){
int t=c[vis[x][y]][i];
work(x,y,t);
s[x][y]=t+'A';
if(dfs(ans-1)) return 1;
s[x][y]='-';
memcpy(vis,pre,sizeof(vis));
}
return 0;
}
inline void Sudoku(){
for(int i=1;i<16;i++) scanf("%s",s[i]);
for(int i=0;i<16;i++)
for(int j=0;j<16;j++)
vis[i][j]=(1<<16)-1;
int cnt=0;
for(int i=0;i<16;i++)
for(int j=0;j<16;j++)
if(s[i][j]!='-') work(i,j,s[i][j]-'A');
else cnt++;
dfs(cnt);
for(int i=0;i<16;i++){
for(int j=0;j<16;j++) putchar(s[i][j]);
putchar('\n');
}
putchar('\n');
}
inline int get_cnt(int i){
int k=i&-i;
c[i].push_back(f[k]);
for(int j=0;j<c[i-k].size();j++) c[i].push_back(c[i-k][j]);
return cnt[i-k]+1;
}
int main(){
for(int i=0;i<16;i++) f[1<<i]=i;
for(int i=1;i<(1<<16);i++) cnt[i]=get_cnt(i);
while(~scanf("%s",s[0])) Sudoku();
return 0;
}
OK,完结撒花，附上福利：一组数据
in:
-------N---L---H
BA-----K------I-
-ED--JH-BC-I-F--
--P-M----F-HL---
--L---K-----A---
O--DN-F-C----J-E
-B---L-A--H--PG-
---G--DB--P-K--C
CF--A--ID--B-OP-
-D---F-L--N---J-
M---P--J-G-E--A-
--E--H-C--F-B--D
-IK-L-A-F----C--
D-M--NJ--I-CF-L-
NP---C--AO---DB-
--A-E--F-D--J-N-
P-C--J-------HE-
-IL-DF---G---A-B
B---I-GC---HD---
--HA-K-------C-F
D---C-EF-BI---P-
J--L----F-PO--I-
-A--G-IN-H--EK--
--B-JL--K---A---
---J--F--IGB-P--
AB---HK--F--G---
--E-A---C-O--ML-
-F---C-E-D-----N
---K---G--D-B---
C---EIB--M---D-P
-L------N-A-C---
--N-P-L-------GA
----E----C--G---
-E---C-B--DP--O-
D-GP--J-F----A--
-I--K-GA-B---E-J
--F---C--D--H-N-
--B--P--E--K--A-
-H--B--K--FI-C--
K---J----H-A-P-L
--A----C-----O-I
--D--F-I-E----P-
-G-EL-H----M-J--
-J--A-B-P-CGF-H-
-C--------O-I-L-
---G-OD---J----H
E--F-M--D--L-K-A
H-P-C--F-A--B---
------H-----G--O
----E----M----H-
-C---O----B--D--
L-G------NACFB--
------M--C---A-K
--K-B--E-P-D---L
---DHC-I---M-PO-
AH----F-J-N--I--
--B-K-J---H-PG-E
-E-F--IMKJL--N-H
J---C-ON-----F--
--C--------O----
HL-E---FI-----G-
G----D--PA--EKFN
-P--NE--H-K-----
-JFA-B--M-D-----
out:
FMJODIBNKPGLEACH
BAHCFPLKNEOMDGIJ
LEDNGJHOBCAIPFKM
KGPIMACEJFDHLNOB
PJLMCEKHGNIFABDO
OKIDNGFPCBLAMJHE
EBCFJLOAMKHDIPGN
AHNGIMDBEJPOKLFC
CFGHAKEIDMJBNOPL
IDOPBFMLHANKCEJG
MLBKPDNJOGCEHIAF
JNEAOHGCILFPBKMD
GIKJLBADFHMNOCEP
DOMEKNJGPIBCFHLA
NPFLHCIMAOEJGDBK
HCABEOPFLDKGJMNI
PDCMBJALOKFINHEG
NILEDFHOJGMCPAKB
BKJFIEGCAPNHDLOM
OGHAMKNPDLBEICJF
DOKHCAEFMBINJGPL
JEGLKBDHFAPOMNIC
FAMCGPINLHJDEKBO
INBPJLOMKCEGAFDH
LCOJNMFDHIGBKPAE
ABPNOHKIEFLMGJCD
KHEDAGPBCNOJFMLI
MFIGLCJEPDKAOBHN
HPAKFNCGIODLBEMJ
CJFOEIBAGMHKLDNP
GLDBHOMJNEAPCIFK
EMNIPDLKBJCFHOGA
MFHBELPOACKJGNID
JEKAFCNBGIDPLHOM
DOGPIHJMFNLECAKB
CILNKDGAHBMOPEFJ
IAFJOECGLDPBHMNK
GLBCDPMHEONKJIAF
PHNOBALKMJFIDCEG
KDEMJIFNCHGAOPBL
FPAHMJECNLBDKOGI
LNDKGFOIJEAHMBPC
BGCELKHPOFIMAJDN
OJMIANBDPKCGFLHE
NCJDHBAEKMOFIGLP
AKIGNODLBPJCEFMH
EBOFPMIJDGHLNKCA
HMPLCGKFIAENBDJO
BMPNAJHCDKFIGELO
FDAKEIBLOMJGNCHP
ICEJFONGLHBPKDAM
LOGHPMDKENACFBIJ
EFLPOGMJBCIHDANK
CIKOBNAEFPGDMHJL
NGJDHCKIALEMBPOF
AHMBDLFPJONKCIEG
ONBLKFJDCIHAPGME
PEDFGAIMKJLBONCH
JAHICPONGDMELFKB
MKCGLHEBNFPOIJDA
HLNEMKPFIBCJAOGD
GBIMJDCHPAOLEKFN
DPOCNELAHGKFJMBI
KJFAIBGOMEDNHLPC