Dancing Links

本頁面將介紹精確覆蓋問題、重複覆蓋問題，解決這兩個問題的算法「X 算法」，以及用來優化 X 算法的雙向十字鏈表 Dancing Link。本頁也將介紹如何在建模的配合下使用 DLX 解決一些搜索題。

精確覆蓋問題

定義

精確覆蓋問題（英文：Exact Cover Problem）是指給定許多集合 \(S_i (1 \le i \le n)\) 以及一個集合 \(X\)，求滿足以下條件的無序多元組 \((T_1, T_2, \cdots , T_m)\)：

\(\forall i, j \in [1, m],T_i\bigcap T_j = \varnothing (i \neq j)\)
\(X = \bigcup\limits_{i = 1}^{m}T_i\)
\(\forall i \in[1, m], T_i \in \{S_1, S_2, \cdots, S_n\}\)

解釋

例如，若給出

\[ \begin{aligned} & S_1 = \{5, 9, 17\} \\ & S_2 = \{1, 8, 119\} \\ & S_3 = \{3, 5, 17\} \\ & S_4 = \{1, 8\} \\ & S_5 = \{3, 119\} \\ & S_6 = \{8, 9, 119\} \\ & X = \{1, 3, 5, 8, 9, 17, 119\} \end{aligned} \]

則 \((S_1, S_4, S_5)\) 為一組合法解。

問題轉化

將 \(\bigcup\limits_{i = 1}^{n}S_i\) 中的所有數離散化，可以得到這麼一個模型：

給定一個 01 矩陣，你可以選擇一些行（row），使得最終每列（column）¹都恰好有一個 1。舉個例子，我們對上文中的例子進行建模，可以得到這麼一個矩陣：

\[ \begin{pmatrix} 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{pmatrix} \]

其中第 \(i\) 行表示着 \(S_i\)，而這一行的每個數依次表示 \([1 \in S_i],[3 \in S_i],[5 \in S_i],\cdots,[119 \in S_i]\)。

實現

暴力 1

一種方法是枚舉選擇哪些行，最後檢查這個方案是否合法。

因為每一行都有選或者不選兩種狀態，所以枚舉行的時間複雜度是 \(O(2^n)\) 的；

而每次檢查都需要 \(O(nm)\) 的時間複雜度。所以總的複雜度是 \(O(nm\cdot2^n)\)。

實現

int ok = 0;
for (int state = 0; state < 1 << n; ++state) {  // 枚舉每行是否被選
  for (int i = 1; i <= n; ++i)
    if ((1 << i - 1) & state)
      for (int j = 1; j <= m; ++j) a[i][j] = 1;
  int flag = 1;
  for (int j = 1; j <= m; ++j)
    for (int i = 1, bo = 0; i <= n; ++i)
      if (a[i][j]) {
        if (bo)
          flag = 0;
        else
          bo = 1;
      }
  if (!flag)
    continue;
  else {
    ok = 1;
    for (int i = 1; i <= n; ++i)
      if ((1 << i - 1) & state) printf("%d ", i);
    puts("");
  }
  memset(a, 0, sizeof(a));
}
if (!ok) puts("No solution.");

暴力 2

考慮到 01 矩陣的特殊性質，每一行都可以看做一個 \(m\) 位二進制數。

因此原問題轉化為

給定 \(n\) 個 \(m\) 位二進制數，要求選擇一些數，使得任意兩個數的與都為 0，且所有數的或為 \(2^m - 1\)。tmp 表示的是截至目前被選中的二進制數的或。

因為每一行都有選或者不選兩種狀態，所以枚舉行的時間複雜度為 \(O(2^n)\)；

而每次計算 tmp 都需要 \(O(n)\) 的時間複雜度。所以總的複雜度為 \(O(n\cdot2^n)\)。

實現

int ok = 0;
for (int i = 1; i <= n; ++i)
  for (int j = m; j >= 1; --j) num[i] = num[i] << 1 | a[i][j];
for (int state = 0; state < 1 << n; ++state) {
  int tmp = 0;
  for (int i = 1; i <= n; ++i)
    if ((1 << i - 1) & state) {
      if (tmp & num[i]) break;
      tmp |= num[i];
    }
  if (tmp == (1 << m) - 1) {
    ok = 1;
    for (int i = 1; i <= n; ++i)
      if ((1 << i - 1) & state) printf("%d ", i);
    puts("");
  }
}
if (!ok) puts("No solution.");

重複覆蓋問題

重複覆蓋問題與精確覆蓋問題類似，但沒有對元素相似性的限制。下文介紹的 X 算法原本針對精確覆蓋問題，但經過一些修改和優化（已標註在其中）同樣可以高效地解決重複覆蓋問題。

X 算法

Donald E. Knuth 提出了 X 算法 (Algorithm X)，其思想與剛才的暴力差不多，但是方便優化。

過程

繼續以上文中中提到的例子為載體，得到一個這樣的 01 矩陣：

\[ \begin{pmatrix} 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{pmatrix} \]

此時第一行有 \(3\) 個 \(1\)，第二行有 \(3\) 個 \(1\)，第三行有 \(3\) 個 \(1\)，第四行有 \(2\) 個 \(1\)，第五行有 \(2\) 個 \(1\)，第六行有 \(3\) 個 \(1\)。選擇第一行，將它刪除，並將所有 \(1\) 所在的列打上標記；

