算法1

2020_12_07更新Y总舞蹈链模板 数独1
B站视频地址 [DLX]舞蹈链数据结构介绍(一)精确覆盖问题
//=========================================================================
dfs算法外使用舞蹈链进行计算

C++ 代码

#include <iostream>  
#include <stdio.h>  
#include <string.h>  


//精确覆盖问题的定义：给定一个由0-1组成的矩阵，
//是否能找到一个行的集合，
//使得集合中每一列都恰好包含一个1
const int MN = 9 * 9 * 9 + 10;//最大行数,共有9*9个格子，每个格子可以放1~9
const int MM = 9 * 9 + 9 * 9 + 9 * 9 + 9 * 9 + 100;//最大列数
const int MAX_NUM = MN * MM; //最大点数  

struct DLX
{
    int n, m, idx;//n行数m列数idx 元素索引 
                 //十字链表组成部分  

    int l[MAX_NUM], r[MAX_NUM], u[MAX_NUM], d[MAX_NUM];    //记录某个idx索引点的上下左右点的索引
    int col[MAX_NUM], row[MAX_NUM];    //两者结合使用 记录某个idx索引点的行 列号


    int nodeIdxPerRow[MAX_NUM];        //记录每行的开头节点的索引
    int nodeNumPerCol[MAX_NUM];        //记录每列节点的个数


    int ansd, ans[MN];

    void init(int n ,int m)    //初始化十字链表的 头节点和 列节点表头串   m表示有多少列
    {
        //初始化头结点和 列节点表头串 头节点数组索引 = 0  列节点表头共m个 索引 1~m
        for (int i = 0; i <= m; i++) {
            r[i] = i + 1;
            l[i] = i - 1;
            u[i] = d[i] = i;    //列节点头串只有互相横向连接 上下连接均指向自己
        }
        r[m] = 0;
        l[0] = m;  //循环连接 col[m] 的右端指向头节点 头结点的左端指向clo[m]

        memset(nodeIdxPerRow, 0, sizeof(nodeIdxPerRow));
        memset(nodeNumPerCol, 0, sizeof(nodeNumPerCol));

        idx = m + 1; //目前使用 0 头结点 与 m个列节点表头串 0~m 共m+1个节点     
    }



    //插入节点 进行的一些数据记录  
    void link(int insertRow, int insertCol)
    {
        nodeNumPerCol[insertCol]++; //插入一个节点 那么该列的节点个数+1
        row[idx] = insertRow;
        col[idx] = insertCol;   //记录第idx个节点所在的行与列

        u[idx] = insertCol;     //当前插入的节点索引记录 向上指向列节点头串中的insertCol
        d[idx] = d[insertCol];  //当前插入节点索引记录 向下指向原来列节点头串的向下指向点
        u[d[insertCol]] = idx;  //原来列节点头串指向的节点 向上由指向列节点头串指向插入的节点(使用索引)
        d[insertCol] = idx;     //列节点头串则向下指向新插入的节点(使用索引)

        //更新每行的节点记录  nodeIdxPerRow
        if (nodeIdxPerRow[insertRow] == 0) {
            //如果该节点是第一个插入的节点
            nodeIdxPerRow[insertRow] = r[idx] = l[idx] = idx;//该行没有点，直接加入 
        }
        else {
            //如果不是第一个插入的节点 同上面处理列次序一样 在记录和第一个节点间 插入本函数插入的节点
            r[idx] = nodeIdxPerRow[insertRow];      //新节点的右端指向原来行记录中的第一个节点
            l[idx] = l[nodeIdxPerRow[insertRow]];   //新节点的左端指向原来行记录第一个节点的左端 也就是行记录nodeIdxPerRow
            r[l[nodeIdxPerRow[insertRow]]] = idx;    //原来行记录第一个节点的左端(也就是行记录nodeIdxPerRow)的右端 指向新插入的点(使用索引)
            l[nodeIdxPerRow[insertRow]] = idx;        //原来行记录第一个节点的左端指向新插入的节点(使用索引)

        }
        idx++;
        return;
    }

    void remove(int deleteCol) {//删除涉及C列的集合 
     //将要删除的列的左右两端连接起来 也等于将自己摘除出来
        r[l[deleteCol]] = r[deleteCol], l[r[deleteCol]] = l[deleteCol];
        for (int i = d[deleteCol]; i != deleteCol; i = d[i]) {
            for (int j = r[i]; j != i; j = r[j]) {
                u[d[j]] = u[j];
                d[u[j]] = d[j];
                nodeNumPerCol[col[j]]--;
            }
        }
    }
    void resume(int resCol) {//恢复涉及C列的集合 
        for (int i = u[resCol]; i != resCol; i = u[i]) {
            for (int j = l[i]; j != i; j = l[j]) {
                u[d[j]] = j;
                d[u[j]] = j;
                nodeNumPerCol[col[j]]++;
            }
        }
        r[l[resCol]] = resCol;
        l[r[resCol]] = resCol;
    }



    bool dance(int deep) //选取了d行  
    {
        if (r[0] == 0)//全部覆盖了  
        {
            //全覆盖了之后的操作  
            ansd = deep;
            return 1;
        }


        int c = r[0];//表头结点指向的第一个列
        for (int i = r[0]; i != 0; i = r[i])//枚举列头指针
        {
            if (nodeNumPerCol[i] < nodeNumPerCol[c])c = i;

        }

        remove(c);//将该列删去
        for (int i = d[c]; i != c; i = d[i])
        {//枚举该列的元素
            ans[deep] = row[i];//记录该列元素的行
            for (int j = r[i]; j != i; j = r[j])
                remove(col[j]);//将该列的某个元素的行上的元素所在的列都删去
            if (dance(deep + 1))
                return 1;
            for (int j = l[i]; j != i; j = l[j])
                resume(col[j]);
        }
        resume(c);
        return 0;
    }
}dlx;
//==========================================================


