我用的是DLX的算法，只不过平时用二维坐标表示链表的节点。发现其中我dance是否选取1最少的一列这点优化比较玄学，有时候加上会直接成功，有时候又会很久不能出结果。逻辑应该是与其他的DLX一样的，很不能理解

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

short int U[730][325][2], D[730][325][2], R[730][325][2], L[730][325][2];  // 链表
bool mat[730][325];  // 存0 1值
short int board[10][10]; // 保存答案
short int c_cnt[325];  // 用于记录每一列有多少1
int head[2]={0, 0};  // 作为每次操作的起点，上下与虚拟节点相连，实际使用则直接用0表示啦
int steps=0;
/*
变量说明：
对于DLX的矩阵（729x325）用xy坐标表示
对于数独的矩阵（9x9）用ij坐标表示
对于数独九宫格的编号（1-9）用变量k表示
其中，k的计算为：k = 3*((i-1)/3)+(j-1)/3+1

坐标示意：(x, y)
(1, 1)  (1, 2)......(1, 324)
.                          .
.                          .
.                          .
.                          .
(729, 1)..........(729, 324)

坐标示意：(i, j)
(1, 1)  (1, 2)......(1, 9)
.                        .
.                        .
.                        .
.                        .
(9, 1)  (9, 2)......(9, 9)

分块示意：int k = (board[i][j])3x3
1 2 3 
4 5 6
7 8 9
*/


// 这里remove和resume不改变改列除虚拟节点外的连接，是基于整个算法只会在虚拟节点间和需要删除的行上进行跨列的访问


void remove(int l){  // 本来没有引入虚拟节点，通过变更head来遍历与删除，判断删完的方法不同
    // 这里remove表示的是，先找到一个列（需要满足的条件）进行覆盖
    // remove本身不需要被回溯，最终每一列都会被remove。

    // [0][l]为l列的虚拟节点

    // 先删除l位置虚拟节点与两侧的连接
    R[L[0][l][0]][L[0][l][1]][1]=R[0][l][1];
    L[R[0][l][0]][R[0][l][1]][1]=L[0][l][1];

    for(int x=D[0][l][0]; x!=0; x=D[x][l][0]){  // 遍历l列值为1的位置（全部节点）（不包括虚拟节点）
    	// cout <<"  x  " <<x<<l<< R[x][l][1]<< endl;
        for(int y=R[x][l][1]; y!=l; y=R[x][y][1]){  // 遍历这一行的其他位置，删除上下连接
            // cout << y << endl;
            
            
            U[D[x][y][0]][D[x][y][1]][0]=U[x][y][0];U[D[x][y][0]][D[x][y][1]][1]=U[x][y][1];
            D[U[x][y][0]][U[x][y][1]][0]=D[x][y][0];D[U[x][y][0]][U[x][y][1]][1]=D[x][y][1];
            c_cnt[y]--;
        }    
    }

    // 解释如下：在dance函数中，会通过删除这些行中节点所在列来进行dance，而显然这两行不会同时选用，故直接删除
}


void resume(int l){  
    steps++;  // 用于记录进行了几次回溯
    // 调用resume的情况永远（等价于）紧接着remove同样的内容，所以完全是remove的逆操作。

    for(int x=D[0][l][0]; x!=0; x=D[x][l][0]){  // 遍历l列值为1的位置（全部节点）（不包括虚拟节点）
        for(int y=R[x][l][1]; y!=l; y=R[x][y][1]){  // 遍历这一行的其他位置，恢复上下连接
            U[D[x][y][0]][D[x][y][1]][0]=x;U[D[x][y][0]][D[x][y][1]][1]=y;
            D[U[x][y][0]][U[x][y][1]][0]=x;D[U[x][y][0]][U[x][y][1]][1]=y;
            c_cnt[y]++;
        }    
    }
    R[L[0][l][0]][L[0][l][1]][1]=l;
    L[R[0][l][0]][R[0][l][1]][1]=l;

}


bool dance(int step){  // 返回值为是否解出了答案; step为dfs的递归深度
    if(R[0][0][1]==0){
        return true;  // 矩阵只剩下head，删完了。
    }

    int min_y=0;
    int min_val=1000;

    for(int y=R[0][0][1]; y!=0; y=R[0][y][1]){

        if (c_cnt[y]<min_val){
            min_y = y;
            min_val = c_cnt[y];
        }
    }  // 找到节点最少的一列min_y，目的为减少递归深度。

    min_y=R[0][0][1];  // 用于验证上面的优化方案有效的语句

    remove(min_y);  // 删除这一列
    
    for(int x=D[0][min_y][0]; x!=0; x=D[x][min_y][0]){  // 遍历这一列上的节点（找到行）
        // 假设选取这一行
        for(int y=R[x][min_y][1]; y!=min_y; y=R[x][y][1]){
            // 对这一行的每一个节点，需要删除这一列（这一列被覆盖）
            remove(y);
        }
        // cout << "step "<<step << "with" << x << "choosen" << endl;
        if(dance(step+1)){
            int v=(x-1)%9+1;  // 反解，见main中注释
            int j=((x-v)/9)%9+1;
            int i=(x-v-9*(j-1))/81+1;
            board[i][j] = v;  // 填入答案
            return true;
        }
        for(int y=R[x][min_y][1]; y!=min_y; y=R[x][y][1]){
            resume(y);
        }
    }
    resume(min_y);
    return false;

}