\[ \begin{pmatrix} \color{Blue}0 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 & \color{Blue}0 \\ 1 & 0 & \color{Red}0 & 1 & \color{Red}0 & \color{Red}0 & 1 \\ 0 & 1 & \color{Red}1 & 0 & \color{Red}0 & \color{Red}1 & 0 \\ 1 & 0 & \color{Red}0 & 1 & \color{Red}0 & \color{Red}0 & 0 \\ 0 & 1 & \color{Red}0 & 0 & \color{Red}0 & \color{Red}0 & 1 \\ 0 & 0 & \color{Red}0 & 1 & \color{Red}1 & \color{Red}0 & 1 \end{pmatrix} \]
選擇所有被標記的列，將它們刪除，並將這些列中含 \(1\) 的行打上標記（重複覆蓋問題無需打標記）；

\[ \begin{pmatrix} \color{Blue}0 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 & \color{Blue}0 \\ 1 & 0 & \color{Blue}0 & 1 & \color{Blue}0 & \color{Blue}0 & 1 \\ \color{Red}0 & \color{Red}1 & \color{Blue}1 & \color{Red}0 & \color{Blue}0 & \color{Blue}1 & \color{Red}0 \\ 1 & 0 & \color{Blue}0 & 1 & \color{Blue}0 & \color{Blue}0 & 0 \\ 0 & 1 & \color{Blue}0 & 0 & \color{Blue}0 & \color{Blue}0 & 1 \\ \color{Red}0 & \color{Red}0 & \color{Blue}0 & \color{Red}1 & \color{Blue}1 & \color{Blue}0 & \color{Red}1 \end{pmatrix} \]
選擇所有被標記的行，將它們刪除；

\[ \begin{pmatrix} \color{Blue}0 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 & \color{Blue}0 \\ 1 & 0 & \color{Blue}0 & 1 & \color{Blue}0 & \color{Blue}0 & 1 \\ \color{Blue}0 & \color{Blue}1 & \color{Blue}1 & \color{Blue}0 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 \\ 1 & 0 & \color{Blue}0 & 1 & \color{Blue}0 & \color{Blue}0 & 0 \\ 0 & 1 & \color{Blue}0 & 0 & \color{Blue}0 & \color{Blue}0 & 1 \\ \color{Blue}0 & \color{Blue}0 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 & \color{Blue}0 & \color{Blue}1 \end{pmatrix} \]

這表示這一行已被選擇，且這一行的所有 \(1\) 所在的列不能有其他 \(1\) 了。

於是得到一個新的小 01 矩陣：

