【2024信友队 - 提高模考】Day 4 提高2 T2：数独

题面

题目描述

请你将一个 $16×16$ 的数独填写完整，使得每行、每列、每个 $4×4$ 十六宫格内字母 $A$ ~ $P$ 均恰好出现一次。

保证每个输入只有唯一解决方案。

输入格式

输入包含多组测试用例。

每组测试用例包括 $16$ 行，每行一组字符串，共 $16$ 个字符串。

第 $i$ 个字符串表示数独的第 $i$ 行。

字符串包含字符可能为字母 $A$ ~ $P$ 或 $−$（表示等待填充）。

测试用例之间用单个空行分隔，输入至文件结尾处终止。

输出格式

对于每个测试用例，均要求保持与输入相同的格式，将填充完成后的数独输出。

每个测试用例输出结束后，输出一个空行。

思路

不多说了，纯模拟

代码

一次纪念我有史以来写过最长的模拟题代码（230行）

#include<bits/stdc++.h>
using namespace std;

char str[20][20];                               // 数独数组
char str2[400][20][20];                         // 回溯备份用
int ones[1 << 17], mp[1 << 17];                 // 二进制中 1 的个数，某二进制中最后一个 1 的位置
int state[20][20];                              // 每个点可以放什么
int state2[400][20][20], state3[400][20][20];   // 回溯备份用

inline int lowbit(int x) {// lowbit 没什么好说了
    return x & -x;
}

void Input() {
    for (int i = 1; i < 16; i ++ ) {            // 读入
        scanf("%s", str[i]);
    }
    for (int i = 0; i < 16; i ++ ) {            // 一开始每个点啥都可以放
        for (int j = 0; j < 16; j ++ ) {
            state[i][j] = (1 << 16) - 1;
        }
    }
}

void draw(int x, int y, int c) {                // 这个点要放字符 c
    str[x][y] = c + 'A';                        // 修改数独
    for (int i = 0; i < 16; i ++) {             // 修改每个点可以放的东西 因为每行每列不能重复
        state[x][i] &= ~(1 << c);
        state[i][y] &= ~(1 << c);
    }
    int sx = x / 4 * 4, sy = y / 4 * 4;         // 每一个宫也不能重复
    for (int i = 0; i < 4; i ++) {      
        for (int j = 0; j < 4; j ++) {
            state[sx + i][sy + j] &= ~(1 << c);
        }
    }
    state[x][y] = 1 << c;                       // 这个点已经确定放 c
}

