一、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;