\[ \begin{pmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{pmatrix} \]
此時第一行（原來的第二行）有 \(3\) 個 \(1\)，第二行（原來的第四行）有 \(2\) 個 \(1\)，第三行（原來的第五行）有 \(2\) 個 \(1\)。選擇第一行（原來的第二行），將它刪除，並將所有 \(1\) 所在的列打上標記；

\[ \begin{pmatrix} \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 \\ \color{Red}1 & 0 & \color{Red}1 & \color{Red}0 \\ \color{Red}0 & 1 & \color{Red}0 & \color{Red}1 \end{pmatrix} \]
選擇所有被標記的列，將它們刪除，並將這些列中含 \(1\) 的行打上標記；

\[ \begin{pmatrix} \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 \\ \color{Blue}1 & \color{Red}0 & \color{Blue}1 & \color{Blue}0 \\ \color{Blue}0 & \color{Red}1 & \color{Blue}0 & \color{Blue}1 \end{pmatrix} \]
選擇所有被標記的行，將它們刪除；

\[ \begin{pmatrix} \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 \\ \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 \\ \color{Blue}0 & \color{Blue}1 & \color{Blue}0 & \color{Blue}1 \end{pmatrix} \]

這樣就得到了一個空矩陣。但是上次刪除的行 1 0 1 1 不是全 \(1\) 的，説明選擇有誤；

\[ \begin{pmatrix} \end{pmatrix} \]
回溯到步驟 4，考慮選擇第二行（原來的第四行），將它刪除，並將所有 \(1\) 所在的列打上標記；

\[ \begin{pmatrix} \color{Red}1 & 0 & \color{Red}1 & 1 \\ \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 \\ \color{Red}0 & 1 & \color{Red}0 & 1 \end{pmatrix} \]
選擇所有被標記的列，將它們刪除，並將這些列中含 \(1\) 的行打上標記；

\[ \begin{pmatrix} \color{Blue}1 & \color{Red}0 & \color{Blue}1 & \color{Red}1 \\ \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 \\ \color{Blue}0 & 1 & \color{Blue}0 & 1 \end{pmatrix} \]
選擇所有被標記的行，將它們刪除；

\[ \begin{pmatrix} \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 \\ \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 \\ \color{Blue}0 & 1 & \color{Blue}0 & 1 \end{pmatrix} \]

於是我們得到了這樣的一個矩陣：

\[ \begin{pmatrix} 1 & 1 \end{pmatrix} \]
此時第一行（原來的第五行）有 \(2\) 個 \(1\)，將它們全部刪除，得到一個空矩陣：

\[ \begin{pmatrix} \end{pmatrix} \]
上一次刪除的時候，刪除的是全 \(1\) 的行，因此成功，算法結束。

答案即為被刪除的三行：\(1, 4, 5\)。

強烈建議自己模擬一遍矩陣刪除、還原與回溯的過程後，再接着閲讀下文。

通過上述步驟，可將 X 算法的流程概括如下：

對於現在的矩陣 \(M\)，選擇並標記一行 \(r\)，將 \(r\) 添加至 \(S\) 中；
如果嘗試了所有的 \(r\) 卻無解，則算法結束，輸出無解；
標記與 \(r\) 相關的行 \(r_i\) 和 \(c_i\)（相關的行和列與 X 算法中第 2 步定義相同，下同）；
刪除所有標記的行和列，得到新矩陣 \(M'\)；
如果 \(M'\) 為空，且 \(r\) 為全 \(1\)，則算法結束，輸出被刪除的行組成的集合 \(S\)；

如果 \(M'\) 為空，且 \(r\) 不全為 \(1\)，則恢復與 \(r\) 相關的行 \(r_i\) 以及列 \(c_i\)，跳轉至步驟 1；

如果 \(M'\) 不為空，則跳轉至步驟 1。

不難看出，X 算法需要大量的「刪除行」、「刪除列」和「恢復行」、「恢復列」的操作。

一個樸素的想法是，使用一個二維數組存放矩陣，再用四個數組分別存放每一行與之相鄰的行編號，每次刪除和恢復僅需更新四個數組中的元素。但由於一般問題的矩陣中 0 的數量遠多於 1 的數量，這樣做的空間複雜度難以接受。

Donald E. Knuth 想到了用雙向十字鏈表來維護這些操作。

而在雙向十字鏈表上不斷跳躍的過程被形象地比喻成「跳躍」，因此被用來優化 X 算法的雙向十字鏈表也被稱為「Dancing Links」。

Dancing Links 優化的 X 算法

預編譯命令

1	`#define IT(i, A, x) for (i = A[x]; i != x; i = A[i])`

定義

雙向十字鏈表中存在四個指針域，分別指向上、下、左、右的元素；且每個元素 \(i\) 在整個雙向十字鏈表系中都對應着一個格子，因此還要表示 \(i\) 所在的列和所在的行，如圖所示：

大型的雙向鏈表則更為複雜：

每一行都有一個行首指示，每一列都有一個列指示。

行首指示為 first[]，列指示是我們新建的 \(c + 1\) 個哨兵結點。值得注意的是，行首指示並非是鏈表中的哨兵結點。它是虛擬的，類似於鄰接表中的 first[] 數組，直接指向 這一行中的首元素。

同時，每一列都有一個 siz[] 表示這一列的元素個數。

特殊地，\(0\) 號結點無右結點等價於這個 Dancing Links 為空。

constexpr int MS = 1e5 + 5;
int n, m, idx, first[MS], siz[MS];
int L[MS], R[MS], U[MS], D[MS];
int col[MS], row[MS];

過程

remove 操作

remove(c) 表示在 Dancing Links 中刪除第 \(c\) 列以及與其相關的行和列。

先將 \(c\) 刪除，此時：

\(c\) 左側的結點的右結點應為 \(c\) 的右結點。
\(c\) 右側的結點的左結點應為 \(c\) 的左結點。

即 L[R[c]] = L[c], R[L[c]] = R[c];。

然後順着這一列往下走，把走過的每一行都刪掉。

如何刪掉每一行呢？枚舉當前行的指針 \(j\)，此時：

\(j\) 上方的結點的下結點應為 \(j\) 的下結點。
\(j\) 下方的結點的上結點應為 \(j\) 的上結點。

注意要修改每一列的元素個數。

即 U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]];。

remove 函數的代碼實現如下：

實現

void remove(const int &c) {
  int i, j;
  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]];
}

recover 操作

recover(c) 表示在 Dancing Links 中還原第 \(c\) 列以及與其相關的行和列。

recover(c) 即 remove(c) 的逆操作，這裏不再贅述。

值得注意的是， recover(c) 的所有操作的順序與 remove(c) 的操作恰好相反。

recover(c) 的代碼實現如下：

實現

void recover(const int &c) {
  int i, j;
  IT(i, U, c) IT(j, L, i) U[D[j]] = D[U[j]] = j, ++siz[col[j]];
  L[R[c]] = R[L[c]] = c;
}

build 操作

build(r, c) 表示新建一個大小為 \(r \times c\)，即有 \(r\) 行，\(c\) 列的 Dancing Links。

新建 \(c + 1\) 個結點作為列指示。

第 \(i\) 個點的左結點為 \(i - 1\)，右結點為 \(i + 1\)，上結點為 \(i\)，下結點為 \(i\)。特殊地，\(0\) 結點的左結點為 \(c\)，\(c\) 結點的右結點為 \(0\)。

於是我們得到了一個環狀雙向鏈表：

這樣就初始化了一個 Dancing Links。

build(r, c) 的代碼實現如下：

實現

void build(const int &r, const 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, idx = c;
  memset(first, 0, sizeof(first));
  memset(siz, 0, sizeof(siz));
}

insert 操作

insert(r, c) 表示在第 \(r\) 行，第 \(c\) 列插入一個結點。

插入操作分為兩種情況：

如果第 \(r\) 行沒有元素，那麼直接插入一個元素，並使 first[r] 指向這個元素。

這可以通過 first[r] = L[idx] = R[idx] = idx; 來實現。
如果第 \(r\) 行有元素，那麼將這個新元素用一種特殊的方式與 \(c\) 和 \(first(r)\) 連接起來。

設這個新元素為 \(idx\)，然後：
- 把 \(idx\) 插入到 \(c\) 的正下方，此時：
  - \(idx\) 下方的結點為原來 \(c\) 的下結點；
  - \(idx\) 下方的結點（即原來 \(c\) 的下結點）的上結點為 \(idx\);
  - \(idx\) 的上結點為 \(c\)；
  - \(c\) 的下結點為 \(idx\)。
  注意記錄 \(idx\) 的所在列和所在行，以及更新這一列的元素個數。
  1 2
  col[++idx] = c, row[idx] = r, ++siz[c]; U[idx] = c, D[idx] = D[c], U[D[c]] = idx, D[c] = idx;
  強烈建議讀者完全掌握這幾步的順序後再繼續閲讀本文。
- 把 \(idx\) 插入到 \(first(r)\) 的正右方，此時：
  - \(idx\) 右側的結點為原來 \(first(r)\) 的右結點；
  - 原來 \(first(r)\) 右側的結點的左結點為 \(idx\)；
  - \(idx\) 的左結點為 \(first(r)\)；
  - \(first(r)\) 的右結點為 \(idx\)。
  1 2
  L[idx] = first[r], R[idx] = R[first[r]]; L[R[first[r]]] = idx, R[first[r]] = idx;
  強烈建議讀者完全掌握這幾步的順序後再繼續閲讀本文。

insert(r, c) 這個操作可以通過圖片來輔助理解：

留心曲線箭頭的方向。

insert(r, c) 的代碼實現如下：

實現

void insert(const int &r, const int &c) {
  row[++idx] = r, col[idx] = c, ++siz[c];
  U[idx] = c, D[idx] = D[c], U[D[c]] = idx, D[c] = idx;
  if (!first[r])
    first[r] = L[idx] = R[idx] = idx;
  else {
    L[idx] = first[r], R[idx] = R[first[r]];
    L[R[first[r]]] = idx, R[first[r]] = idx;
  }
}

dance 操作

dance() 即為遞歸地刪除以及還原各個行列的過程。

如果 \(0\) 號結點沒有右結點，那麼矩陣為空，記錄答案並返回；
選擇列元素個數最少的一列，並刪掉這一列；
遍歷這一列所有有 \(1\) 的行，枚舉它是否被選擇；
遞歸調用 dance()，如果可行，則返回；如果不可行，則恢復被選擇的行；
如果無解，則返回。

dance() 的代碼實現如下：

實現

bool dance(int dep) {
  int i, j, c = R[0];
  if (!R[0]) {
    ans = dep;
    return 1;
  }
  IT(i, R, 0) if (siz[i] < siz[c]) c = i;
  remove(c);
  IT(i, D, c) {
    stk[dep] = row[i];
    IT(j, R, i) remove(col[j]);
    if (dance(dep + 1)) return 1;
    IT(j, L, i) recover(col[j]);
  }
  recover(c);
  return 0;
}

其中 stk[] 用來記錄答案。

注意我們每次優先選擇列元素個數最少的一列進行刪除，這樣能保證程序具有一定的啓發性，使搜索樹分支最少。

對於重複覆蓋問題，在搜索時可以用估價函數（與 A* 中類似）進行剪枝：若當前最好情況下所選行數超過目前最優解，則可以直接返回。

模板

模板代碼

#include <bits/stdc++.h>
const int N = 500 + 10;
int n, m, idx, ans;
int first[N], siz[N], stk[N];

int read() {  // 快读
  int x = 0, f = 0, ch;
  while (!isdigit(ch = getchar())) f |= ch == '-';
  while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  return f ? -x : x;
}

struct DLX {
  static const int MAXSIZE = 1e5 + 10;
  int n, m, tot, first[MAXSIZE + 10], siz[MAXSIZE + 10];
  int L[MAXSIZE + 10], R[MAXSIZE + 10], U[MAXSIZE + 10], D[MAXSIZE + 10];
  int col[MAXSIZE + 10], row[MAXSIZE + 10];

  void build(const int &r, const int &c) {  // 进行build操作
    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));
  }

  void insert(const int &r, const int &c) {  // 进行insert操作
    col[++tot] = c, row[tot] = r, ++siz[c];
    D[tot] = D[c], U[D[c]] = tot, U[tot] = c, D[c] = tot;
    if (!first[r])
      first[r] = L[tot] = R[tot] = tot;
    else {
      R[tot] = R[first[r]], L[R[first[r]]] = tot;
      L[tot] = first[r], R[first[r]] = tot;
    }
  }

  void remove(const int &c) {  // 进行remove操作
    int i, j;
    L[R[c]] = L[c], R[L[c]] = R[c];
    for (i = D[c]; i != c; i = D[i])
      for (j = R[i]; j != i; j = R[j])
        U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]];
  }

  void recover(const int &c) {  // 进行recover操作
    int i, j;
    for (i = U[c]; i != c; i = U[i])
      for (j = L[i]; j != i; j = L[j]) U[D[j]] = D[U[j]] = j, ++siz[col[j]];
    L[R[c]] = R[L[c]] = c;
  }

  bool dance(int dep) {  // dance
    if (!R[0]) {
      ans = dep;
      return 1;
    }
    int i, j, c = R[0];
    for (i = R[0]; i != 0; i = R[i])
      if (siz[i] < siz[c]) c = i;
    remove(c);
    for (i = D[c]; i != c; i = D[i]) {
      stk[dep] = row[i];
      for (j = R[i]; j != i; j = R[j]) remove(col[j]);
      if (dance(dep + 1)) return 1;
      for (j = L[i]; j != i; j = L[j]) recover(col[j]);
    }
    recover(c);
    return 0;
  }
} solver;

