学步园

终于搞出个dancing links啦，跳舞庆祝。。

先简单讲讲dancing links，大概就是处理一大类覆盖问题的神法。

这个算法处理的是一个叫做精确覆盖的模型，意思大概就是给你个01矩阵，要求你选出若干行，使得每列有且仅有一个1

不同于别的搜索，dancing links是搜每一列去被哪个行来覆盖，用一个双向十字链表来将所有的1链起来，从而达到去除冗余操作，提升运行速度的神奇效果，疗效显著，3盒一个疗程。。

好了，刚才有一点废话，进入正题。（那个dancing links的具体实现可以参考一些论文或是代码）

讲讲数独怎么转化为精确覆盖模型吧

可以想到，数独无非就是带有一大堆限制条件的选数问题嘛，精确覆盖也就是有每列只能选一个的限制条件的选行问题，

那么只要把这些限制条件对应到精确覆盖上就可以了，怎么对应呢？

以9数独为例，每个格子理论上是可以填1~9之间的任意一个数，但由于有行列宫的限制，所以不能随心所欲地填

而如果我们以 第i行第j列填k 对应到精确覆盖中的行，那么在第i行第j列填了k之后，第i行就不能再填k了，第j列也不能再填k了，第g[i,j]个宫也不能填k了，事实上，第i行第j列这个格子也不能再填别的数了

这可以联想到精确覆盖中每列有且仅有一个1吧！那么我们把 第i行填k、第j列填k、第g[i,j]宫填k 还有 第i行第j列这个格子 对应到精确精确覆盖中的列，再把 第i行第j列填k 这样的行中 对应的列放上1（也就是在 第i行填k、第j列填k、第g[i,j]宫填k 还有 第i行第j列这个格子 这些列放1），恰好契合了数独的所有限制条件，就可以用精确覆盖模型做了！

dancing links=高效+极速，这话不假。

数独实测，就算是加了一大堆优化的直接搜索（包括某年集训队论文提到的一个带状态压缩优化的那个版本）在dancing links面前也是抬不起头的。

真的太神了~~

代码：（代码大同小异，这里就贴个16数独的算了）

pku 3076

