Acwing166 数独题解 - DFS剪枝优化

166. 数独 - AcWing题库

题意

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

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

思路

搜索+剪枝(优化搜索顺序、位运算)

• 优化搜索顺序:很明显,我们肯定是从当前能填合法数字最少的位置开始填数字
• 位运算:很明显这里面check判定很多,我们必须优化这个check,所以我们可以对于,每一行,每一列,每一个九宫格,都利用一个九位二进制数保存,当前还有哪些数字可以填写.
• lowbit:我们这道题目当前得需要用lowbit运算取出当前可以能填的数字.

code + 详细注释

#include <iostream>

#define lowbit(x) (x & -x) // lowbit操作
#define get(x, y) (row[x] & col[y] & cell[x / 3][y / 3]) // get(x, y) 找到该位置可以填哪些数的状态

using namespace std;

const int N = 9, M = 1 << N;

int one[M], map[M]; // one[state]为该state中有几个1, map[state]为state对应的十进制值
int col[N], row[N], cell[3][3];
char str[100];

void init() { // 初始化(将所有位置都初始化可以填数的状态)
    for (int i = 0; i < N; ++ i) row[i] = col[i] = (1 << N) - 1; 
    // 将行和列都用二进制来优化(刚开始的位置都为1)

    for (int i = 0; i < 3; ++ i)
        for (int j = 0; j < 3; ++ j)
            cell[i][j] = (1 << N) - 1; // 每个3 * 3的小方格也用二进制来优化(刚开始也都为1)
}

void draw(int x, int y, int t, bool is_set) { // 在(x, y)的位置上(is_set)<是/否>填t的操作 
    if (is_set) str[x * N + y] = '1' + t; // 如果填数的话, 将该数转换为字符形式填入字符串中对应的位置
    else str[x * N + y] = '.'; // 否则说明字符串该位置上填的是'.';

    int v = 1 << t; // 找到该数对应二进制之后的位置的数
    if (!is_set) v = -v; // 如果该位置不填数，则将该数取负

    row[x] -= v; //在这个原数对应的行减去该数的二进制数
    col[y] -= v; // 在这个原数对应的列减去该数的二进制数
    cell[x / 3][y / 3] -= v; // 在这个原数对应的小方格减去该数的二进制数
}

bool dfs(int cnt) {
    if (!cnt) return true; // 知道没有位置能填数就结束搜索

    int minv = 10; // 记录当前最少枚举方案
    int x, y; // x, y记录枚举方案最少的位置的x, y

    for (int i = 0; i < N; ++ i)
        for (int j = 0; j < N; ++ j)
            if (str[i * N + j] == '.') { // 该位置对应的字符串位置上为'.', 才说明能填数
                int state = get(i, j); // 找到该位置上能填的数的状态
                if(one[state] < minv) { // 只有当当前位置的方案少于当前最少方案才有搜索的必要
                    x = i, y = j;
                    minv = one[state];
                }
            }

    int state = get(x, y); // 找到最少枚举方案对应的位置的能填的数的状态
    for (int i = state; i; i -= lowbit(i)) { // 枚举该位置上能填的数，用lowbit操作
        int t = map[lowbit(i)]; // 找到该位置上能填的数
        draw(x, y, t, true); // 填数
        if (dfs(cnt - 1)) return true; // 继续搜索
        draw(x, y, t, false); // 恢复
    }

    return false;
}

int main() {
    for (int i = 0; i < N; ++ i) map[1 << i] = i; // 预处理map[]

    for (int i = 0; i < 1 << N; ++ i)
        for (int j = 0; j < N; ++ j)
            one[i] += (i >> j & 1); // 预处理one[]

    while (cin >> str, str[0] != 'e') { // 多组输入
        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'; // 找到该位置上的数
                    draw(i, j, t, true); // 在该位置上填上该数
                }
                else cnt ++ ; // 否则说明该位置需要填数
            }

        dfs(cnt); // 开始搜索

        puts(str); // 输出答案
    }

    return 0; // 结束快乐~
}

作者：Hustle
链接：https://www.acwing.com/solution/content/57159/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。