int main() {
  n = read(), m = read();
  solver.build(n, m);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) {
      int x = read();
      if (x) solver.insert(i, j);
    }
  solver.dance(1);
  if (ans)
    for (int i = 1; i < ans; ++i) printf("%d ", stk[i]);
  else
    puts("No Solution!");
  return 0;
}

性質

DLX 遞歸及回溯的次數與矩陣中 \(1\) 的個數有關，與矩陣的 \(r, c\) 等參數無關。因此，它的時間複雜度是 指數級 的，理論複雜度大概在 \(O(c^n)\) 左右，其中 \(c\) 為某個非常接近於 \(1\) 的常數，\(n\) 為矩陣中 \(1\) 的個數。

但實際情況下 DLX 表現良好，一般能解決大部分的問題。

建模

DLX 的難點，不全在於鏈表的建立，而在於建模。

請確保已經完全掌握 DLX 模板後再繼續閲讀本文。

我們每拿到一個題，應該考慮行和列所表示的意義：

行表示決策，因為每行對應着一個集合，也就對應着選/不選；
列表示狀態，因為第 \(i\) 列對應着某個條件 \(P_i\)。

對於某一行而言，由於不同的列的值不盡相同，我們 由不同的狀態，定義了一個決策。

例題 1 P1784 數獨

