Dancing Links X求解数独

输入未填的数独,空位用$0$表示,输出填好的数独.

前言

很早之前学的东西,写一下题解方便以后复习.

思路

数独的解使得每行、每列、每个粗线宫中数字$1\sim 9$各出现一次.若用$0$表示不选该数码,$1$表示选该数码,则求解数独可转化为若干个$1$的精确覆盖问题,用Dancing Links X求解.

到底是几个$1$?来分析一下:

首先填数独的每个决策可用一个三元组$(r,c,v)$表示,即在$(r,c)$处填入数$v$,因为每个$(r,c)$所在的粗线宫可由$r$和$c$计算出,故DLX中记录答案的数组有$9\times 9\times 9=729$行.

考虑决策$(r,c,v)$造成的影响:①第$r$行用了一个$v$  (用$9\times 9=81$列表示);②第$c$列用了一个$v$  (用$9\times 9=81$列表示);③在$(r,c)$所在的box中用了一个$v$  (用$9\times 9=81$列表示);④在$(r,c)$中填入$v$  (用$9\times 9=81$列表示),故DLX中记录答案的数组有$9\times 9\times 4=324$列,参与精确覆盖的共$729\times 4=2916$个$1$.

综上,$9\times 9$的数独求解转化为$729$行、$324$列、$2916$个$1$的精确覆盖问题.

Dancing Links X用双向十字链表维护,具体的实现见下面的代码,注释很清晰,不再赘述.

代码

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
#define endl '\n'

const int a = 9 * 9 * 9;  // 每个决策都是在(r,c)处填入数v,每个变量有9种选择
const int b = 9 * 9 * 4;  // 每个决策(r,c,v)将产生4个影响:
                          // ①第r行用了一个v  (用9*9=81列表示)
                          // ②第c列用了一个v  (用9*9=81列表示)
                          // ③在(r,c)所在的box中用了一个v  (用9*9=81列表示)
                          // ④在(r,c)中填入v  (用9*9=81列表示)
// 9*9的数独转化为9*9*9*4=2916个1的精确覆盖问题
const int N = a * b + 5;  // DLX记录答案的数组的大小

int ans[10][10];  // 数独答案
int stk[N] = { 0 };  // DLX中记录答案的数组

struct DLX {  // Dancing Links X
    static const int MaxSize = 1e5 + 5;  // DLX记录各方向元素的数组的大小
    int n, m;  // 行数、列数
    int idx;  // 要插入的元素
    int first[MaxSize] = { 0 };  // 行指示
    int siz[MaxSize] = { 0 };  // 每列元素个数
    int L[MaxSize], R[MaxSize], U[MaxSize], D[MaxSize];  // 双向十字链表左右上下的元素
    int row[MaxSize], col[MaxSize];  // 行、列

    void build(int r, int c) {  // 新建一个r行c列的DLX
        n = r, m = c;  // 行数、列数
        for (int i = 0; i <= c; i++) {
            L[i] = i - 1;  // 第i个节点的左节点指向i-1
            R[i] = i + 1;  // 第i个节点的右节点指向i+1
            U[i] = D[i] = i;  // i的上下节点都指向i
        }
        L[0] = c;  // 0节点的左节点指向c
        R[c] = 0;  // c节点的右节点指向0
        idx = c;
    }

    void insert(int r, int c) {  // 在(r,c)处插入节点
        col[++idx] = c, row[idx] = r;
        siz[c]++;  // 更新列元素个数
        D[idx] = D[c];  // idx的下节点指向原来c的下节点
        U[D[c]] = idx;  // idx的下节点(即原来c的下节点)的上节点指向idx
        U[idx] = c;  // idx的上节点指向c
        D[c] = idx;  // c的下节点指向idx

        if (!first[r])  // 若第r行无元素,则插入元素,并让first[r]指向该元素
            first[r] = L[idx] = R[idx] = idx;
        else {
            R[idx] = R[first[r]];  // idx的右节点指向原来first[r]的右节点
            L[R[first[r]]] = idx;  // 原来first[r]的右节点的左节点指向idx
            L[idx] = first[r];  // idx的左节点指向first[r]
            R[first[r]] = idx;  // first[r]的右节点指向idx
        }
    }

