20210914下午
搜尋？狗都不用。
| T1 | T2 | T3 | T4 | T5 |
|---|---|---|---|---|
| 預測 | 100 | 100 | 100 | 60 |
| 一測 | 100 | 100 | 100 |
T1：
簡單搜尋。。。按順序搜就行
T2：
提示把剪枝都講了，實在是太良心了。
T3：
不是，憑什麼 n = 8000 n=8000 n=8000能搜出來啊。。。我本來想寫 10 10 10個 h a s h hash hash暴力了。。。
爆搜能搜出來。。。而且題面是 N o s o l u t i o n ! No\ \ solution! No solution!，答案是 N o S o l u t i o n ! No\ \ Solution! No Solution!。
T4：
經典搜尋加模拟，其實蠻簡單的，隻有消去和墜落兩個操作要注意。
一些剪枝：
1.如果目前同一顔色隻有 1 1 1塊或 2 2 2塊就結束遊戲，無解。
2.隻有右邊為空時才往左邊移，否則一定往右移更優。
3.如果是相同色塊就無需交換。
貼個代碼吧。
struct game{ //遊戲狀态
int s[10][10]; //塊色
int col[15]; //每種顔色個數，用于剪枝1
bool cl[10][10]; //清除标記
void Read() //讀入
{
int tmp;
for(int i=1;i<=5;i++) for(int j=1;scanf("%d",&tmp)&&tmp;j++) s[i][j]=tmp;
return;
}
bool empty() //是否消完
{
for(int i=1;i<=5;i++) for(int j=1;j<=7;j++) if(s[i][j]) return false;
return true;
}
bool clear() //消塊
{
bool res=false;
for(int i=1;i<=5;i++)
{
for(int j=1,k,c;j<=7;j++)
{
c=s[i][j];if(!c) continue;
for(k=i;k<=5&&s[k+1][j]==c;k++); //向右拓展
if(k-i+1>=3) {res=true;for(int l=i;l<=k;l++) cl[l][j]=true;}
for(k=j;k<=7&&s[i][k+1]==c;k++); //向上拓展
if(k-j+1>=3) {res=true;for(int l=j;l<=k;l++) cl[i][l]=true;}
}
}
for(int i=1;i<=5;i++) for(int j=1;j<=7;j++) if(cl[i][j]) s[i][j]=0,cl[i][j]=false; //消去
return res;
}
void fall() //墜落
{
for(int j=2;j<=7;j++) for(int i=1;i<=5;i++) for(int k=j;k>1&&s[i][k]&&!s[i][k-1];k--) swap(s[i][k],s[i][k-1]); //下面為空就一直掉
return;
}
bool over() //剪枝1
{
memset(col,0,sizeof(col));
for(int i=1;i<=5;i++) for(int j=1;j<=7;j++) col[s[i][j]]++;
for(int i=1;i<=10;i++) if(col[i]>=1&&col[i]<=2) return true;
return false;
}
}st;
void Dfs(int x,game now) //搜尋
{
if(flag) return;
now.fall(); //可能上次移向空處
while(now.clear()) now.fall(); //能消就一直消
if(now.over()) return;
if(x==n+1)
{
if(now.empty()) print(),flag=true;
return;
}
game nxt;nxt=now;
for(int i=1;i<=5;i++)
{
for(int j=1;j<=7;j++)
{
if(!now.s[i][j]) continue;
if(in(i+1,j)&&now.s[i+1][j]!=now.s[i][j]) //剪枝3
{
swap(nxt.s[i+1][j],nxt.s[i][j]);
ans[x].x=i;ans[x].y=j;ans[x].f=1;
Dfs(x+1,nxt);
if(flag) return;
swap(nxt.s[i+1][j],nxt.s[i][j]);
}
if(!now.s[i-1][j]) //剪枝2
{
if(!in(i-1,j)||now.s[i-1][j]==now.s[i][j]) continue; //剪枝3
swap(nxt.s[i-1][j],nxt.s[i][j]);
ans[x].x=i;ans[x].y=j;ans[x].f=-1;
Dfs(x+1,nxt);
if(flag) return;
swap(nxt.s[i-1][j],nxt.s[i][j]);
}
}
}
return;
}
思路很清晰的模拟。
T5：
《關于我用搜尋怎麼剪都剪不過就去學 D a n c i n g L i n k s X Dancing\ \ Links\ \ X Dancing Links X然後 40 m s 40ms 40msA了數獨這件事》
搜尋我就不多說了，就算我加了按最小選擇排序也過不了，可能是我的問題。
下面我來隆重介紹 D a n c i n g L i n k s X Dancing\ \ Links\ \ X Dancing Links X算法。
D L X DLX DLX是由 X X X算法通過十字連結清單優化而來，用于解決精準覆寫問題。
什麼是精準覆寫問題？
可以了解為給出 n n n個集合和一個全集，要求選出一些集合使他們不重複地構成全集，也就是 S 1 ∪ S 2 ∪ S 3 ⋯ = S S_1\cup S_2 \cup S_3 \dots =S S1∪S2∪S3⋯=S且 S 1 ∩ S 2 ∩ S 3 ⋯ = ∅ S_1 \cap S_2 \cap S_3 \dots=\varnothing S1∩S2∩S3⋯=∅。
舉個例子，現在有集合
S = { 114 , 233 , 514 , 7 , 1926 , 817 , 666 } S=\{114,233,514,7,1926,817,666\} S={114,233,514,7,1926,817,666}
S 1 = { 114 , 514 , 7 } S_1=\{114,514,7\} S1={114,514,7}
S 2 = { 114 , 1926 , 817 , 666 } S_2=\{114,1926,817,666\} S2={114,1926,817,666}
S 3 = { 514 , 817 , 666 } S_3=\{514,817,666\} S3={514,817,666}
S 4 = { 114 } S_4=\{114\} S4={114}
S 5 = { 114 , 233 , 7 , 1926 } S_5=\{114,233,7,1926\} S5={114,233,7,1926}
S 6 = { 514 , 7 , 1926 , 66 } S_6=\{514,7,1926,66\} S6={514,7,1926,66}
S 7 = { 233 , 514 , 7 } S_7=\{233,514,7\} S7={233,514,7}
S 8 = { 233 , 817 } S_8=\{233,817\} S8={233,817}
可以一眼看出這個問題的精準覆寫為 S 2 S_2 S2和 S 7 S_7 S7或 S 3 S_3 S3和 S 5 S_5 S5或 S 4 S_4 S4， S 6 S_6 S6和 S 8 S_8 S8。
那麼 X X X算法是如何解決這個問題的呢？
首先，我們把這些關系轉化為矩陣
S 114 233 514 7 1926 817 666 S 1 1 0 1 1 0 0 0 S 2 1 0 0 0 1 1 1 S 3 0 0 1 0 0 1 1 S 4 1 0 0 0 0 0 0 S 5 1 1 0 1 1 0 0 S 6 0 0 1 1 1 0 1 S 7 0 1 1 1 0 0 0 S 8 0 1 0 0 0 1 0 \begin{matrix} S&114&233&514&7&1926&817&666 \\ S_1&1&0&1&1&0&0&0 \\ S_2&1&0&0&0&1&1&1 \\ S_3&0&0&1&0&0&1&1 \\ S_4&1&0&0&0&0&0&0 \\ S_5&1&1&0&1&1&0&0 \\ S_6&0&0&1&1&1&0&1 \\ S_7&0&1&1&1&0&0&0 \\ S_8&0&1&0&0&0&1&0 \end{matrix} SS1S2S3S4S5S6S7S81141101100023300001011514101001107100011101926010011008170110000166601100100
然後，我們先假設選擇了 S 1 S_1 S1，顯然我們就不能選那些在 S 1 S_1 S1上有數的集合，那麼我們就去删除這些行和列
得到
S 233 1926 817 66 S 8 1 0 1 0 \begin{matrix} S&233&1926&817&66 \\ S_8 &1&0&1&0 \end{matrix} SS82331192608171660
接着我們選擇 S 8 S_8 S8并進行同樣的操作。
S 1926 66 \begin{matrix} S&1926&66 \end{matrix} S192666
發現集合被删完了， S S S卻還有剩，說明選 S 1 S_1 S1無法得到答案，于是回溯恢複被删除的行和列并不再考慮 S 1 S_1 S1
之後選擇 S 2 S_2 S2
得到
S 233 514 7 S 7 1 1 1 \begin{matrix} S&233&514&7 \\ S_7&1&1&1 \end{matrix} SS72331514171
選擇 S 7 S_7 S7， S S S被删完，說明找到一組答案，若不是多組答案可以直接退出程式了。
若要找多組答案，則繼續回溯，選擇 S 3 S_3 S3
得到
S 114 233 7 1926 S 4 1 0 0 0 S 5 1 1 1 1 \begin{matrix} S&114&233&7&1926 \\ S_4&1&0&0&0 \\ S_5&1&1&1&1 \end{matrix} SS4S51141123301701192601
若選擇 S 4 S_4 S4，那麼有
S 233 7 1926 \begin{matrix} S&233&7&1926 \end{matrix} S23371926
無解，回溯選擇 S 5 S_5 S5，發現消完，找到另一組解。
回溯選擇 S 4 S_4 S4
得到
S 233 514 7 1926 817 666 S 6 0 1 1 1 0 1 S 7 1 1 1 0 0 0 S 8 1 0 0 0 1 0 \begin{matrix} S&233&514&7&1926&817&666 \\ S_6&0&1&1&1&0&1 \\ S_7&1&1&1&0&0&0 \\ S_8&1&0&0&0&1&0 \end{matrix} SS6S7S823301151411071101926100817001666100
選擇 S 6 S_6 S6，得到
S 233 817 S 8 1 1 \begin{matrix} S&233&817 \\ S_8&1&1 \end{matrix} SS823318171
删去後再次得到一組解。
後面就不模拟了（做圖做麻了，不過大概意思應該都知道了，這就是 X X X算法的大緻流程。
可以發現此算法需要大量的删除行列和恢複的操作，是以如果樸素實作，其指數級複雜度取決于矩陣中 1 1 1的個數，大概隻能接受 n , m ≤ 100 n,m\le 100 n,m≤100的矩陣。
是以我們的十字連結清單優化就來啦， D L X DLX DLX橫空出世。（其實并沒有，它也不是啥省選内容。
下面偷一下DLX 詳細講解的圖來簡單介紹一下十字連結清單（我真的做不來啊淦。
十字連結清單擁有四個指針左 l l l右 r r r上 u u u下 d d d，以這些指針來存儲一個矩陣。
完整版大概是張這樣的。
當然，除了上面的幾個數組，還有 f i r s t i first_i firsti表示每一行的行首，每一列的列首則是由 0 0 0節點連接配接出的虛拟節點。
另外需要一個 s i z i siz_i sizi記錄每列的節點個數。
是以大概需要這幾個數組
int n,m,tot,first[N],siz[N]; //tot表示節點編号
int l[N],r[N],u[N],d[N];
int row[N],col[N]; //表示該節點的行列
接下來是幾個操作
1.建表
建構一個 R × C R\times C R×C的空矩陣，隻需将每一列的虛節點建出來就行。
void build(int R,int C)
{
n=R;m=C;
for(int i=0;i<=C;i++) l[i]=i-1,r[i]=i+1,u[i]=d[i]=i;
l[0]=C;r[C]=0;tot=C; //每一行列都是環狀連結清單，新節點從C+1開始
memset(first,0,sizeof(first));
memset(siz,0,sizeof(siz));
return;
}
另外建議使用以下形式通路環狀連結清單
2.插入
在 ( R , C ) (R,C) (R,C)處插入一個點，相當于我們在矩陣内插入一個 1 1 1。
定義該節點為 t o t tot tot，在列上，直接進行操作。
将 t o t tot tot上方改為 C C C， t o t tot tot下方改為原來 C C C下方的節點，原來 C C C下方節點的上方改為 t o t tot tot， C C C下方節點改為 t o t tot tot。
即
對行，進行分類。
若該行還沒有 f i r s t first first節點，将 f i r s t first first直接改為 t o t tot tot。
若該行有 f i r s t first first節點了，将 t o t tot tot左邊改為 f i r s t R first_R firstR，右邊改為原來 f i r s t R first_R firstR的右邊， f i r s t R first_R firstR右邊節點的左邊改為 t o t tot tot， f i r s t R first_R firstR的右邊改為 t o t tot tot
即
if(!first[R]) first[R]=l[tot]=r[tot]=tot;
else l[tot]=first[R],r[tot]=r[first[R]],l[r[first[R]]]=tot,r[first[R]]=tot;
都是很好了解的連結清單操作，完整如下
void insert(int R,int C)
{
row[++tot]=R;col[tot]=C;siz[C]++;
u[tot]=C,d[tot]=d[C],u[d[C]]=tot,d[C]=tot;
if(!first[R]) first[R]=l[tot]=r[tot]=tot;
else l[tot]=first[R],r[tot]=r[first[R]],l[r[first[R]]]=tot,r[first[R]]=tot;
return;
}
3.移除
對于移除列 C C C的操作，我們需要移除這一列與向下通路到的每一行。
移除這一列很簡單，将 C C C左右節點的左右指針修改即可。
接着向下通路每個節點，再橫向通路哪一行，将節點上下節點修改以删去那一行。
完成修改操作。
void remove(int C)
{
l[r[C]]=l[C];r[l[C]]=r[C];
IT(i,d,C) IT(j,r,i) u[d[j]]=u[j],d[u[j]]=d[j],siz[col[j]]--;
return;
}
4.恢複
其實就是把移除操作反過來弄一遍。
void recover(int C)
{
IT(i,d,C) IT(j,r,i) u[d[j]]=d[u[j]]=j,siz[col[j]]++;
l[r[C]]=r[l[C]]=C;
return;
}
以上就是我們需要的所有操作，然後與 X X X算法結合就是 D L X DLX DLX算法了。
bool dance(int dep,int *s)
{
int C=r[0]; //若0無右節點，說明矩陣為空，算法結束
if(!C) {···;return true;} //處理答案
IT(i,r,0) if(siz[i]<siz[C]) C=i; //找一個結點最少的列以減少搜尋樹
remove(C);
IT(i,d,C)
{
s[dep]=row[i];
IT(j,r,i) remove(col[j]);
if(dance(dep+1,s)) return true; //鏡像操作，若多組資料就不用return
IT(j,r,i) recover(col[j]);
s[dep]=0;
}
recover(C);
return false;
}
（叫 D a n c i n g L i n k s X Dancing\ \ Links\ \ X Dancing Links X是因為搜尋過程在各行中跳）
可以通過【模闆】舞蹈鍊（DLX）了。
D L X DLX DLX的複雜度為 O ( c n ) O(c^n) O(cn)，其中 n n n為矩陣中 1 1 1的個數，而 c c c是一個十分接近于 1 1 1的常數，是以一般可以通過大部分題目。
不過該算法還有一個難點，将題目要求抽象成集合與矩陣。
我們回到數獨這道題本身上來。
在 i i i行 j j j列 w w w宮 ( i , j , w ) (i,j,w) (i,j,w)填一個數 k k k，因為 w w w可以由 i , j i,j i,j确定，是以我們隻需要 i × j × k i\times j\times k i×j×k即 9 × 9 × 9 = 729 9\times 9\times 9=729 9×9×9=729行（個集合）。
而這個操作又會引起哪些擾動呢。
會使 ( i , j ) (i,j) (i,j)位置被占
會使 i i i行 k k k這個數無法使用。
會使 j j j列 k k k這個數無法使用。
會使 w w w宮 k k k這個數無法使用。
每種都需要 81 81 81列來存儲，是以共 81 × 4 = 324 81\times 4=324 81×4=324列（集合大小）。
是以，我們成功将數獨問題轉化為一個 729 × 324 729\times 324 729×324的精确覆寫問題。
代碼和模闆的差別在于插入結點。
#include<bits/stdc++.h>
#define IT(i,A,x) for(int i=A[x];i!=x;i=A[i]) //好用
using namespace std;
const int N=1e5+5; //數組要開矩陣大小
int a,s[N],ans[105][105];
class Orthogonal_List{ //十字連結清單
public:
int n,m,tot,first[N],siz[N];
int l[N],r[N],u[N],d[N];
int col[N],row[N];
void build(int R,int C)
{
n=R;m=C;
for(int i=0;i<=C;i++) l[i]=i-1,r[i]=i+1,u[i]=d[i]=i;
l[0]=C;r[C]=0;tot=C;
memset(first,0,sizeof(first));
memset(siz,0,sizeof(siz));
return;
}
void insert(int R,int C)
{
row[++tot]=R;col[tot]=C;siz[C]++;
u[tot]=C,d[tot]=d[C],u[d[C]]=tot,d[C]=tot;
if(!first[R]) first[R]=l[tot]=r[tot]=tot;
else l[tot]=first[R],r[tot]=r[first[R]],l[r[first[R]]]=tot,r[first[R]]=tot;
return;
}
void remove(int C)
{
l[r[C]]=l[C];r[l[C]]=r[C];
IT(i,d,C) IT(j,r,i) u[d[j]]=u[j],d[u[j]]=d[j],siz[col[j]]--;
return;
}
void recover(int C)
{
IT(i,d,C) IT(j,r,i) u[d[j]]=d[u[j]]=j,siz[col[j]]++;
l[r[C]]=r[l[C]]=C;
return;
}
bool dance(int dep)
{
int C=r[0];
if(!C) {for(int i=1,x,y,z;i<dep;i++) {x=((s[i]-1)/9)/9+1;y=((s[i]-1)/9)%9+1;z=(s[i]-1)%9+1;ans[x][y]=z;};return true;}
IT(i,r,0) if(siz[i]<siz[C]) C=i;
remove(C);
IT(i,d,C)
{
s[dep]=row[i];
IT(j,l,i) remove(col[j]); //這裡用兩個IT(j,r,i)就會錯，其他都行，玄學。。。
if(dance(dep+1)) return true;
IT(j,r,i) recover(col[j]);
s[dep]=0;
}
recover(C);
return false;
}
}lis;
char ch[100];
int main()
{
while(scanf("%s",ch+1)&&ch[1]!='e')
{
lis.build(729,324); //建圖
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
{
a=ch[(i-1)*9+j]=='.'?0:ch[(i-1)*9+j]-'0';
for(int k=1,l;k<=9;k++)
{
if(a-k&&a) continue; //其實就是有值就隻填a，為空就每個都填
l=((i-1)*9+(j-1))*9+k; //行
lis.insert(l,(i-1)*9+j); //i行j列
lis.insert(l,81+(i-1)*9+k); //i行k數
lis.insert(l,162+(j-1)*9+k); //j列k數
lis.insert(l,243+(((i-1)/3)*3+(j-1)/3)*9+k); //w宮k數
}
}
}
lis.dance(1); //你你你你要跳舞嗎
for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) putchar(ans[i][j]+'0');putchar('\n');
}
return 0;
}
完結撒花。
總結：搜尋是有極限的，是以我直接擺爛啦。