解題思路

先考慮決策是什麼。

在這一題中，每一個決策可以用形如 \((r, c, w)\) 的有序三元組表示。

注意到「宮」並不是決策的參數，因為它 可以被每個確定的 \((r, c)\) 表示。

因此有 \(9 \times 9 \times 9 = 729\) 行。

再考慮狀態是什麼。

我們思考一下 \((r, c, w)\) 這個決將會造成什麼影響。記 \((r, c)\) 所在的宮為 \(b\)。

第 \(r\) 行用了一個 \(w\)（用 \(9 \times 9 = 81\) 列表示）；
第 \(c\) 列用了一個 \(w\)（用 \(9 \times 9 = 81\) 列表示）；
第 \(b\) 宮用了一個 \(w\)（用 \(9 \times 9 = 81\) 列表示）；
\((r, c)\) 中填入了一個數（用 \(9 \times 9 = 81\) 列表示）。

因此有 \(81 \times 4 = 324\) 列，共 \(729 \times 4 = 2916\) 個 \(1\)。

至此，我們成功地將 \(9 \times 9\) 的數獨問題轉化成了一個 有 \(729\) 行，\(324\) 列，共 \(2916\) 個 \(1\) 的精確覆蓋問題。

參考代碼

#include <bits/stdc++.h>
const int N = 1e6 + 10;
int ans[10][10], stk[N];

int read() {
  int x = 0, f = 0, ch;
  while (!isdigit(ch = getchar())) f |= ch == '-';
  while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  return f ? -x : x;
}  // 快读

struct DLX {
  static const int MAXSIZE = 1e5 + 10;
  int n, m, tot, first[MAXSIZE + 10], siz[MAXSIZE + 10];
  int L[MAXSIZE + 10], R[MAXSIZE + 10], U[MAXSIZE + 10], D[MAXSIZE + 10];
  int col[MAXSIZE + 10], row[MAXSIZE + 10];

  void build(const int &r, const int &c) {  // 进行build操作
    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));
  }

  void insert(const int &r, const int &c) {  // 进行insert操作
    col[++tot] = c, row[tot] = r, ++siz[c];
    D[tot] = D[c], U[D[c]] = tot, U[tot] = c, D[c] = tot;
    if (!first[r])
      first[r] = L[tot] = R[tot] = tot;
    else {
      R[tot] = R[first[r]], L[R[first[r]]] = tot;
      L[tot] = first[r], R[first[r]] = tot;
    }
  }

  void remove(const int &c) {  // 进行remove操作
    int i, j;
    L[R[c]] = L[c], R[L[c]] = R[c];
    for (i = D[c]; i != c; i = D[i])
      for (j = R[i]; j != i; j = R[j])
        U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]];
  }

  void recover(const int &c) {  // 进行recover操作
    int i, j;
    for (i = U[c]; i != c; i = U[i])
      for (j = L[i]; j != i; j = L[j]) U[D[j]] = D[U[j]] = j, ++siz[col[j]];
    L[R[c]] = R[L[c]] = c;
  }

  bool dance(int dep) {  // dance
    int i, j, c = R[0];
    if (!R[0]) {
      for (i = 1; i < dep; ++i) {
        int x = (stk[i] - 1) / 9 / 9 + 1;
        int y = (stk[i] - 1) / 9 % 9 + 1;
        int v = (stk[i] - 1) % 9 + 1;
        ans[x][y] = v;
      }
      return 1;
    }
    for (i = R[0]; i != 0; i = R[i])
      if (siz[i] < siz[c]) c = i;
    remove(c);
    for (i = D[c]; i != c; i = D[i]) {
      stk[dep] = row[i];
      for (j = R[i]; j != i; j = R[j]) remove(col[j]);
      if (dance(dep + 1)) return 1;
      for (j = L[i]; j != i; j = L[j]) recover(col[j]);
    }
    recover(c);
    return 0;
  }
} solver;

