DLX数独建图：一共9*9*9 = 729行，9*9*4 = 324列。第i行表示数独的i/81行i/9%9列放置数字i%9。324列分成4个部分，每个部分81列，分别限制每个格子只能放一个数字、每行只能放一种数字、每列只能放一种数字、每个3*3的格子只能放一种数字。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iostream>
#include <sstream>using namespace std;const int maxn = 3241;
const int inf = 1000000000;char mtx[729][324];
char sudoku[82];
int N, M, head, idx; // 分别是行数, 列数, 列头结点链表的头结点, 结点计数器
int L[maxn], R[maxn], U[maxn], D[maxn];
int RH[maxn], CH[maxn], S[maxn]; // RH为结点的行编号, CH结点的列编号, S为每列结点数void InitMtx() {int i, j, k, t;memset(mtx, 0, sizeof(mtx));for (i = 0; i < 9; i++) {for (j = 0; j < 9; j++) {t = i * 9 + j;if (sudoku[t] == '.') {for (k = 0; k < 9; k++) {mtx[t*9+k][t] = 1; // (行,列)mtx[t*9+k][81+i*9+k] = 1; // (行,数)mtx[t*9+k][162+j*9+k] = 1; // (列,数)mtx[t*9+k][243+(i/3*3+j/3)*9+k] = 1; // (格,数)}} else {k = sudoku[t] - '1';mtx[t*9+k][t] = 1; // (行,列)mtx[t*9+k][81+i*9+k] = 1; // (行,数)mtx[t*9+k][162+j*9+k] = 1; // (列,数)mtx[t*9+k][243+(i/3*3+j/3)*9+k] = 1; // (格,数)}}}
}int Node(int up, int down, int left, int right) {U[idx] = up; D[idx] = down;L[idx] = left; R[idx] = right;D[up] = U[down] = R[left] = L[right] = idx;return idx++;
}void Build() {int i, j, k;idx = maxn - 1;head = Node(idx, idx, idx, idx); // 初始化列头结点链表的头结点idx = 0;for (j = 0; j < M; j++) { // 申请M个结点为每列的头结点Node(idx, idx, L[head], head);CH[j] = j; S[j] = 0;}for (i = 0; i < N; i++) {k = -1;for (j = 0; j < M; j++) {if (!mtx[i][j]) continue;if (k == -1) {k = Node(U[CH[j]], CH[j], idx, idx);RH[k] = i; CH[k] = j; S[j]++;} else {k = Node(U[CH[j]], CH[j], k, R[k]);RH[k] = i; CH[k] = j; S[j]++;}}}
}void Remove(int c) {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];S[CH[j]]--;}}
}void Resume(int c) {int i, j;R[L[c]] = c;L[R[c]] = c;for (i = U[c]; i != c; i = U[i]) {for (j = L[i]; j != i; j = L[j]) {S[CH[j]]++;D[U[j]] = j;U[D[j]] = j;}}
}int dfs() {if (R[head] == head)return 1;int i, j, k, c, min = inf;for (j = R[head]; j != head; j = R[j]) {if (S[j] < min) {min = S[j];c = j;}}Remove(c);for (i = D[c]; i != c; i = D[i]) {k = RH[i];sudoku[k/9] = '1' + k % 9;for (j = R[i]; j != i; j = R[j])Remove(CH[j]);if (dfs()) return 1;for (j = L[i]; j != i; j = L[j])Resume(CH[j]);}Resume(c);return 0;
}int main() {N = 729, M = 324;while (gets(sudoku), strcmp(sudoku, "end")) {InitMtx();Build();dfs();printf("%s\n", sudoku);}return 0;
}