int main(){
    memset(c_cnt, 0, sizeof(c_cnt));
    memset(mat, 0, sizeof(mat));
    for(int x=0; x<=729; x++){  // x能取0的原因是：在第0行创建一行虚拟节点用于管理
        for(int y=1; y<=324; y++){  
            // 构建链表
            
            U[x][y][0]=x-1;U[x][y][1]=y;
            D[x][y][0]=x+1;D[x][y][1]=y;
            if(x==0) U[x][y][0]=729;
            if(x==729) D[x][y][0]=0;
            L[x][y][1]=y-1;L[x][y][0]=x;
            R[x][y][1]=y+1;R[x][y][0]=x;
            if(y==1) L[x][y][1]=324;
            if(y==324) R[x][y][1]=1;
        }
    }
    // 创建两个虚拟节点与head的连接
    R[0][0][0]=0;  R[0][0][1]=1;
    L[0][0][0]=0;  L[0][0][1]=324;
    R[0][324][0]=0;R[0][324][1]=0;
    L[0][1][0]=0;  L[0][1][1]=0;


    for(int i=1; i<=9; i++){
        for(int j=1; j<=9; j++){
            cin >> board[i][j];
            // 在这里进行输入，若有值，则直接跳过后续的赋值，以便直接删除对应节点。
            for(int v=1; (v<=9); v++){
                // 给mat赋值
                /*
                x的范围：1-749。其中：
                    PICK(i, j, v)表示在i行j列填入v，x=81*(i-1)+9*(j-1)+v
                    反解可得：
                    -v=(PICK-1)%9+1
                    -j=((PICK-v)/9)%9+1
                    -i=(PICK-v-9*j)/81

                y的范围：1-324。其中：
                    1-81行：LINE(i, v)表示i行有元素v，y=9*(i-1)+v
                    82-162行：COLUMN(j, v)表示j列有元素v，y=81+9*(j-1)+v
                    163-243行：BLOCK(k, v)表示编号为k的九宫格有元素v，y=162+9*(k-1)+v
                    244-324行：NODE(i, j)表示数独(i, j)位置有值，y=243+9*(i-1)+j
                */
                int k = 3*((i-1)/3)+(j-1)/3+1;
                int x = 81*(i-1)+9*(j-1)+v;
                mat[x][9*(i-1)+v] = 1;
                mat[x][81+9*(j-1)+v] = 1;
                mat[x][162+9*(k-1)+v] = 1;
                mat[x][243+9*(i-1)+j] = 1;
                c_cnt[9*(i-1)+v] ++;
                c_cnt[81+9*(j-1)+v] ++;
                c_cnt[162+9*(k-1)+v] ++;
                c_cnt[243+9*(i-1)+j] ++;
            }
        }
    }

    for(int x=1; x<=729; x++){
        
    	int v=(x-1)%9+1;  // 反解，见main中注释
        int j=((x-v)/9)%9+1;
        int i=(x-v-9*(j-1))/81+1;

        for(int y=1; y<=324; y++){  
            // 清洗链表（删去0节点）
            if(mat[x][y]!=0)continue;
            // cout << board[i][j] << "?" << endl;
            /*
            [x][y][0] 表示x值
            [x][y][1] 表示y值
            U[x][y][0]  U[x][y][1]  本节点上一个节点的xy
            D[x][y][0]  D[x][y][1]
            L[x][y][1]
            R[x][y][1]
            */
            U[D[x][y][0]][D[x][y][1]][0]=U[x][y][0];  // 更新与上面的连接
            U[D[x][y][0]][D[x][y][1]][1]=U[x][y][1];

            D[U[x][y][0]][U[x][y][1]][0]=D[x][y][0];
            D[U[x][y][0]][U[x][y][1]][1]=D[x][y][1];

            L[R[x][y][0]][R[x][y][1]][0]=L[x][y][0];
            L[R[x][y][0]][R[x][y][1]][1]=L[x][y][1];

            R[L[x][y][0]][L[x][y][1]][0]=R[x][y][0];
            R[L[x][y][0]][L[x][y][1]][1]=R[x][y][1];
        }
    }

    for(int i=1; i<=9; i++){  // 删除给出已经满足条件的列（被覆盖）
        for(int j=1; j<=9; j++){
            if(board[i][j]){
                int v = board[i][j];
                int k = 3*((i-1)/3)+(j-1)/3+1;
                int x = 81*(i-1)+9*(j-1)+v;
                remove(9*(i-1)+v);
                remove(81+9*(j-1)+v);
                remove(162+9*(k-1)+v);
                remove(243+9*(i-1)+j);
            }
        }
    }
    dance(1);
    for(int i=1; i<=9; i++){
        for(int j=1; j<=9; j++){
            cout << board[i][j] << " ";
        }
        cout << endl;
    }
    // cout << steps << endl;  // 输出迭代深度
}