POJ 3076 數獨求解：DLX 精確覆蓋算法完整實現

問題描述

標準 16×16 數獨，使用字母 A–P 填充。規則：每行、每列、每個 4×4 子方格內字母均不重複。輸入保證有唯一解。需讀取多組數據，輸出完整解。

為什麼選 DLX (Dancing Links)?

數獨是典型的精確覆蓋問題：每個格子必須填一個數，且每行/列/宮的每個數字只能出現一次。共 4 類約束，總列數 = 16×16×4 = 1024。每個可能的填寫動作（行、列、數字）對應一行，覆蓋 4 個約束列。DLX 能高效回溯搜尋唯一解。

約束矩陣建模

• 列 0–255：cell[i][j] 格子被填（每格必填一個數）
• 列 256–511：row[i][num] 第 i 行出現數字 num
• 列 512–767：col[j][num] 第 j 列出現數字 num
• 列 768–1023：block[b][num] 第 b 個 4×4 宮出現數字 num

總行數 = 16×16×16 = 4096（每格 16 種可能）。預填數字只保留對應行。

核心代碼結構

struct DLX {
    int n, m, size;                 // 行數、列數、節點總數
    int U[maxnode], D[maxnode], L[maxnode], R[maxnode];
    int Row[maxnode], Col[maxnode]; // 節點對應的行、列
    int H[maxnode], S[maxnode];     // 每行首節點、每列節點數
    int ansd, ans[maxn];            // 解的深度、解路徑

    void init(int _n, int _m);      // 初始化列頭鏈表
    void Link(int r, int c);        // 插入節點 (r,c)
    void remove(int c);             // 覆蓋列 c
    void resume(int c);             // 恢復列 c
    bool Dance(int d);              // 深度 d 遞歸搜尋
};

// 建立精確覆蓋矩陣
void place(int &r, int &c1, int &c2, int &c3, int &c4,
           int i, int j, int k) {
    r = (i*N + j)*N + k;            // 行編號
    c1 = i*N + j + 1;               // 格子約束
    c2 = N*N + N*i + k;             // 行約束
    c3 = N*N*2 + N*j + k;           // 列約束
    c4 = N*N*3 + ((i/4)*4 + j/4)*N + k; // 宮約束
}

Dancing Links 核心邏輯

bool Dance(int d) {
    if (R[0] == 0) {                // 所有列覆蓋完 → 找到解
        for (int i = 0; i < d; i++)
            sudoku[(ans[i]-1)/16] = (ans[i]-1)%16 + 'A';
        // 輸出解...
        return true;
    }
    // 選擇節點數最少的列（啟發式優化）
    int c = R[0];
    for (int i = R[0]; i != 0; i = R[i])
        if (S[i] < S[c]) c = i;
    remove(c);
    for (int i = D[c]; i != c; i = D[i]) {
        ans[d] = Row[i];
        for (int j = R[i]; j != i; j = R[j]) remove(Col[j]);
        if (Dance(d+1)) return true;
        for (int j = L[i]; j != i; j = L[j]) resume(Col[j]);
    }
    resume(c);
    return false;
}

複雜度與優化

• 最壞情況指數級，但 DLX 配合「最少列優先」啟發式，實測極快。
• 16×16 數獨在 10 秒內輕鬆通過（POJ 限制 10000MS）。
• 內存：節點數 ≈ 4096×4 + 1024 ≈ 1.7 萬，遠小於 64MB 限制。

總結

本題是 DLX 算法的教科書級應用。關鍵在於正確建模 4 類約束、高效實現雙向鏈表的刪除/恢復，以及利用啟發式剪枝。代碼模板化後，可直接套用於其他精確覆蓋問題（如 N 皇后、數獨變體等）。