一、Dancing Links算法實現數獨求解（NP難問題）

算法方案

數獨可轉化為精確覆蓋問題，使用Knuth提出的DLX算法實現高效求解。該算法通過雙向十字循環鏈表實現快速回溯，時間復雜度可達O(n^k)（k為常數）

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;const int MAXN = 9*9*9 + 10;
const int MAXM = 9*9*4 + 10;
int U[MAXN], D[MAXN], L[MAXN], R[MAXN];
int C[MAXN], H[MAXN]; // 列指針、行頭指針
int S[MAXM], O[MAXN]; // 列計數、答案棧
int n, m, size; // 總行數、總列數、結點總數void init(int _m) {m = _m;for(int i=0; i<=m; ++i) {U[i] = D[i] = i;L[i] = i-1;R[i] = i+1;S[i] = 0;}R[m] = 0; L[0]()  = m;size = m + 1;
}void link(int r, int c) {C[size] = c;U[size] = U[c];D[size] = c;D[U[c]] = size;U[c] = size;if(H[r] == -1) H[r] = L[size] = R[size] = size;