算法

(爆搜,剪枝)

爆搜：

• 爆搜枚举所有未填格子能填的数
• 边界：所有数都填完

剪枝：

• 对于每个未填格子，若只有一个可填字母，那么将其填上
• 对于每个未填格子，若一个字母都不能填，则无解，返回
• 对于每行，
  • 若每个字母不能出现在其任意位置，则无解，返回
  • 若若某个字母只能填在一个未填位置，那么将其填上
• 对于每列，同行
• 对于每个 $4 \times 4$ 方格，同行
• 每次爆搜填的格子时，找到一个可填方案数最少的格子填

详见代码及注释

优化：

• 每个格子备选方案用一个二进制数存储

时间复杂度

爆搜这种东西。。一直都是玄学复杂度的。。

C++ 代码

#include <cstdio>
#include <cstring>

const int N = 16;    // 数独边长
const int M = 65536; // 每个状态能填情况的数量（2 ^ N）
const int S = 257;   // 数独大小

unsigned short state[N][N];       // 存数独每个格子能填的数（用一个二进制串表示）
unsigned short bstate1[S][N][N];  // 状态备份数组 1。考虑最坏情况，即每层 dfs 都备份一遍，一共最多 dfs S 层，所以大小开到 S。
unsigned short bstate2[S][N][N];  // 状态备份数组 2
unsigned short ones[M], log_2[M]; // ones[i] 存 i 的二进制中 1 的个数。log_2 [i] 存 i 以 2 为底的对数（只存 2 的整次幂）
char str[N][17];     // 存输入的数独，读入时每行后面会自动加一个 '\0'，所以每个串要开到 17。
char bstr[S][N][17]; // 数独备份数组

 // 将数独中 (x, y) 位置的数该位 t
void draw(int x, int y, unsigned short t)
{
    str[x][y] = t + 65;   // 首先在数独上将 (x, y) 改为 t
    t = ~(1 << t);        // 让 t 变为二进制中第 t 位为 0 的数，方便后面计算
    for (int i = 0; i < N; i ++ ) // 枚举 行/列
    {
        state[x][i] &= t; // 第 x 行第 i 列的数不能再填 t，将其第 t 位制为 0
        state[i][y] &= t; // 第 i 行第 y 列的数不能再填 t，将其第 t 位制为 0
    }
    int a = x / 4 * 4, b = y / 4 * 4; // 取出 (x, y) 所在的 4 * 4 方格的左上角下标
    for (int i = 0; i < 4; i ++ )     // 枚举这个 4 * 4 方格中的所有数
        for (int j = 0; j < 4; j ++ )
            state[a + i][b + j] &= t; // 所有数都不能填 t，将其第 t 位制为 0
    state[x][y] = ~t;     // (x, y) 位填上 t，不能再填其它数，将其除 t 位以外都制成 0
}

// 将 bstate1 和 bstr 的第 cnt 层分别复制到 state 和 str 中，并返回 false
// 由于在 dfs 中用到的比较多，这里单独用一个函数写一下，简化代码。
bool remove(int cnt)
{
    memcpy(state, bstate1[cnt], sizeof state);
    memcpy(str, bstr[cnt], sizeof str);
    return false;
}