    void remove(int c) {  // 删除第c列及其相关行列
        L[R[c]] = L[c];  // c左节点的右节点指向c的右节点
        R[L[c]] = R[c];  // c右节点的左节点指向c的左节点
        for (int i = D[c]; i != c; i = D[i]) {  // 沿该列从上往下遍历
            for (int j = R[i]; j != i; j = R[j]) {  // 沿该行从左往右遍历
                U[D[j]] = U[j];  // j的上节点的下节点指向j的下节点
                D[U[j]] = D[j];  // j的下节点的上节点指向j的上节点
                siz[col[j]]--;  // 更新每列的元素个数
            }
        }
    }

    void recover(int c) {  // 还原第c列及其相关行列,操作与remove相反
        for (int i = U[c]; i != c; i = U[i]) {  // 沿该列从下往上遍历
            for (int j = L[i]; j != i; j = L[j]) {  // 沿该行从右往左遍历
                U[D[j]] = D[U[j]] = j;  // j的上节点的下节点、下节点的上节点都指向j
                siz[col[j]]++;  // 更新每列的元素个数
            }
        }
        L[R[c]] = R[L[c]] = c;  // c的右节点的左节点、左节点的右节点都指向c
    }

    bool dance(int dep) {  // 递归地删除和还原各行列,直至找到一组解
        if (!R[0]) {  // 若0节点无右节点,则矩阵已空,记录答案并返回
            for (int i = 1; i < dep; i++) {
                int x = (stk[i] - 1) / 9 / 9 + 1;
                int y = (stk[i] - 1) / 9 % 9 + 1;
                int value = (stk[i] - 1) % 9 + 1;
                ans[x][y] = value;  // 记录解
            }
            return true;  // 找到一组解,返回
        }

        int c = R[0];
        for (int i = R[0]; i != 0; i = R[i]) {  // 从左往右遍历
            if (siz[i] < siz[c])  // 找到列元素个数最少的一列
                c = i;
        }
        remove(c);  // 优先选择列元素最少的一列进行删除,剪枝
        for (int i = D[c]; i != c; i = D[i]) {  // 从上往下遍历该列所有有1的行,枚举它们是否被选择
            stk[dep] = row[i];
            for (int j = R[i]; j != i; j = R[j])
                remove(col[j]);
            if (dance(dep + 1))  // 递归调用dance,若可行,则返回;否则恢复被选择的行
                return true;  // 找到一组解,返回
            for (int j = L[i]; j != i; j = L[j])  // 从右往左遍历
                recover(col[j]);
        }
        recover(c);
        return false;  // 删除和还原所有行列后仍找不到解,则无解
    }
}solver;

int GetID(int row, int col, int val) {  // 在(row,col)处填入值val,获取该决策在数组中的下标
    return (row - 1) * 9 * 9 + (col - 1) * 9 + val;
}

void Insert(int row, int col, int val) {  // 在(row,col)处填入值val,
    int dx = (row - 1) / 3 + 1;
    int dy = (col - 1) / 3 + 1;
    int box = (dx - 1) * 3 + dy;  // 所在的3*3格子
    int id = GetID(row, col, val);  // 插入位置的横坐标
    int f[4];  // 插入位置的纵坐标
    f[0] = (row - 1) * 9 + val;
    f[1] = 81 + (col - 1) * 9 + val;
    f[2] = 81 * 2 + (box - 1) * 9 + val;
    f[3] = 81 * 3 + (row - 1) * 9 + col;
    for (int i = 0; i < 4; i++)
        solver.insert(id, f[i]);  // 插入节点
}

int main() {
    IOS;
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    // ----------------------------------------------------------------

    solver.build(a, b);
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            cin >> ans[i][j];
            for (int k = 1; k <= 9; k++) {
                if (ans[i][j] && ans[i][j] != k)
                    continue;
                Insert(i, j, k);  // 在(i,j)处填入k
            }
        }
    }

    solver.dance(1);  // 求解

    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) 
            cout << ans[i][j] << ' ';
        cout << endl;
    }

    // ----------------------------------------------------------------
#ifndef ONLINE_JUDGE
    cout << endl << "ok" << endl;
#endif
    return 0;
}