Dancing Links（DLX）算法实现：解决精确覆盖问题

一、引言

在我的最近一次对开源社区的贡献中，我实现了用于解决精确覆盖问题的舞动链接（Dancing Links，简称DLX）算法。这一努力是为了处理AlgoGenesis/C仓库中的Issue #1131。我的拉取请求可以在这里找到。

二、理解问题

（一）问题概述

问题要求实现一个符合C11标准的DLX算法。DLX是一个高效的解决精确覆盖问题的方法，例如数独、N皇后问题和多米诺骨牌的铺设。挑战在于创建干净、模块化的、且附带适当注释解释关键部分的代码。

（二）准备工作与环境配置

在开始编码之前，我需要做以下几件事：

• 深入理解DLX算法：尽管我对Algorithm X和精确覆盖问题已经有所了解，但我需要更深入地理解舞动链接是如何优化搜索过程的。
• 参考现有实现：查看其他语言中的实现，了解不同的方法。
• 配置开发环境：确保拥有一个符合C11标准的编译器（如GCC和Clang），并在IDE（Visual Studio Code）中配置好C开发环境。

三、学习与研究

（一）需要学习的知识点

• 数据结构：如何使用循环双向链表表示DLX矩阵。
• 内存管理：在C语言中高效分配和释放内存，特别是处理动态数据结构时。
• 可移植性问题：编写能在MacOS和Linux系统上顺利编译和运行的代码。

（二）进行的研究

• 阅读唐纳德·克努斯的论文《Dancing Links》，理解理论基础。
• 复习C11标准特性，确保代码符合标准。
• 检查论坛和关于用C实现DLX的讨论，避免常见陷阱并学习最佳实践。

四、实现修复

（一）代码解释

数据结构

节点结构

// 表示DLX矩阵中的元素，向四个方向链接（上下左右）
typedef struct Node {
    struct Node *left;   // 左节点指针
    struct Node *right;  // 右节点指针
    struct Node *up;     // 上节点指针
    struct Node *down;   // 下节点指针
    struct Column *col;  // 所属列指针
} Node;

列结构

// 继承自Node，并包含额外的信息如大小和名称
typedef struct Column {
    Node node;     // 节点头
    int size;      // 列中1的数量
    char name[20]; // 调试用标识符
} Column;

根节点

// 作为一个特殊的Column节点，作为遍历矩阵的起点
static Column root;

初始化

// 设置循环链接的列头
void initialize_dlx(int cols) {
    root.node.right = &root.node;
    root.node.left = &root.node;

    for (int i = 0; i < cols; i++) {
        Column *col = (Column *)malloc(sizeof(Column)); // 分配内存
        if (!col) {
            fprintf(stderr, "Memory allocation failed for column headers.\n"); // 分配失败提示
            exit(EXIT_FAILURE); // 结束程序
        }
        col->size = 0;
        snprintf(col->name, sizeof(col->name), "C%d", i); // 设置列名
        col->node.up = &col->node;
        col->node.down = &col->node;
        col->node.col = col;

        // 将新列插入到头部列表
        col->node.right = root.node.right;
        col->node.left = &root.node;
        root.node.right->left = &col->node;
        root.node.right = &col->node;
    }
}

添加行

// 添加行到矩阵中
void add_row(int *row_data, int row_size, char *row_name) {
    Node **row_nodes = malloc(row_size * sizeof(Node *)); // 动态分配内存
    if (!row_nodes) {
        fprintf(stderr, "Memory allocation failed for row_nodes.\n"); // 分配失败提示
        exit(EXIT_FAILURE); // 结束程序
    }

    // ... (函数其余部分)

    free(row_nodes); // 释放内存
}

覆盖和揭开列

覆盖列

// 移除一列及其所有含有该列1值的行
void cover(Column *col) {
    col->node.right->left = col->node.left;
    col->node.left->right = col->node.right;

    for (Node *row = col->node.down; row != &col->node; row = row->down) {
        for (Node *node = row->right; node != row; node = node->right) {
            node->down->up = node->up;
            node->up->down = node->down;
            node->col->size--; // 减少列中1的数量
        }
    }
}

揭开列

// 恢复先前覆盖的列及其行
void uncover(Column *col) {
    for (Node *row = col->node.up; row != &col->node; row = row->up) {
        for (Node *node = row->left; node != row; node = node->left) {
            node->col->size++; // 增加列中1的数量
            node->down->up = node;
            node->up->down = node;
        }
    }

    col->node.right->left = &col->node;
    col->node.left->right = &col->node;
}

（二）搜索函数

// 实现递归搜索算法X以查找所有解决方案
void search(int k) {
    if (root.node.right == &root.node) {
        // 找到解决方案
        printf("Solution %d:\n", ++solution_count);
        for (int i = 0; i < k; i++) {
            // 输出行标识符
            printf("Row: ");
            Node *n = solution[i];
            do {
                printf("%s ", n->col->name);
                n = n->right;
            } while (n != solution[i]);
            printf("\n");
        }
        return;
    }

    Column *col = choose_column(); // 选择列
    if (!col || col->size == 0) return;

    cover(col); // 覆盖选中的列

    for (Node *row = col->node.down; row != &col->node; row = row->down) {
        solution[k] = row; // 记录当前行
        for (Node *node = row->right; node != row; node = node->right) {
            cover(node->col); // 覆盖当前行中的列
        }
        search(k + 1); // 递归搜索
        for (Node *node = row->left; node != row; node = node->left) {
            uncover(node->col); // 揭开当前行中的列
        }
    }

    uncover(col); // 揭开列
}

五、演示：修复前后的对比

（一）修复前

编译错误

使用VLA导致编译器抛出错误：

expression must have a constant value

这是因为VLA在C11标准中不是强制支持的，而且某些编译器或IDE（如Visual Studio Code的IntelliSense）可能无法识别它们。

（二）修复后

成功编译

用动态内存分配代替VLA解决了问题，代码编译无错误或警告。

执行

运行程序产生了提供的精确覆盖问题的预期解决方案。

Solution 1:
Row: C2 C4 C5 
Row: C0 C3 C6 

六、遇到的挑战

（一）编译错误

问题

最初使用VLA导致某些系统上的编译错误。

解决办法

用malloc和free替换VLA来动态分配内存，确保跨不同编译器和系统的兼容性。

（二）内存管理

挑战

在C中管理动态内存分配需要小心处理以避免内存泄漏和段错误。

方法

确保每次malloc都有相应的free，并检查分配失败的情况。

（三）理解算法

复杂度

DLX算法在多个链表中操作指针的过程可能很复杂。

克服方法

绘制图表来可视化数据结构，并使用调试器逐步跟踪代码执行流程。

七、与项目维护者的互动

我与项目维护者进行了富有成效的交流。提交初始拉取请求后，他们提供了关于代码风格和文档的反馈。他们强调了遵循C11标准和确保代码可移植性的重要性。他们的指导帮助我完善了实现。

八、结论

1. 解决这个问题是一次宝贵的学习经历。我对DLX算法有了更深的理解，提高了我的C编程技能，并且为一个可以帮助他人高效解决精确覆盖问题的开源项目做出了贡献。
2. 这次经验不仅增强了我的技术能力，还让我更加熟悉了开源协作的流程。