Dancing Links, Exact Cover Problem(舞蹈链精确覆盖问题，高效解数独)

日付: 10月 26, 2018

## Exact Cover Problem
精确覆盖问题是指一个全为0或1的矩阵，要选择一些行，使每一列1恰好出现一次。这个问题是NP完全的，但是在矩阵比较稀疏的情况下可以回溯递归解决。

## Knuth's Algorithm X
X算法可用来解决精确覆盖问题，流程如下：
1. 如果矩阵$A$为空，找到答案
2. 选择一列$c$(一般选1最少的一列更快)
3. 选择满足$A_{r,c} = 1$的一行$r$，将$r$添加到部分解(遍历回溯)
5. 遍历满足$A_{r,j}=1$的列$j$，遍历满足$A_{i,j}=1$的行$i$，删除行$i$，删除列$j$
6. 在剩余的$A$上递归调用X算法

## Dancing Links
X算法的主要瓶颈在于第4步中的删除和第3步中的回溯操作需要对数组不断地查询和备份。因此Knuth提出了一种数据结构Dancing Links，用于实现高效的元素删除和恢复。

Dancing Links是在矩阵$A$中，每行每列都是一个双向循环链表。双向链表中，删除一个元素x只需要`x.left.right = x.right, x.right.left = x.left`，此时x的左右指针依然指向原来的元素，恢复时只需要`x.left.right = x.right.left = x`即可。

Dancing Links的要素有：
1. 所有的元素要记录6个值：其上下左右指向的元素以及所在行列。
2. 一个header行。包括header以及代表每一列的结点，记作$c_j$。
3. 一个$S$数组，记录每一列的元素数量，用于找1最少的列。
4. $n$行$m$列数据，只考虑原矩阵中为1的元素。每一行形成一个双向循环链表，每一列与对应的$c_j$形成双向循环链表。

在Dancing Links中，定义`remove`列的操作为“1. 在header行中删除该列对应的$c_j$；2. 对于该列其他元素，将除该元素外同行的其他元素从对应的列中删除”，相应的，选择行的操作就是`remove`行中元素对应的列。这样的结果是以$c_j$为入口依然能够访问所有被删除的元素，但以header为入口无法访问，相当于被删除了。那么恢复时，只需要从$c_j$出发，逆序遍历，逐一恢复即可。详见代码
```c++
    void remove(int c) {
        L[R[c]] = L[c],  R[L[c]] = R[c];
        for (int i = D[c]; i != c; i = D[i])
            for (int j = R[i]; j != i; j = R[j])
                U[D[j]] = U[j], D[U[j]] = D[j], --S[J[j]];
    }
    void restore(int c) {
        for (int i = U[c]; i != c; i = U[i])
            for (int j = L[i]; j != i; j = L[j])
                U[D[j]] = D[U[j]] = j, ++S[J[j]];
        L[R[c]] = R[L[c]] = c;
    }
```

原X算法的流程可以修改为：
1. 如果header行没有列，找到答案成功返回
2. 选择一列$c$，其元素数量最少，`remove(c)`
3. 遍历选择列$c$中的一个元素，将其行中其他元素对应的列调用`remove`删掉
4. 递归处理剩余部分，如果没找到答案就将3中删除的列`restore`

## Solving Sudoku
数独问题可以规约到精确覆盖问题，可用Dancing Links高效求解。
数独中的每个限制条件可以看作一列，每个填写步骤可以看作一行。

列的构造：
1. 每个格子只能放一个数字，81列
2. 每行、每列、每宫必须有1-9出现，81×3 = 243列

行的构造：每个格子填入1-9之一的数共9×9×9 = 729行，分别将该填法能满足的列置为1

对于已经填写的数字，将其对应的行选择(也就是把行中元素对应的列`remove`)之后再运行算法。

### Code
<details><summary>Sudoku Solver, DLX</summary>

