数独

纯暴力 0 分

// 最暴力枚举的代码
#include <bits/stdc++.h>
using namespace std;
int a[10][10];
int idx[10][10] = {
    {},
    {0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
    {0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
    {0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
    {0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
    {0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
    {0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
    {0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
    {0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
    {0, 7, 7, 7, 8, 8, 8, 9, 9, 9}};
void dfs(int nowX, int nowY)
{
    // 九行都填完了就检查
    if (nowX > 9)
    {
        // 位运算检查
        for (int i = 1; i <= 9; i++)
        {
            // 第 i 行
            int sta = 0;
            for (int j = 1; j <= 9; j++)
                sta = sta | (1 << (a[i][j] - 1));
            if (sta != ((1 << 9) - 1))
                return;
            // 第 i 列
            sta = 0;
            for (int j = 1; j <= 9; j++)
                sta = sta | (1 << (a[j][i] - 1));
            if (sta != ((1 << 9) - 1))
                return;
        }
        // 检查九宫格
        int sta[10];
        for (int i = 1; i <= 9; i++)
            sta[i] = 0;
        for (int i = 1; i <= 9; i++)
            for (int j = 1; j <= 9; j++)
            {
                int nowIdx = idx[i][j];
                sta[nowIdx] = sta[nowIdx] | (1 << (a[i][j] - 1));
            }
        for (int i = 1; i <= 9; i++)
            if (sta[i] != ((1 << 9) - 1))
                return;
        for (int i = 1; i <= 9; i++)
        {
            for (int j = 1; j <= 9; j++)
                cout << a[i][j] << " ";
            cout << "\n";
        }
        exit(0);
    }
    // 算出来下一个位置的行列编号
    int nxtX, nxtY;
    nxtX = nowX;
    nxtY = nowY + 1;
    if (nxtY > 9)
        nxtX++, nxtY = 1;
    // 如果已经填了就不管了
    if (a[nowX][nowY] != 0)
    {
        dfs(nxtX, nxtY);
        return;
    }
    // 考虑 1~9 的所有可能性
    for (int i = 1; i <= 9; i++)
    {
        a[nowX][nowY] = i;
        dfs(nxtX, nxtY);
        a[nowX][nowY] = 0;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    for (int i = 1; i <= 9; i++)
        for (int j = 1; j <= 9; j++)
            cin >> a[i][j];
    dfs(1, 1); // 从 (1,1) 的位置开始搜索
    return 0;
}

满分

// 最暴力枚举的代码
#include <bits/stdc++.h>
using namespace std;
int a[10][10];
int idx[10][10] = {
    {},
    {0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
    {0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
    {0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
    {0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
    {0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
    {0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
    {0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
    {0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
    {0, 7, 7, 7, 8, 8, 8, 9, 9, 9}};
bool flag1[10][10]; // 第 i 行有没有数字 j
bool flag2[10][10]; // 第 i 列有没有数字 j
bool flag3[10][10]; // 第 i 个九宫格有没有数字 j
void dfs(int nowX, int nowY)
{
    // 九行都填完了就检查
    if (nowX > 9)
    {
        for (int i = 1; i <= 9; i++)
        {
            for (int j = 1; j <= 9; j++)
                cout << a[i][j] << " ";
            cout << "\n";
        }
        exit(0);
    }
    // 算出来下一个位置的行列编号
    int nxtX, nxtY;
    nxtX = nowX;
    nxtY = nowY + 1;
    if (nxtY > 9)
        nxtX++, nxtY = 1;
    // 如果已经填了就不管了
    if (a[nowX][nowY] != 0)
    {
        dfs(nxtX, nxtY);
        return;
    }
    // 考虑 1~9 的所有可能性
    for (int i = 1; i <= 9; i++)
    {
        // 检查 a[nowX][nowY] 能不能填 i
        if (flag1[nowX][i] ||
            flag2[nowY][i] ||
            flag3[idx[nowX][nowY]][i])
            continue;
        // 填 i
        a[nowX][nowY] = i;
        flag1[nowX][i] = true;
        flag2[nowY][i] = true;
        flag3[idx[nowX][nowY]][i] = true;
        // 做下一步
        dfs(nxtX, nxtY);
        // 撤销影响
        a[nowX][nowY] = 0;
        flag1[nowX][i] = false;
        flag2[nowY][i] = false;
        flag3[idx[nowX][nowY]][i] = false;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    for (int i = 1; i <= 9; i++)
        for (int j = 1; j <= 9; j++)
        {
            cin >> a[i][j];
            if (a[i][j] != 0)
            {
                flag1[i][a[i][j]] = true;
                flag2[j][a[i][j]] = true;
                flag3[idx[i][j]][a[i][j]] = true;
            }
        }
    dfs(1, 1); // 从 (1,1) 的位置开始搜索
    return 0;
}