program syj; {sudoku_dancing links}<br /> const nn=16; oo=maxlongint shr 1;<br /> var u,d,l,r,h,tx,ty,tz:array[0..(nn+1)*nn*nn*4]of longint;<br /> size:array[1..nn*nn*4]of longint;<br /> map:array[1..nn,1..nn]of longint;<br /> n,m,tot:longint; ok:boolean;<br /> procedure print;<br /> var i,j:longint;<br /> begin<br /> for i:=1 to n do begin<br /> for j:=1 to n do write(chr(map[i,j]+64));<br /> writeln;<br /> end;<br /> writeln;<br /> // writeln; inc(tt);<br /> // writeln(tt);<br /> // close(input);close(output);<br /> // halt;<br /> ok:=true;<br /> end;<br /> procedure cover(i:longint);<br /> var j,k:longint;<br /> begin<br /> l[r[i]]:=l[i];r[l[i]]:=r[i]; j:=d[i];<br /> while j<>i do begin<br /> k:=r[j];<br /> while k<>j do begin<br /> u[d[k]]:=u[k];d[u[k]]:=d[k]; dec(size[h[k]]);<br /> k:=r[k];<br /> end;<br /> j:=d[j];<br /> end;<br /> end;<br /> procedure recover(i:longint)；<br /> var j,k:longint;<br /> begin<br /> l[r[i]]:=i;r[l[i]]:=i; j:=u[i];<br /> while j<>i do begin<br /> k:=l[j];<br /> while k<>j do begin<br /> u[d[k]]:=k;d[u[k]]:=k; inc(size[h[k]]);<br /> k:=l[k];<br /> end;<br /> j:=u[j];<br /> end;<br /> end;<br /> procedure dlx;<br /> var i,j,k,min:longint;<br /> begin<br /> i:=r[0]; min:=oo<br /> while i<>0 do begin<br /> if size[i]<=min then begin //!! <=<br /> min:=size[i]; j:=i;<br /> end;<br /> i:=r[i];<br /> end;<br /> if min=0 then exit;<br /> if min=oo then begin<br /> print;exit;<br /> end;<br /> cover(j); i:=d[j];<br /> while i<>j do begin<br /> k:=r[i]; map[tx[i],ty[i]]:=tz[i];<br /> while k<>i do begin<br /> cover(h[k]); map[tx[k],ty[k]]:=tz[k];<br /> k:=r[k];<br /> end;<br /> dlx; if ok then exit;<br /> k:=l[i]; map[tx[i],ty[i]]:=0;<br /> while k<>i do begin<br /> recover(h[k]); map[tx[k],ty[k]]:=0;<br /> k:=l[k];<br /> end;<br /> i:=d[i];<br /> end;<br /> recover(j);<br /> end;<br /> function calc(i,j:longint):longint;<br /> begin calc:=(i-1)div m*m+(j+m-1) div m; end;<br /> procedure init;<br /> var i,j,k,ii,kk:longint;<br /> cc:char;<br /> begin<br /> tot:=n*n*4;<br /> for i:=1 to tot do begin<br /> l[i]:=i-1;r[i]:=i+1;u[i]:=i;d[i]:=i;<br /> end;<br /> r[0]:=1; r[tot]:=0; ii:=tot;<br /> for i:=1 to n do<br /> for j:=1 to n do<br /> for k:=1 to n do begin<br /> inc(tot); tx[tot]:=i;ty[tot]:=j;tz[tot]:=k; h[tot]:=(i-1)*n+k;inc(size[h[tot]]);<br /> l[tot]:=tot+3;r[tot]:=tot+1;u[tot]:=u[h[tot]];d[tot]:=h[tot];<br /> d[u[h[tot]]]:=tot;u[h[tot]]:=tot;<br /> inc(tot); tx[tot]:=i;ty[tot]:=j;tz[tot]:=k; h[tot]:=(j-1)*n+k+n*n;inc(size[h[tot]]);<br /> l[tot]:=tot-1;r[tot]:=tot+1;u[tot]:=u[h[tot]];d[tot]:=h[tot];<br /> d[u[h[tot]]]:=tot;u[h[tot]]:=tot;<br /> inc(tot); tx[tot]:=i;ty[tot]:=j;tz[tot]:=k; h[tot]:=(calc(i,j)-1)*n+k+n*n*2;inc(size[h[tot]]);<br /> l[tot]:=tot-1;r[tot]:=tot+1;u[tot]:=u[h[tot]];d[tot]:=h[tot];<br /> d[u[h[tot]]]:=tot;u[h[tot]]:=tot;<br /> inc(tot); tx[tot]:=i;ty[tot]:=j;tz[tot]:=k; h[tot]:=(i-1)*n+j+n*n*3;inc(size[h[tot]]);<br /> l[tot]:=tot-1;r[tot]:=tot-3;u[tot]:=u[h[tot]];d[tot]:=h[tot];<br /> d[u[h[tot]]]:=tot;u[h[tot]]:=tot;<br /> end;<br /> for i:=1 to n do begin<br /> for j:=1 to n do begin<br /> read(cc);if cc='-' then continue;<br /> k:=ord(cc)-64;<br /> kk:=4*((i-1)*n*n+(j-1)*n+k-1)+ii;<br /> for kk:=kk+1 to kk+4 do begin<br /> map[tx[kk],ty[kk]]:=tz[kk];<br /> cover(h[kk]);<br /> end;<br /> end;<br /> readln;<br /> end;<br /> end;<br /> begin<br /> n:=nn; m:=round(sqrt(n));<br /> while not seekeof do begin<br /> ok:=false;tot:=0;<br /> fillchar(size,sizeof(size),0);<br /> fillchar(map,sizeof(map),0);<br /> init;<br /> dlx;<br /> readln;<br /> end;<br /> end.<br />

可惜，速度还是比盾盾那个诡异动态版dlx慢一点

还有，那个每次选1最少的那个列的那个地方，如果<=就是400ms左右，<就是3000ms+了

因为我的列的顺序是行->列->宫->格子，估计是后面的宫的那个限制条件卡的紧一些，所有先选后面的会好些，这个地方囧了我好久