hiho一下 第135周 九宮 （枚舉幻方）

描述

小Hi最近在教鄰居家的小朋友國小奧數，而最近正好講述到了三階幻方這個部分，三階幻方指的是将1~9不重複的填入一個3*3的矩陣當中，使得每一行、每一列和每一條對角線的和都是相同的。

三階幻方又被稱作九宮格，在國小奧數裡有一句非常有名的口訣：“二四為肩，六八為足，左三右七，戴九履一，五居其中”，通過這樣的一句口訣就能夠非常完美的構造出一個九宮格來。

有意思的是，所有的三階幻方，都可以通過這樣一個九宮格進行若幹鏡像和旋轉操作之後得到。現在小Hi準備将一個三階幻方（不一定是上圖中的那個）中的一些數組抹掉，交給鄰居家的小朋友來進行還原，并且希望她能夠判斷出究竟是不是隻有一組解。

而你呢，也被小Hi傳遞了同樣的任務，但是不同的是，你需要寫一個程式~

輸入

輸入僅包含單組測試資料。

每組測試資料為一個3*3的矩陣，其中為0的部分表示被小Hi抹去的部分。

對于100%的資料，滿足給出的矩陣至少能還原出一組可行的三階幻方。

輸出

如果僅能還原出一組可行的三階幻方，則将其輸出，否則輸出“Too Many”（不包含引号）。

樣例輸入

0 7 2
0 5 0
0 3 0      

樣例輸出

6 7 2
1 5 9
8 3 4      

題意

給出一個不完整的三階幻方，問能否将它還原，如果可以還原成多種情況，輸出 ​

​Too Many​

​ ，否則輸出唯一還原後的幻方。

思路

怎麼說呢！這道題，想了想這樣的三階幻方，中心的數字一定是5，并且四個角一定是偶數，不論怎麼旋轉變化，總共也不超過10種情況。

于是，很輕松的寫出了八種所有情況。

AC 代碼

#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<string.h>
using namespace std;

int a[8][3][3]=     //三階幻方旋轉總共隻有八種情況，可以很快寫出來的
{
    {
        {8,1,6},
        {3,5,7},
        {4,9,2}
    },
    {
        {6,1,8},
        {7,5,3},
        {2,9,4}
    },
    {
        {4,9,2},
        {3,5,7},
        {8,1,6}
    },
    {
        {2,9,4},
        {7,5,3},
        {6,1,8}
    },
    {
        {6,7,2},
        {1,5,9},
        {8,3,4}
    },
    {
        {8,3,4},
        {1,5,9},
        {6,7,2}
    },
    {
        {2,7,6},
        {9,5,1},
        {4,3,8}
    },
    {
        {4,3,8},
        {9,5,1},
        {2,7,6}
    }
};

bool judge(int a[3][3],int s[3][3])
{
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
            if(s[i][j]!=0&&a[i][j]!=s[i][j])
                return false;
    return true;
}

int main()
{
    int s[3][3],count=0,sk;
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
            scanf("%d",&s[i][j]);
    for(int i=0; i<8; i++)
        if(judge(a[i],s))
        {
            sk=i;
            count++;
        }
    if(count==1)
        for(int i=0; i<3; i++)
            for(int j=0; j<3; j++)
                printf(j!=2?"%d ":"%d\n",a[sk][i][j]);
    else printf("Too Many\n");
    return 0;
}