Sudoku

来自蓝书

思路

优化搜索顺序，位运算常数优化。

优化搜索顺序

数独问题的搜索很简单，“搜索状态”就是每个位置上填了什么数。在每个状态下，选择一个未填位置，检查那些填入仍能满足数独条件（合法）的数字。构成的新的局面即为该状态的“分支”。

足够暴力的写法为依次对每个位置进行搜索，但盲目搜索的效率肯定相当低，如果让人类玩数独的话，我们会先填已经能唯一确定的位置，这样就可以减少其他位置的合法数字，使数独的复杂程度降低。

在搜索中，我们也可以采取类似的策略，从能填的合法数字最少的位置向下搜索，这样就能大大减少分支数量，也就是优化顺序的剪枝方法。

常数优化

1. 对于每行每列每个九宫格，分别用一个 9 位二进制保存有那些数能用。
2. 对于每个数字，把它所在的行、列、九宫格的三个二进制数做按位与运算，就可以知道该位置可以填那些数，再用 lowbit 运算就可以将能填的数字取出。
3. 当一个位置上填上某个数后，把该位置所在行、列、九宫格的二进制数对应位改为 0 更新装态，回溯时改为 1 还原现场。可以联想利用异或的性质。
4. 用 lowbit 运算预处理每个 9 位二进制数有几位 1 ，即可快速确定能填的合法数字最少的位置
5. 打表确定用 lowbit 运算取出来的位置对应的数字

代码

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1 << 9;

int cnt[N], f[N], T, sukodu[9][9], x[9], y[9], z[9];
char c;

int gon(int i, int j) { return i / 3 * 3 + j / 3; }

int get_cnt(int i)
{
    int ans = 0;
    while(i)
        ans++, i -= (i & -i);
    return ans;
}

void work(int i, int j, int v)
{
    x[i] ^= (1 << v);
    y[j] ^= (1 << v);
    z[gon(i, j)] ^= (1 << v);
}

bool dfs(int tot)
{
    if (!tot) return true;

    int t = 10, nx, ny;

    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
        {
            if (!sukodu[i][j])
            {
                int w = x[i] & y[j] & z[gon(i, j)]; // 优化2
                if (cnt[w] < t)
                    nx = i, ny = j, t = cnt[w];
            }
        }

    int w = x[nx] & y[ny] & z[gon(nx, ny)];
    while(w)
    {
        int now = f[w & -w];
        sukodu[nx][ny] = now + 1;
        work(nx, ny, now);
        if (dfs(tot - 1)) return true;

        sukodu[nx][ny] = 0;
        work(nx, ny, now);
        w -= w & -w;
    } 
    return false;
}

int main()
{
    for (int i = 0; i < N; i++) cnt[i] = get_cnt(i); //优化4
    for (int i = 0; i < 9; i++) f[1 << i] = i;  // 优化5

    scanf("%d", &T);
    while(T--)
    {
        int tot = 0;
        for (int i = 0; i < 9; i++) x[i] = y[i] = z[i] = N - 1; // 优化1

        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
            {
                cin >> c;
                sukodu[i][j] = c - '0';
                if (sukodu[i][j]) work(i, j, sukodu[i][j] - 1); // 优化3
                else tot++;
            }

        if (dfs(tot))
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                    printf("%d", sukodu[i][j]);
                puts("");
            }
    }
    return 0;
}

后记

这道题目数据很水，完全不需要优化就能过，这很明显
但作为蓝书的题目，我想应该要有蓝书的写法，我是蒟蒻，我写不来蓝书的方法，我想也有人不会，所以发出来给像我这样的蒟蒻参考
位运算优化会快很多，我的代码实测为 4ms ，比大多数题解快一些