int GetId(int row, int col, int num) {
  return (row - 1) * 9 * 9 + (col - 1) * 9 + num;
}

void Insert(int row, int col, int num) {
  int dx = (row - 1) / 3 + 1;
  int dy = (col - 1) / 3 + 1;
  int room = (dx - 1) * 3 + dy;
  int id = GetId(row, col, num);
  int f1 = (row - 1) * 9 + num;            // task 1
  int f2 = 81 + (col - 1) * 9 + num;       // task 2
  int f3 = 81 * 2 + (room - 1) * 9 + num;  // task 3
  int f4 = 81 * 3 + (row - 1) * 9 + col;   // task 4
  solver.insert(id, f1);
  solver.insert(id, f2);
  solver.insert(id, f3);
  solver.insert(id, f4);
}

int main() {
  solver.build(729, 324);
  for (int i = 1; i <= 9; ++i)
    for (int j = 1; j <= 9; ++j) {
      ans[i][j] = read();
      for (int v = 1; v <= 9; ++v) {
        if (ans[i][j] && ans[i][j] != v) continue;
        Insert(i, j, v);
      }
    }
  solver.dance(1);
  for (int i = 1; i <= 9; ++i, putchar('\n'))
    for (int j = 1; j <= 9; ++j, putchar(' ')) printf("%d", ans[i][j]);
  return 0;
}

例題 2 靶形數獨

解題思路

這一題與數獨的模型構建 一模一樣，主要區別在於答案的更新。

這一題可以開一個權值數組，每次找到一組數獨的解時，

每個位置上的數乘上對應的權值計入答案即可。

參考代碼

#include <bits/stdc++.h>
const int oo = 0x3f3f3f3f;
const int N = 1e5 + 10;
const int e[] = {6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 6, 6, 7,  8,
                 8, 8, 8, 8, 7, 6, 6, 7, 8, 9, 9, 9, 8, 7, 6, 6, 7, 8, 9, 10, 9,
                 8, 7, 6, 6, 7, 8, 9, 9, 9, 8, 7, 6, 6, 7, 8, 8, 8, 8, 8, 7,  6,
                 6, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6};
int ans = -oo, a[10][10], stk[N];

int read() {
  int x = 0, f = 0, ch;
  while (!isdigit(ch = getchar())) f |= ch == '-';
  while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  return f ? -x : x;
}

int GetWeight(int row, int col, int num) {  // 求数乘上对应的权值
  return num * e[(row - 1) * 9 + (col - 1)];
}

struct DLX {
  static const int MAXSIZE = 1e5 + 10;
  int n, m, tot, first[MAXSIZE + 10], siz[MAXSIZE + 10];
  int L[MAXSIZE + 10], R[MAXSIZE + 10], U[MAXSIZE + 10], D[MAXSIZE + 10];
  int col[MAXSIZE + 10], row[MAXSIZE + 10];

  void build(const int &r, const int &c) {  // 进行build操作
    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));
  }

  void insert(const int &r, const int &c) {  // 进行insert操作
    col[++tot] = c, row[tot] = r, ++siz[c];
    D[tot] = D[c], U[D[c]] = tot, U[tot] = c, D[c] = tot;
    if (!first[r])
      first[r] = L[tot] = R[tot] = tot;
    else {
      R[tot] = R[first[r]], L[R[first[r]]] = tot;
      L[tot] = first[r], R[first[r]] = tot;
    }
  }

  void remove(const int &c) {  // 进行remove操作
    int i, j;
    L[R[c]] = L[c], R[L[c]] = R[c];
    for (i = D[c]; i != c; i = D[i])
      for (j = R[i]; j != i; j = R[j])
        U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]];
  }

  void recover(const int &c) {  // 进行recover操作
    int i, j;
    for (i = U[c]; i != c; i = U[i])
      for (j = L[i]; j != i; j = L[j]) U[D[j]] = D[U[j]] = j, ++siz[col[j]];
    L[R[c]] = R[L[c]] = c;
  }

  void dance(int dep) {  // dance
    int i, j, c = R[0];
    if (!R[0]) {
      int cur_ans = 0;
      for (i = 1; i < dep; ++i) {
        int cur_row = (stk[i] - 1) / 9 / 9 + 1;
        int cur_col = (stk[i] - 1) / 9 % 9 + 1;
        int cur_num = (stk[i] - 1) % 9 + 1;
        cur_ans += GetWeight(cur_row, cur_col, cur_num);
      }
      ans = std::max(ans, cur_ans);
      return;
    }
    for (i = R[0]; i != 0; i = R[i])
      if (siz[i] < siz[c]) c = i;
    remove(c);
    for (i = D[c]; i != c; i = D[i]) {
      stk[dep] = row[i];
      for (j = R[i]; j != i; j = R[j]) remove(col[j]);
      dance(dep + 1);
      for (j = L[i]; j != i; j = L[j]) recover(col[j]);
    }
    recover(c);
  }
} solver;

