题目链接

算法竞赛进阶指南-80.数独

数独 是一种传统益智游戏，你需要把一个 $9 \times 9$ 的数独补充完整，使得数独中每行、每列、每个 $ 3 \times 3 $ 的九宫格内数字 $1 \sim 9$ 均恰好出现一次。

请编写一个程序填写数独。

输入格式

输入包含多组测试用例。

每个测试用例占一行，包含 $81$ 个字符，代表数独的 $81$ 个格内数据（顺序总体由上到下，同行由左到右）。

每个字符都是一个数字（$1-9$）或一个 .（表示尚未填充）。

您可以假设输入中的每个谜题都只有一个解决方案。

文件结尾处为包含单词 end 的单行，表示输入结束。

输出格式

每个测试用例，输出一行数据，代表填充完全后的数独。

输入样例：

4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end

输出样例：

417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936

Method : DFS

最初的dfs：

step1：每次随机选择一个未填数字的格子

step2：每次根据数独规则，枚举当前数字可以选哪些有效数字，->dfs()

这个无优化的dfs会因为搜索空间太大而TLE，需要做优化：

step1优化：每次优先选择可选数字最少的格子（优化搜索顺序）
具体而言：可以用bitset<9> row[i], col[j], cell[i]来用二进制状态压缩，表示当前某行某列某格的可选数字

#include <iostream>
#include <cstring>

using namespace std;

const int N = 9;
const int M = 81 + 7;

int one[1 << N], map[1 << N];
int row[N], col[N], cell[N][N];
char str[M];


inline int lowbit(int x) {
    return x & -x;
}

void init() {
    for (int i = 0; i < N; i ++) {
        row[i] = (1 << N) - 1;
        col[i] = (1 << N) - 1;
    }
    for (int i = 0; i < 3; i ++) {
        for (int j = 0; j < 3; j ++) {
            cell[i][j] = (1 << N) - 1;
        }
    }
}

inline int get(int x, int y) {
    return row[x] & col[y] & cell[x / 3][y / 3];
}

bool dfs(int cnt) {
    // boundary
    if (cnt == 0) return true;
    
    // 优化搜索顺序：优先选取可选数量最少的点
    int one_min = 10;
    int x, y;
    for (int i = 0; i < N; i ++) {
        for (int j = 0; j < N; j ++) {
            if (str[i * 9 + j] == '.') {
                int t = one[get(i, j)];
                if (t < one_min) {
                    one_min = t;
                    x = i, y = j;
                }
            }
        }
    }
    
    // 枚举可选数字
    for (int i = get(x, y); i; i -= lowbit(i)) {
        int t = map[lowbit(i)];
        
        row[x] -= 1 << t;
        col[y] -= 1 << t;
        cell[x / 3][y / 3] -= 1 << t;
        str[x * 9 + y] = '1' + t;
        
        if (dfs(cnt - 1)) return true;
        
        // recover
        row[x] += 1 << t;
        col[y] += 1<< t;
        cell[x / 3][y / 3] += 1 << t;
        str[x * 9 + y] = '.';
    }
    
    return false;
}


int main() {
    // 对1~9 (0~8)做映射
    for (int i = 0; i < N; i ++) map[1 << i] = i;
    for (int i = 0; i < 1 << N; i ++) {
        for (int j = i; j; j -= lowbit(j)) {
            one[i] ++; // i的二进制表示中有one[i]个1
        }
    }
    
    while (cin >> str, strcmp(str, "end")) {
        init();
        
        int cnt = 0;
        for (int i = 0, k = 0; i < N; i ++) {
            for (int j = 0; j < N; j ++, k ++) {
                if (str[k] != '.') {
                    int t = str[k] - '1';
                    row[i] -= 1 << t;
                    col[j] -= 1 << t;
                    cell[i / 3][j / 3] -= 1 << t;
                    
                }
                else {
                    cnt ++;
                }
            }
        }
        
        dfs(cnt);
        
        cout << str << endl;
        // for (int i = 0; i < 81; i ++) {
        //     printf("%c", str[i]);
        // }
        // puts("");
    }
    
    return 0;
}

复杂度分析

• 时间复杂度：${O(cnt * N^2 * N)}$。

• 空间复杂度：${O(N^2)}$。

Method：Dancing Link (DLX)

数独这种精确覆盖问题，可以用DLX，等我学会了再补~.