// 爆搜
bool dfs(int cnt)
{
    // 如果 cnt 为 0，说明填完了，返回 true
    if (!cnt) return true;

    // 先将数独的状态备份一下
    int kcnt = cnt; // 由于在填的时候会让 cnt -- ，所以在调用 remove 的时候不能直接传入 cnt。要把 cnt 也备份下
    memcpy(bstate1[kcnt], state, sizeof state);
    memcpy(bstr[kcnt], str, sizeof str);

    // 剪枝 1: 对于每行，若只有一个可填字母，那么将其填上
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            if (str[i][j] < 65 && ones[state[i][j]] == 1)
            {
                draw(i, j, log_2[state[i][j]]);
                cnt -- ;
            }

    // 剪枝 2: 若某个位置不能填数，则无解，remove 并返回
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            if (!state[i][j])
                return remove(kcnt);

    // 剪枝 3: 对于每行
    // 如果某个字母不能出现在任意位置，则无解，remove 并返回
    // 如果存在一个数只能填到一个未填位置，那么填上；
    for (int i = 0; i < N; i ++ )
    {
        // drawn 记录所有已经填上的数，
        // sor 记录该行每个元素可选方案的并集，
        // sand 记录该行所有可选方案中，只出现 1 次或 0 次的数的集合（先假定所有数都合法，再筛掉不合法的）
        unsigned short drawn = 0, sor = 0, sand = M - 1;
        for (int j = 0; j < N; j ++ )
        {
            // sor 是 j 以前所有可选方案的并集，
            // state[i][j] 是当前数可选的方案，
            // sor & state[i][j] 是 j 及以前所有至少出现两次的字母，
            // 所以这个操作即为：在 sand 中，把所有在 j 及以前至少出现两字的字母筛掉
            sand &= ~(sor & state[i][j]);
            // 将 (i, j) 的可选方案计入 sor
            sor |= state[i][j];
            // 如果该位置已经填上数，将该位置上的数计入 drawn
            if (str[i][j] != 45) drawn |= state[i][j];
        }

        // 如果可选方案并集不为所有数，说明存在某个字母不能出现在该行中的任意位置，remove 并返回
        if (sor != M - 1) return remove(kcnt);

        // sand 记录所有出现 0/1 次的数，
        // 由于 sor == M - 1（否则就跳到上面那个 if 里去了），说明没有出现 0 次的数，
        // 所以 sand 即为所有出现了一次的数，
        // drawn 记录所有已经填上的数，
        // sand & ~drawn 即在 sand 中将所有已填的数去掉，即只出现过一次且未填的数
        for (int j = sand & ~drawn; j; j &= j - 1)
        {
            unsigned short t = j & -j;
            for (int k = 0; k < N; k ++ )
                if (state[i][k] & t)
                {
                    draw(i, k, log_2[t]);
                    cnt -- ;
                }
        }
    }

    // 剪枝 4: 对于每列，同 剪枝3
    // 按列枚举，所有上面的 state[i][j] 改为 state[j][i] 即可
    for (int i = 0; i < N; i ++ )
    {
        unsigned short drawn = 0, sor = 0, sand = M - 1;
        for (int j = 0; j < N; j ++ )
        {
            sand &= ~(sor & state[j][i]);
            sor |= state[j][i];
            if (str[j][i] != 45) drawn |= state[j][i];
        }
        if (sor != M - 1) return remove(kcnt);
        for (int j = sand & ~drawn; j; j &= j - 1)
        {
            unsigned short t = j & -j;
            for (int k = 0; k < N; k ++ )
                if (state[k][i] & t)
                {
                    draw(k, i, log_2[t]);
                    cnt -- ;
                }
        }
    }

    // 剪枝 5: 对于每个 4 * 4 方格，同 剪枝3
    // 按 4 * 4 方格枚举，要做下坐标变换，其余操作同上
    for (int i = 0; i < N; i ++ )
    {
        // (i / 4 * 4, i % 4 * 4) 即当前 4 * 4 方格的左上角坐标
        int x = i / 4 * 4, y = i % 4 * 4;
        unsigned short drawn = 0, sor = 0, sand = M - 1;
        for (int j = 0; j < N; j ++ )         // 枚举 4 * 4 方格中的每个位置
        {
            int a = x + j / 4, b = y + j % 4; // 取出该位置上
            sand &= ~(sor & state[a][b]);
            sor |= state[a][b];
            if (str[a][b] != 45) drawn |= state[a][b];
        }
        if (sor != M - 1) return remove(kcnt);
        for (int j = sand & ~drawn; j; j &= j - 1)
        {
            unsigned short t = j & -j;
            for (int k = 0; k < N; k ++ )     // 同上
            {
                int a = x + k / 4, b = y + k % 4;
                if (state[a][b] & t)
                {
                    draw(a, b, log_2[t]);
                    cnt -- ;
                }
            }
        }
    }

    // 如果填完后 cnt 为 0，说明填完了，返回 true
    if (!cnt) return true;

    // 找到整个数独中能填的数最少的位置
    // 这里可以再做一下 剪枝1 和 剪枝2
    int x, y, mins = 17;
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            if (str[i][j] < 65)
                if (!state[i][j]) return remove(kcnt);
                else if (ones[state[i][j]] == 1)
                {
                    draw(i, j, log_2[state[i][j]]);
                    cnt -- ;
                }
                else if (ones[state[i][j]] < mins)
                {
                    mins = ones[state[i][j]];
                    x = i, y = j;
                }

    // 同上，如果 cnt 为 0，返回 true 
    if (!cnt) return true;

    // 先将 state 备份到 bstate2[kcnt] 中
    memcpy(bstate2[kcnt], state, sizeof state);

    // 枚举 (x, y) 上所有能填的数
    for (int i = state[x][y]; i; i &= i - 1)
    {
        draw(x, y, log_2[i & -i]);     // 将该数填上
        if (dfs(cnt - 1)) return true; // 如果 dfs(cnt - 1) 成功了，那么直接返回 true
        memcpy(state, bstate2[kcnt], sizeof state); // 不成功，将 bstate2[kcnt] 复制回来，枚举下一个能填的数
    }
    return remove(kcnt); // 都不行，remove 并返回 false
}

int main()
{
    // 初始化 ones 和 log_2
    for (int i = 1; i < M; i ++ )
        for (int j = i; j; j &= j - 1)
            ones[i] ++ ;
    for (int i = 0; i < N; i ++ )
        log_2[1 << i] = i;

    while (~scanf("%s", *str)) // 如果 scanf 不返回 -1，那么继续执行
    {
        // 先将剩下从 1 到 N - 1 行的数独读完
        for (int i = 1; i < N; i ++ )
            scanf("%s", str[i]);

        // 将 state 中的所有元素 memset 为 -1
        // 由于 -1 的二进制表示中全是 1，这样也就将所有元素的所有位都制为了 1
        // 由于用的是 unsigned short，范围正好是 0 到 65535，在调用 ones[state[i][j]] 和 log[state[i][j]] 时，可避免溢出
        memset(state, -1, sizeof state);

        // 初始化 state 和 cnt
        int cnt = 0;
        for (int i = 0; i < N; i ++ )
            for (int j = 0; j < N; j ++ )
                if (str[i][j] == 45) cnt ++ ;    // 如果该位置元素是 '-'，那么 cnt ++ 
                else draw(i, j, str[i][j] - 65); // 否则在该位填上 str[i][j] - 'A'

        // 爆搜填 cnt 个数
        dfs(cnt);

        // 输出填上的结果
        for (int i = 0; i < N; i ++ ) puts(str[i]);
        putchar(getchar());
    }
    return 0;
}