int GetId(int row, int col, int num) {
  return (row - 1) * 9 * 9 + (col - 1) * 9 + num;
}

void Insert(int row, int col, int num) {
  int dx = (row - 1) / 3 + 1;    // r
  int dy = (col - 1) / 3 + 1;    // c
  int room = (dx - 1) * 3 + dy;  // room
  int id = GetId(row, col, num);
  int f1 = (row - 1) * 9 + num;            // task 1
  int f2 = 81 + (col - 1) * 9 + num;       // task 2
  int f3 = 81 * 2 + (room - 1) * 9 + num;  // task 3
  int f4 = 81 * 3 + (row - 1) * 9 + col;   // task 4
  solver.insert(id, f1);
  solver.insert(id, f2);
  solver.insert(id, f3);
  solver.insert(id, f4);
}

int main() {
  solver.build(729, 324);
  for (int i = 1; i <= 9; ++i)
    for (int j = 1; j <= 9; ++j) {
      a[i][j] = read();
      for (int v = 1; v <= 9; ++v) {
        if (a[i][j] && v != a[i][j]) continue;
        Insert(i, j, v);
      }
    }
  solver.dance(1);
  printf("%d", ans == -oo ? -1 : ans);
  return 0;
}

例題 3 「NOI2005」智慧珠遊戲

解題思路

定義：題中給我們的智慧珠的形態，稱為這個智慧珠的標準形態。

顯然，我們可以通過改變兩個參數 \(d\)（表示順時針旋轉 \(90^{\circ}\) 的次數）和 \(f\)（是否水平翻轉）來改變這個智慧珠的形態。

仍然，我們先考慮決策是什麼。

在這一題中，每一個決策可以用形如 \((v, d, f, i)\) 的有序五元組表示。

表示第 \(i\) 個智慧珠的標準形態的左上角的位置，序號為 \(v\)，經過了 \(d\) 次順時針轉 \(90^{\circ}\)。

巧合的是，我們可以令 \(f = 1\) 時不水平翻轉，\(f = -1\) 時水平翻轉，從而達到簡化代碼的目的。

因此有 \(55 \times 4 \times 2 \times 12 = 5280\) 行。

需要注意的是，因為一些不合法的填充，如 \((1, 0, 1, 4)\)，

所以 在實際操作中，空的智慧珠棋盤也只需要建出 \(2730\) 行。

再考慮狀態是什麼。

這一題的狀態比較簡單。

我們思考一下，\((v, d, f, i)\) 這個決策會造成什麼影響。

某些格子被佔了（用 \(55\) 列表示）；
第 \(i\) 個智慧珠被用了（用 \(12\) 列表示）。

因此有 \(55 + 12 = 67\) 列，共 \(5280 \times (5 + 1) = 31680\) 個 \(1\)。

至此，我們成功地將智慧珠遊戲轉化成了一個 有 \(5280\) 行，\(67\) 列，共 \(31680\) 個 \(1\) 的精確覆蓋問題。

參考代碼

#include <bits/stdc++.h>
int numcol, numrow;
int dfn[3000], tx[2], nxt[2], num[50][50], vis[50];
char ans[50][50];
const int f[2] = {-1, 1};
const int table[12][5][2] = {
    // directions of shapes
    {{0, 0}, {1, 0}, {0, 1}},                   // A
    {{0, 0}, {0, 1}, {0, 2}, {0, 3}},           // B
    {{0, 0}, {1, 0}, {0, 1}, {0, 2}},           // C
    {{0, 0}, {1, 0}, {0, 1}, {1, 1}},           // D
    {{0, 0}, {1, 0}, {2, 0}, {2, 1}, {2, 2}},   // E
    {{0, 0}, {0, 1}, {1, 1}, {0, 2}, {0, 3}},   // F
    {{0, 0}, {1, 0}, {0, 1}, {0, 2}, {1, 2}},   // G
    {{0, 0}, {1, 0}, {0, 1}, {1, 1}, {0, 2}},   // H
    {{0, 0}, {0, 1}, {0, 2}, {1, 2}, {1, 3}},   // I
    {{0, 0}, {-1, 1}, {0, 1}, {1, 1}, {0, 2}},  // J
    {{0, 0}, {1, 0}, {1, 1}, {2, 1}, {2, 2}},   // K
    {{0, 0}, {1, 0}, {0, 1}, {0, 2}, {0, 3}},   // L
};
const int len[12] = {3, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5};
const int getx[] = {0,  1,  2,  2,  3,  3,  3,  4,  4,  4,  4,  5,  5,  5,  5,
                    5,  6,  6,  6,  6,  6,  6,  7,  7,  7,  7,  7,  7,  7,  8,
                    8,  8,  8,  8,  8,  8,  8,  9,  9,  9,  9,  9,  9,  9,  9,
                    9,  10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11,
                    11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12,
                    12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
                    13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14};