char s[90], path[90];
struct node
{
    int r, c, v;
}nds[MN];
int main()
{
    while (~scanf("%s", s))
    {
        if (s[0] == 'e')break;
        dlx.init(9 * 9 * 9, 9 * 9 * 4);
        int r = 1;
        for (int i = 1; i <= 9; i++)
        {
            for (int j = 1; j <= 9; j++)
            {
                if (s[(i - 1) * 9 + j - 1] == '.')
                {
                    for (int z = 1; z <= 9; z++)
                    {
                        dlx.link(r, (i - 1) * 9 + j);
                        dlx.link(r, 81 + (i - 1) * 9 + z);
                        dlx.link(r, 162 + (j - 1) * 9 + z);
                        dlx.link(r, 243 + (((i - 1) / 3) * 3 + (j + 2) / 3 - 1) * 9 + z);
                        nds[r].r = i, nds[r].c = j, nds[r].v = z;
                        r++;
                    }
                }
                else
                {
                    int z = s[(i - 1) * 9 + j - 1] - '0';
                    dlx.link(r, (i - 1) * 9 + j);
                    dlx.link(r, 81 + (i - 1) * 9 + z);
                    dlx.link(r, 162 + (j - 1) * 9 + z);
                    dlx.link(r, 243 + (((i - 1) / 3) * 3 + (j + 2) / 3 - 1) * 9 + z);
                    nds[r].r = i, nds[r].c = j, nds[r].v = z;
                    r++;
                }
            }
        }
        dlx.ansd = -1;
        dlx.dance(0);
        int deep = dlx.ansd;
        for (int i = 0; i < deep; i++)
        {
            int posr = dlx.ans[i];
            path[(nds[posr].r - 1) * 9 + nds[posr].c - 1] = '0' + nds[posr].v;
        }
        path[deep] = '\0';
        printf("%s\n", path);
    }
    return 0;
}

Y总模板

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20000;

int m = 9 * 9 * 4;
int u[N], d[N], l[N], r[N], s[N], col[N], row[N], idx;
int ans[N], top;
struct Op
{
    int x, y;
    char z;
}op[N];
char g[20][9];
char input[90];

void init()
{
    for (int i = 0; i <= m; i++)
    {
        l[i] = i - 1, r[i] = i + 1;
        s[i] = 0;
        d[i] = u[i] = i;
    }
    l[0] = m, r[m] = 0;
    idx = m + 1;
}

void add(int& hh, int& tt, int x, int y)
{
    row[idx] = x, col[idx] = y, s[y] ++;
    u[idx] = y, d[idx] = d[y], u[d[y]] = idx, d[y] = idx;
    r[hh] = l[tt] = idx, r[idx] = tt, l[idx] = hh;
    tt = idx++;
}

void remove(int p)
{
    r[l[p]] = r[p], l[r[p]] = l[p];
    for (int i = d[p]; i != p; i = d[i])
        for (int j = r[i]; j != i; j = r[j])
        {
            s[col[j]] --;
            u[d[j]] = u[j], d[u[j]] = d[j];
        }
}

void resume(int p)
{
    for (int i = u[p]; i != p; i = u[i])
        for (int j = l[i]; j != i; j = l[j])
        {
            u[d[j]] = j, d[u[j]] = j;
            s[col[j]] ++;
        }
    r[l[p]] = p, l[r[p]] = p;
}

bool dfs()
{
    if (!r[0]) return true;
    int p = r[0];
    for (int i = r[0]; i; i = r[i])
        if (s[i] < s[p])
            p = i;
    remove(p);
    for (int i = d[p]; i != p; i = d[i])
    {
        ans[++top] = row[i];
        for (int j = r[i]; j != i; j = r[j]) remove(col[j]);
        if (dfs()) return true;
        for (int j = l[i]; j != i; j = l[j]) resume(col[j]);
        top--;
    }
    resume(p);
    return false;
}

int main()
{
    while (~scanf("%s", input))
    {
        if (input[0] == 'e') break;

        memset(g, 0, sizeof(g[0][0]) * 20 * 9);
        int ii = 0;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                g[i][j] = input[ii++];
            }
        }

        init();

        for (int i = 0, n = 1; i < 9; i++)
            for (int j = 0; j < 9; j++)
            {
                int a = 0, b = 8;
                if (g[i][j] != '.') a = b = g[i][j] - '1';
                for (int k = a; k <= b; k++, n++)
                {
                    int hh = idx, tt = idx;
                    op[n] = { i, j, (char)(k + '1') };
                    add(hh, tt, n, i * 9 + j + 1);
                    add(hh, tt, n, 81 + i * 9 + k + 1);
                    add(hh, tt, n, 81 * 2 + j * 9 + k + 1);
                    add(hh, tt, n, 81 * 3 + (i / 3 * 3 + j / 3) * 9 + k + 1);
                }
            }

        dfs();
        for (int i = 1; i <= top; i++)
        {
            auto t = op[ans[i]];
            g[t.x][t.y] = t.z;
        }


        puts(g[0]);
        //puts("");
    }

    return 0;
}

代码与结构经过自己调整注释
参考链接
https://www.cnblogs.com/ivan-count/p/7355431.html

https://www.cnblogs.com/grenet/p/3145800.html

https://blog.csdn.net/whereisherofrom/article/details/79220897

https://www.luogu.org/blog/ONE-PIECE/qian-tan-dlx 【模板】舞蹈链（DLX）

我的leetcode视频题解空间