bool Dfs(int cnt) {                             // 能不能放第倒数 cnt 个字母
    if (!cnt) return true;                      // 安全放完
    int kcnt = cnt;                             // 备份
    memcpy(str2[kcnt], str, sizeof str);
    memcpy(state2[kcnt], state, sizeof state);
    for (int i = 0; i < 16; i ++) {             // 枚举空白点
        for (int j = 0; j < 16; j ++) {
            if (str[i][j] == '-') {
                int s = state[i][j];
                if (!s) {                       // 什么都放不了，无解
                    memcpy(str, str2[kcnt], sizeof str);
                    memcpy(state, state2[kcnt], sizeof state);
                    return false;
                }
                if (ones[s] == 1) {             // 只能放一个，直接放
                    draw(i, j, mp[s]);
                    cnt --;
                }
            }
        }
    }
    for (int i = 0; i < 16; i ++) {
        int sor = 0, sand = (1 << 16) - 1;
        int drawn = 0;
        for (int j = 0; j < 16; j ++) {
            int s = state[i][j];
            sand &= ~(s & sor);
            sor |= s;
            if (str[i][j] != '-') {
                drawn |= s;
            }
        }
        if (sor != (1 << 16) - 1) {
            memcpy(str, str2[kcnt], sizeof str);
            memcpy(state, state2[kcnt], sizeof state);
            return false;
        }
        
        for (int j = sand; j; j -= lowbit(j)) {
            int t = lowbit(j);
            if (!(drawn & t)) {
                for (int k = 0; k < 16; k ++) {
                    if (state[i][k] & t) {
                        draw(i, k, mp[t]);
                        cnt --;
                        break;
                    }
                }
            }
        }
    }
    for (int i = 0; i < 16; i ++) {
        int sor = 0, sand = (1 << 16) - 1;
        int drawn = 0;
        for (int j = 0; j < 16; j ++) {
            int s = state[j][i];
            sand &= ~(s & sor);
            sor |= s;
            if (str[j][i] != '-') {
                drawn |= s;
            }
        }
        if (sor != (1 << 16) - 1) {
            memcpy(str, str2[kcnt], sizeof str);
            memcpy(state, state2[kcnt], sizeof state);
            return false;
        }
        for (int j = sand; j; j -= lowbit(j)) {
            int t = lowbit(j);
            if (!(drawn & t)) {
                for (int k = 0; k < 16; k ++) {
                    if (state[k][i] & t) {
                        draw(k, i, mp[t]);
                        cnt --;
                        break;
                    }
                }
            }
        }
    }
    for (int i = 0; i < 16; i ++) {
        int sor = 0, sand = (1 << 16) - 1;
        int drawn = 0;
        for (int j = 0; j < 16; j ++) {
            int sx = i / 4 * 4, sy = i % 4 * 4;
            int dx = j / 4, dy = j % 4;
            int s = state[sx + dx][sy + dy];
            sand &= ~(s & sor);
            sor |= s;
            if (str[sx + dx][sy + dy] != '-') {
                drawn |= s;
            }
        }
        
        if (sor != (1 << 16) - 1) {
            memcpy(str, str2[kcnt], sizeof str);
            memcpy(state, state2[kcnt], sizeof state);
            return false;
        }
        
        for (int j = sand; j; j -= lowbit(j)) {
            int t = lowbit(j);
            if (!(drawn & t)) {
                for (int k = 0; k < 16; k ++) {
                    int sx = i / 4 * 4, sy = i % 4 * 4;
                    int dx = k / 4, dy = k % 4;
                    if (state[sx + dx][sy + dy] & t) {
                        draw(sx + dx, sy + dy, mp[t]);
                        cnt --;
                        break;
                    }
                }
            }
        }
    }
    if (!cnt) return true;
    int x, y, s = 20;
    for (int i = 0; i < 16; i ++) {
        for (int j = 0; j < 16; j ++) {
            if (str[i][j] == '-' && ones[state[i][j]] < s) {
                s = ones[state[i][j]];
                x = i, y = j;
            }
        }
    }
    
    memcpy(state3[kcnt], state, sizeof state);
    for (int i = state[x][y]; i; i -= lowbit(i)) {
        memcpy(state, state3[kcnt], sizeof state);
        draw(x, y, mp[lowbit(i)]);
        if (Dfs(cnt - 1)) {
            return true;
        }
    }
    memcpy(state, state2[kcnt], sizeof state);
    memcpy(str, str2[kcnt], sizeof str);
    return false;
}

void Work() {
    int cnt = 0;
    for (int i = 0; i < 16; i ++ ) {
        for (int j = 0; j < 16; j ++ ) {
            if (str[i][j] != '-') {
                draw(i, j, str[i][j] - 'A');
            }
            else {
                cnt ++ ;
            }
        }
    }
    Dfs(cnt);
    for (int i = 0; i < 16; i ++ ) {
        cout << str[i] << endl;
    }
    cout << endl;
}

int main() {
    for (int i = 0; i < 16; i ++ ) {
        mp[1 << i] = i;
    }
    for (int i = 0; i < 1 << 16; i ++ ) {
        for (int j = i; j; j -= lowbit(j)) {
            ones[i] ++ ;
        }
    }
    while (~scanf("%s", *str)) {
        Input();
        Work();
    }
    return 0;
}