舞蹈链(Dance Link X)算法生成数独和解数独 C语言实现

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

// 定义数独的大小
#define SIZE 9

int sudoku[SIZE][SIZE];

// 定义DLX节点结构
typedef struct Node {
    struct Node *left, *right, *up, *down;
    struct ColumnNode *column;
    int row, col;
} Node;

// 辅助节点
typedef struct ColumnNode {
    struct Node *head;
    int size;
    int col;
} ColumnNode;

// 辅助约束列，方便定位到哪一列 432个约束条件
ColumnNode *columns[4*SIZE*SIZE];
Node *root;

int answers[81];


//==========================  生成数独 ==================================

// 随机生成一定个数的初始数字 (即先在数独中填入几个数字)
int initConstraint[4*SIZE*SIZE]={0};
void initLocationDict(int initCount) {
    srand(time(NULL));
    for (int num = 0; num < initCount; num++)
    {
        while (true)
        {
            printf("随机生成数字\n");
            int i = rand() % SIZE;
            int j = rand() % SIZE;
            int k = rand() % SIZE + 1;
            printf("num=%d,i=%d,j=%d,k=%d\n", num, i, j, k);

            int a = i * 9 + j;
            printf("%d\n", initConstraint[a] );
            if (initConstraint[a] == 1) continue;
            int b = i * 9 + k + 80;
            printf("%d\n", initConstraint[b] );
            if (initConstraint[b] == 1) continue;
            int c = j * 9 + k + 161;
            printf("%d\n", initConstraint[c] );
            if (initConstraint[c] == 1) continue;
            int d = (i / 3 * 3 + j / 3) * 9 + k + 242;
            printf("%d\n", initConstraint[d] );
            if (initConstraint[d] == 1) continue;

            initConstraint[a] = 1;
            initConstraint[b] = 1;
            initConstraint[c] = 1;
            initConstraint[d] = 1;
            sudoku[i][j] = k;
            printf("随机生成第%d个数字%d,i=%d,j=%d \n", num, k, i, j);
            break;
        }
    }
    
}

// 初始化DLX列节点（哨兵列）
void initialize(){
    // 根节点
    root = (Node *)malloc(sizeof(Node));
    root->left = root;
    root->right = root;
    root->up = root;
    root->down = root;

    Node *prev = root;
    // 列节点
    for (int i = 0; i < 4 * SIZE * SIZE; i++) {
        Node *node = (Node *)malloc(sizeof(Node));
        prev->right = node;
        node->left = prev;
        node->right = root;
        node->up = node;
        node->down = node;
        node->col = i;
        
        columns[i] = (ColumnNode *)malloc(sizeof(ColumnNode));
        columns[i]->head = node; // 指向每一列的第一个节点
        columns[i]->size = 0;
        columns[i]->col = i;

        node->column = columns[i];
        prev = node;
    }


}

// 添加[i,j,k]相关的4个约束到十字链表中的同一行
void appendRow(int *cs, int row_id){
    Node *prev;
    Node *first;
    for (int i = 0; i < 4; i++)
    {
        int col_id = cs[i];
        Node *node = (Node *)malloc(sizeof(Node));
        Node *head = columns[col_id]->head;
        Node *tail = head->up;

        node->row = row_id;
        node->col = col_id;
        node->column = columns[col_id];

        tail->down = node;
        node->up = tail;
        node->down = head;
        head->up = node;

        ++columns[col_id]->size;// 列元素的数量+1
        
        if (i == 0)
        {
            first = node;
            node->left = node;
            node->right = node;
            prev = node;
        } else{
            node->right = prev->right;
            node->right->left = node;
            prev->right = node;
            node->left = prev;
        }
    }
}