```c++
#include <bits/stdc++.h>
using namespace std;

// r and c are 1-indexed
struct DLX {
    int n, m, sz;
    vector<int> S, R, U, L, D, I, J;
    DLX(int n, int m, vector<pair<int, int>> P) : n(n), m(m), sz(0), S(m + 1) {
        assert(n > 0 && m > 0);
        sort(P.begin(), P.end());
        add(1, 0, m, 0, 0, 0);
        for (int i = 1; i <= m; i++) add((i + 1) % (m + 1), i, i - 1, i, 0, i);
        sz = m + 1;
        vector<int> C(m + 1), F(n + 1);
        iota(C.begin(), C.end(), 0);
        for (auto p : P) {
            int r = p.first, c = p.second;
            assert(0 < r && r <= n && 0 < c && c <= m);
            if (!F[r]) add(sz, C[c], sz, c, r, c), F[r] = sz;
            else add(F[r], C[c], sz - 1, c, r, c);
            L[R[sz]] = R[L[sz]] = U[D[sz]] = D[U[sz]] =  sz, C[c] = sz++, S[c]++;
        }
    }
    void add(int r, int u, int l, int d, int i, int j) {
        R.push_back(r), U.push_back(u), L.push_back(l), \
        D.push_back(d), I.push_back(i), J.push_back(j);
    }
    void remove(int c) {
        L[R[c]] = L[c],  R[L[c]] = R[c];
        for (int i = D[c]; i != c; i = D[i])
            for (int j = R[i]; j != i; j = R[j])
                U[D[j]] = U[j], D[U[j]] = D[j], --S[J[j]];
    }
    void restore(int c) {
        for (int i = U[c]; i != c; i = U[i])
            for (int j = L[i]; j != i; j = L[j])
                U[D[j]] = D[U[j]] = j, ++S[J[j]];
        L[R[c]] = R[L[c]] = c;
    }
    vector<vector<int>> ans(int n_ans = 1, const vector<int> &Used = {}) {
        for (auto c : Used) assert(1 <= c && c <= m), remove(c);
        vector<vector<int>> Ans;
        vector<int> Tmp;
        function<void()> dfs = [&]() {
            if (n_ans < 1) return;
            if (!R[0]) { n_ans--; Ans.emplace_back(Tmp); return; }
            int c = R[0];
            for (int i = c; i; i = R[i]) if (S[i] < S[c]) c = i;
            remove(c);
            for (int i = D[c]; i != c; i = D[i]) {
                Tmp.push_back(I[i]);
                for (int j = R[i]; j != i; j = R[j]) remove(J[j]);
                dfs(), Tmp.pop_back();
                if (n_ans < 1) return;
                for (int j = L[i]; j != i; j = L[j]) restore(J[j]);
            }
            restore(c);
        };
        return dfs(), Ans;
    }
};

// 51Nod. 1211
int G[10][10];
int main() {
    for (int i = 1; i <= 9; i++)
        for (int j = 1; j <= 9; j++)
            scanf("%d", &G[i][j]);
    vector<pair<int, int>> P;
    auto row_col = [](int i, int k) { return 81 + (i - 1) * 9 + k; };
    auto col_col = [](int j, int k) { return 81 * 2 + (j - 1) * 9 + k; };
    auto block_col = [](int i, int j, int k) { return 81 * 3 + ((i - 1) / 3 * 3 + (j - 1) / 3) * 9 + k; };
    vector<int> Used;
    int cnt = 0;
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            cnt += !!G[i][j];
            for (int k = 1; k <= 9; k++) {
                int r = (i - 1) * 81 + (j - 1) * 9 + k;
                int a = (i - 1) * 9 + j, b = row_col(i, k), c = col_col(j, k), d = block_col(i, j, k);
                for (auto x : {a, b, c, d}) P.emplace_back(r, x);
                if (k == G[i][j]) for (auto x : {a, b, c, d}) Used.push_back(x);
            }
        }
    }
    if (cnt < 17) return puts("No Solution"), 0;
    DLX dlx(9 * 9 * 9, 9 * 9 * 4, P);
    auto Ans = dlx.ans(2, Used);
    if (Ans.size() != 1u) printf("No Solution\n");
    else {
        for (auto r : Ans.front()) {
            r--;
            int k = r % 9 + 1;
            r /= 9;
            int j = r % 9 + 1;
            r /= 9;
            int i = r % 9 + 1;
            G[i][j] = k;
        }
        for (int i = 1; i <= 9; i++)
            for (int j = 1; j <= 9; j++)
                printf("%d%c", G[i][j], " \n"[j == 9]);
    }
    return 0;
}
```
</details>

KONGROOの基地

このブログを検索

Dancing Links, Exact Cover Problem(舞蹈链精确覆盖问题，高效解数独)

コメント

コメントを投稿