const int gety[] = {0, 1, 1, 2,  1,  2,  3,  1, 2,  3,  4,  1, 2, 3, 4,  5,  1,
                    2, 3, 4, 5,  6,  1,  2,  3, 4,  5,  6,  7, 1, 2, 3,  4,  5,
                    6, 7, 8, 1,  2,  3,  4,  5, 6,  7,  8,  9, 1, 2, 3,  4,  5,
                    6, 7, 8, 9,  10, 1,  2,  3, 4,  5,  6,  7, 8, 9, 10, 11, 1,
                    2, 3, 4, 5,  6,  7,  8,  9, 10, 11, 12, 1, 2, 3, 4,  5,  6,
                    7, 8, 9, 10, 11, 12, 13, 1, 2,  3,  4,  5, 6, 7, 8,  9};

struct DLX {
  static const int MS = 1e5 + 10;
  int n, m, tot, first[MS], siz[MS];
  int L[MS], R[MS], U[MS], D[MS];
  int col[MS], row[MS];

  void build(const int &r, const 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));
  }

  void insert(const int &r, const int &c) {  // insert
    col[++tot] = c, row[tot] = r, ++siz[c];
    D[tot] = D[c], U[D[c]] = tot, U[tot] = c, D[c] = tot;
    if (!first[r])
      first[r] = L[tot] = R[tot] = tot;
    else
      R[tot] = R[first[r]], L[R[first[r]]] = tot, L[tot] = first[r],
      R[first[r]] = tot;  // !
  }

  void remove(const int &c) {  // remove
    int i, j;
    L[R[c]] = L[c], R[L[c]] = R[c];
    for (i = D[c]; i != c; i = D[i])
      for (j = R[i]; j != i; j = R[j])
        U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]];
  }

  void recover(const int &c) {  // recover
    int i, j;
    for (i = U[c]; i != c; i = U[i])
      for (j = L[i]; j != i; j = L[j]) U[D[j]] = D[U[j]] = j, ++siz[col[j]];
    L[R[c]] = R[L[c]] = c;
  }

  bool dance() {  // dance
    if (!R[0]) return 1;
    int i, j, c = R[0];
    for (i = R[0]; i != 0; i = R[i])
      if (siz[i] < siz[c]) c = i;
    remove(c);
    for (i = D[c]; i != c; i = D[i]) {
      if (col[i] <= 55) ans[getx[col[i]]][gety[col[i]]] = dfn[row[i]] + 'A';
      for (j = R[i]; j != i; j = R[j]) {
        remove(col[j]);
        if (col[j] <= 55) ans[getx[col[j]]][gety[col[j]]] = dfn[row[j]] + 'A';
      }
      if (dance()) return 1;
      for (j = L[i]; j != i; j = L[j]) recover(col[j]);
    }
    recover(c);
    return 0;
  }
} solver;

int main() {
  for (int i = 1; i <= 10; ++i) scanf("%s", ans[i] + 1);
  for (int i = 1; i <= 10; ++i)
    for (int j = 1; j <= i; ++j) {
      if (ans[i][j] != '.') vis[ans[i][j] - 'A'] = 1;
      num[i][j] = ++numcol;
    }
  solver.build(2730, numcol + 12);
  /*******build*******/
  for (int id = 0, op; id < 12; ++id) {  // every block
    for (++numcol, op = 0; op <= 1; ++op) {
      for (int dx = 0; dx <= 1; ++dx) {
        for (int dy = 0; dy <= 1; ++dy) {
          for (tx[0] = 1; tx[0] <= 10; ++tx[0]) {
            for (tx[1] = 1; tx[1] <= tx[0]; ++tx[1]) {
              bool flag = 1;
              for (int k = 0; k < len[id]; ++k) {
                nxt[op] = tx[op] + f[dx] * table[id][k][0];
                nxt[op ^ 1] = tx[op ^ 1] + f[dy] * table[id][k][1];
                if (vis[id]) {
                  if (ans[nxt[0]][nxt[1]] != id + 'A') {
                    flag = 0;
                    break;
                  }
                } else if (ans[nxt[0]][nxt[1]] != '.') {
                  flag = 0;
                  break;
                }
              }
              if (!flag) continue;
              dfn[++numrow] = id;
              solver.insert(numrow, numcol);
              for (int k = 0; k < len[id]; ++k) {
                nxt[op] = tx[op] + f[dx] * table[id][k][0];
                nxt[op ^ 1] = tx[op ^ 1] + f[dy] * table[id][k][1];
                solver.insert(numrow, num[nxt[0]][nxt[1]]);
              }
            }
          }
        }
      }
    }
  }
  /********end********/
  if (!solver.dance())
    puts("No solution");
  else
    for (int i = 1; i <= 10; ++i, puts(""))
      for (int j = 1; j <= i; ++j) putchar(ans[i][j]);
  return 0;
}

習題

外部鏈接

註釋

（兩岸用語差異）台灣：直行（column）、橫列（row） ↩

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：LeverImmy, 383494
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用