// 生成DLX十字链表
void build(){
    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < SIZE; j++)
        {
            if (sudoku[i][j] != 0) // 11个格子已经随机生成的数字 占用十字链表的11行, 每行4个约束即4个Node
            {
                int k = sudoku[i][j];
                int cs[4];
                cs[0] = i * 9 + j;
                cs[1] = i * 9 + k + 80;
                cs[2] = j * 9 + k + 161;
                cs[3] = (i / 3 * 3 + j / 3) * 9 + k + 242;
                int row_id = (i * 9 + j) * 9 + k - 1;
                appendRow(cs, row_id);

            } else { // 其他没有生成的70个格子，每个格子有9种可能数字1-9，需要占用十字链表的70*9=630行，每行4个约束即4个Node
                for (int k = 1; k < 10; k++) {
                    int cs[4];
                    cs[0] = i * 9 + j;
                    cs[1] = i * 9 + k + 80;
                    cs[2] = j * 9 + k + 161;
                    cs[3] = (i / 3 * 3 + j / 3) * 9 + k + 242;
                    int row_id = (i * 9 + j) * 9 + k - 1;
                    appendRow(cs, row_id);
                }

            }
        }
    }
}

void removeCol(ColumnNode *columnNode){
    Node *head = columnNode->head;
    head->right->left = head->left;
    head->left->right = head->right;
    for (Node *row = head->down; row != head; row = row->down)
    {
        for (Node *j = row->right; j != row; j = j->right) {
            j->down->up = j->up;
            j->up->down = j->down;
            columns[j->col]->size--;
        }
    }
}

void restoreCol(ColumnNode *columnNode){
    Node *head = columnNode->head;
    for (Node *row = head->up; row != head; row = row->up) {
        for (Node *j = row->left; j != row; j = j->left) {
            j->down->up = j;
            j->up->down = j;
            columns[j->col]->size++;
        }
    }
    head->right->left = head;
    head->left->right = head;
}


// 递归dance
// 如果 0 号结点没有右结点，那么矩阵为空，记录答案并返回；
// 选择列元素个数最少的一列，并删掉这一列；
// 遍历这一列所有有 1 的行，枚举它是否被选择；
// 递归调用 dance()，如果可行，则返回；如果不可行，则恢复被选择的行；
// 如果无解，则返回。
bool dance(int dep){
    // 哨兵列为空，说明所有列都有1，所有列的约束都被满足了了
    if (root->right == root) return true;
    
    // 如果有某列没有node，即该列没有1，即该列的约束无法满足
    for (Node *node = root->right; node != root; node = node->right)
    {
        if (node->down == node) return false; 
    }

    // 取每列中1的数量最少一列的开始dance
    int col = root->right->col;
    for (Node *node = root->right; node != root; node = node->right)
    {
       if (node->column->size < columns[col]->size) col = node->column->col;
    }
    
    ColumnNode *columnNode = columns[col];
    removeCol(columnNode);
    for (Node *row = columnNode->head->down; row != columnNode->head; row = row->down) {
        answers[dep] = row->row;
        for (Node *j = row->right; j != row; j = j->right) removeCol(columns[j->col]);
        if (dance(dep + 1)) return true;
        for (Node *j = row->left; j != row; j = j->left) restoreCol(columns[j->col]);
    }
    restoreCol(columnNode);
    return false;
}

// 将十字链表中行号转为数独的位置和值
void formattedAnswer(){
    for (int i = 0; i < 81; i++)
    {
        int row_id = answers[i];
        int loc = row_id / 9;
        int i = loc / 9;
        int j = loc % 9;
        int k = row_id % 9 + 1;
        sudoku[i][j] = k;
    }
}

// 打印数独
 printsudoku(){
    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < SIZE; j++)
        {
            printf("%d,", sudoku[i][j]);
        }
        printf("\n");
    }

 }


// 校验唯一解
bool checkUniqueSolution(){
    // todo
}


int main(int argc, char const *argv[])
{
    
    initLocationDict(11); // 生成 11个 初始数字，因为11个填入后 能生成数独的概率最大。12个就小一点
    printsudoku(); // 打印 填入的11个数字的数独
    printf("\n");

    initialize(); // 初始化 哨兵列节点 和 辅助列节点
    build(); // 构建DLX十字循环链表
    //dance(0); // 开始执行DLX算法
    while (!dance(0)) // 如果没有解，重新生成，因为即使使用11的初始数字的能生成数独的概率最大，但也不是100%
    {
    }

    formattedAnswer(); // 将DLX的答案转为二维数组（数独形式）
    printsudoku(); // 打印最终生的数独
    printf("\n");

    // 挖洞
    // 校验唯一解
    // 解法打分，判断难度


    return 0;
}