西山居 9.11 笔试题

描述

给出 3 * 3 方阵，你需要在其中填入数字 1 ~ 9，使其每一行和每一列的元素之和为15
其中一些位置上的数字已经给出，空出的位置用 0 表示
若存在解，则输出任意一个结果方阵即可
否则输出 "Not Found"

分析

这是一道 深搜 & 回溯剪枝 的问题
考虑遍历整个方阵
若当前位置已有数字，直接向下搜索即可
若为空位，则遍历所有剩余的数字，尝试填入其中，向下搜索

确定了搜索方式之后就是确定剪枝策略
考虑每一行和每一列的最后一个位置，当我们搜索到这些位置的时候，需要填入的数字是确定的
若该位置已有数字已有数字且不满足和为15的条件
或者需要填入的数字已经被使用过，那么就可以剪枝了

当搜索到最后一个位置时，用异或运算求出唯一没有被使用的数字
同时考察行和列是否满足条件，如果满足，那么就说明找到了一个解，就可以直接返回了

代码

#include <cstdio>

int g[9], vis, flag;

int getX(int k) {
    if (k % 3 == 2) return 15 - g[k - 2] - g[k - 1];
    else if (k / 3 == 2) return 15 - g[k - 6] - g[k - 3];
    return 0;
}

void output() {
    printf("%d %d %d\n", g[0], g[1], g[2]);
    printf("%d %d %d\n", g[3], g[4], g[5]);
    printf("%d %d %d\n", g[6], g[7], g[8]);
}

void dfs(int k) {
    if (flag) return;
    if (k == 8) {
        int x = g[8] ? g[8] : ((1 << 9) - 1) ^ vis;

        if (g[2] + g[5] + x == 15 && g[6] + g[7] + x == 15) {
            g[8] = x;
            output();
            flag = 1;
            return;
        }
    }

    int x = getX(k);
    if (x == 0) {
        if (g[k]) dfs(k + 1);
        else {
            for (int i = 1; i <= 9; ++i) {
                if (vis & (1 << (i - 1))) continue;
                vis ^= (1 << (i - 1));
                g[k] = i;
                dfs(k + 1);
                g[k] = 0;
                vis ^= (1 << (i - 1));
            }
        }
    }
    else {
        if (g[k] == x) dfs(k + 1);
        else if (g[k] == 0 && !(vis & (1 << (x - 1)))) {
            vis ^= (1 << (x - 1));
            g[k] = x;
            dfs(k + 1);
            g[k] = 0;
            vis ^= (1 << (x - 1));
        }
    }
}

int main() {
    for (int &x: g) {
        scanf("%d", &x);
        if (x) vis |= (1 << (x - 1));
    }

    dfs(0);
    return 0;
}