P1274 魔术数字游戏

题目描述

填数字方格的游戏有很多种变化，如下图所示的4×4方格中，我们要选择从数字1到16来填满这十六个格子(Aij，其中i＝1..4，j＝1..4)。为了让游戏更有挑战性，我们要求下列六项中的每一项所指定的四个格子，其数字累加的和必须为34：

四个角落上的数字，即A11+A14+A41+A44＝34。

每个角落上的2×2方格中的数字，例如左上角：A11+A12+A21+A22＝34。

最中间的2×2方格中的数字，即A22+A23+A32+A33=34。

每条水平线上四个格子中的数字，即Ai1+Ai2+Ai3+Ai4＝34，其中i＝1..4。

每条垂直线上四个格子中的数字，即A1j+A2j+A3j+A4j＝34，其中j＝1..4。

两条对角线上四个格子中的数字，例如左上角到右下角：A11+A22+A33+A44＝34。

右上角到左下角：A14+A23+A32+A41＝34

输入格式

输入文件会指定把数字1先固定在某一格内。输入的文件只有一行包含两个正数据I和J，表示第1行和第J列的格子放数字1。剩下的十五个格子，请按照前述六项条件用数字2到16来填满。

输出格式

把全部的正确解答用每4行一组写到输出文件，每行四个数，相邻两数之间用一个空格隔开。两组答案之间，要以一个空白行相间，并且依序排好。排序的方式，是先从第一行的数字开始比较，每一行数字，由最左边的数字开始比，数字较小的解答必须先输出到文件中。

输入输出样例

输入 #1

1 1

输出 #1

1 4 13 16
14 15 2 3
8 5 12 9
11 10 7 6

1 4 13 16
14 15 2 3
12 9 8 5
7 6 11 10


首先为了方便计算我们显然要把一个格子的两个坐标压成一个整数。
具体计算方法将

然后，打一发表。。。。。。

好的，结了。

#include <cstdio>

int b[15][4] = {
    {0, 1, 2, 3},
    {4, 5, 6, 7},
    {8, 9, 10, 11},
    {12, 13, 14, 15},
    {0, 4, 8, 12},
    {1, 5, 9, 13},
    {2, 6, 10, 14},
    {3, 7, 11, 15},
    {0, 5, 10, 15},
    {3, 6, 9, 12},
    {5, 6, 9, 10},
    {0, 1, 4, 5},
    {2, 3, 6, 7},
    {8, 9, 12, 13},
    {10, 11, 14, 15}
};

int a[16];
int vis[17];
int xz[16][10];
int cnt[16];
int pos1;

void DFS(int num){
    if (num == 16){
        if (a[pos1] != 1) return ;
        for (int i = 0; i < 4; ++i) printf("%d%c", a[i], ((i == 3) ? '
' : ' '));
        for (int i = 4; i < 8; ++i) printf("%d%c", a[i], ((i == 7) ? '
' : ' '));
        for (int i = 8; i < 12; ++i) printf("%d%c", a[i], ((i == 11) ? '
' : ' '));
        for (int i = 12; i < 16; ++i) printf("%d%c", a[i], ((i == 15) ? '
' : ' '));
        puts("");
        return ;
    }
    a[num] = 0;
    for (int i = 0; i < cnt[num]; ++i){
        if (!a[num]){
            a[num] = 34 - a[b[xz[num][i]][0]] - a[b[xz[num][i]][1]] - a[b[xz[num][i]][2]];
            if (a[num] > 16 || a[num] < 1) return ;
            if (a[num] == 1 && num != pos1) return ;
            if (vis[a[num]]) return ;
        }
        else{
            if (a[num] != 34 - a[b[xz[num][i]][0]] - a[b[xz[num][i]][1]] - a[b[xz[num][i]][2]]) return ;
        }
    }
    if (!a[num]){
        if (num == pos1){
            if (vis[1]) return ;
            vis[1] = 1; a[num] = 1;
            DFS(num + 1);
            vis[1] = 0;
        }
        else{
            for (int i = 2; i <= 16; ++i){
                if(vis[i]) continue;
                vis[i] = 1; a[num] = i;
                DFS(num + 1);
                vis[i] = 0;
            }
        }
    }
    else{
        if (num == pos1 && a[num] != 1) return ;
        vis[a[num]] = 1;
        DFS(num + 1);
        vis[a[num]] = 0;
    }
}

int main(){
    int x, y; scanf("%d %d", &x, &y); pos1 = (x - 1) * 4 + y - 1;
    for (int i = 0; i < 15; ++i){
        xz[b[i][3]][cnt[b[i][3]]++] = i;
    }
    DFS(0);
    return 0;
}