九宫幻方-第八届蓝桥省赛-C组(DFS和对比所有幻方种类)

目录

​

解法一：DFS（深搜）：

解法一代码：

解法二：直接拿所有可能的幻方，与输入的不为0的数进行比较

解法二代码：

小明最近在教邻居家的小朋友小学奥数，而最近正好讲述到了三阶幻方这个部分，三阶幻方指的是将 1∼9 不重复的填入一个 3×3 的矩阵当中，使得每一行、每一列和每一条对角线的和都是相同的。

三阶幻方又被称作九宫格，在小学奥数里有一句非常有名的口诀：“二四为肩，六八为足，左三右七，戴九履一，五居其中”，通过这样的一句口诀就能够非常完美的构造出一个九宫格来。

4 9 2

3 5 7

8 1 6

有意思的是，所有的三阶幻方，都可以通过这样一个九宫格进行若干镜像和旋转操作之后得到。

现在小明准备将一个三阶幻方（不一定是上图中的那个）中的一些数抹掉，交给邻居家的小朋友来进行还原，并且希望她能够判断出究竟是不是只有一个解。

而你呢，也被小明交付了同样的任务，但是不同的是，你需要写一个程序~

输入格式:

一个 3×3 的矩阵，其中为 0 的部分表示被小明抹去的部分。数据保证给出的矩阵至少能还原出一组可行的三阶幻方。

输出格式:

如果仅能还原出一组可行的三阶幻方，则将其输出，否则输出 "Too Many"。

输入样例

0 7 2
0 5 0
0 3 0

输出样例：

6 7 2
1 5 9
8 3 4

解法一：DFS（深搜）：

思路：所有行，列，对角线的和相等，其实就是行，列，对角线和均为(1~9)/3=15

用dfs填充所有为0 的数，并判断是否符合要求，如果符合要求count+1，最后判断count的值即可，注意：dfs填充完需要进行减枝，进行遍历下一种情况。

解法一代码：

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int count1=0;
int a[3][3];
int res[3][3];
int b[9];
void dfs(int x,int y)
{
    if(x==1){if(a[0][0]+a[0][1]+a[0][2]!=15){return;}}
    if(x==2){if(a[1][0]+a[1][1]+a[1][2]!=15){return;}}
    if(x==3){
        if(a[1][0]+a[1][1]+a[1][2]==15&&a[0][0]+a[0][1]+a[0][2]==15&&a[2][0]+a[2][1]+a[2][2]==15&&a[0][0]+a[1][1]+a[2][2]==15&&a[0][2]+a[1][1]+a[2][0]==15&& a[1][0]+a[1][1]+a[1][2]==15&&a[0][0]+a[2][0]+a[1][0]==15&&a[0][2]+a[1][2]+a[2][2]==15&&a[0][1]+a[1][1]+a[2][1]==15)
        {
            for(int i=0;i<3;i++){
                for(int j=0;j<3;j++)
                {
                    res[i][j]=a[i][j];
                }
            }
            count1++;
        }
    }
    if(a[x][y]==0)
    {
        for(int i=1;i<=9;i++)
        {
            if(b[i]==0)
            {
                a[x][y]=i;
                b[i]=1;
                dfs(x+(y+1)/3,(y+1)%3);
                b[i]=0;
                a[x][y]=0;
            }
        }
    }
    else {
        dfs(x+(y+1)/3,(y+1)%3);
    }
}
int main()
{
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            cin>>a[i][j];
            b[a[i][j]]=1;
        }
    }
    dfs(0,0);
    if(count1==1)
    {
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
            {
                j!=2?cout<<res[i][j]<<" ":cout<<res[i][j];
            }
            cout<<"\n";
        }
    }
    else {
        cout<<"Too Many";
    }
    return 0;
}

解法二：直接拿所有可能的幻方，与输入的不为0的数进行比较

 思路：直接找出幻方的所有可能，旋转和镜像产生的可能，总共8总，顺时针旋转4次，镜像之后顺时针旋转4次

 {4, 9, 2, 3, 5, 7, 8, 1, 6},
 {8, 3, 4, 1, 5, 9, 6, 7, 2},
 {6, 1, 8, 7, 5, 3, 2, 9, 4},
 {2, 7, 6, 9, 5, 1, 4, 3, 8},
 {2, 9, 4, 7, 5, 3, 6, 1, 8},
 {6, 7, 2, 1, 5, 9, 8, 3, 4},
 {8, 1, 6, 3, 5, 7, 4, 9, 2},
 {4, 3, 8, 9, 5, 1, 2, 7, 6},

再将输入的不为0的数与之对比。

解法二代码：

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int ans[8][9] ={
            {4, 9, 2, 3, 5, 7, 8, 1, 6},
            {8, 3, 4, 1, 5, 9, 6, 7, 2},
            {6, 1, 8, 7, 5, 3, 2, 9, 4},
            {2, 7, 6, 9, 5, 1, 4, 3, 8},
            {2, 9, 4, 7, 5, 3, 6, 1, 8},
            {6, 7, 2, 1, 5, 9, 8, 3, 4},
            {8, 1, 6, 3, 5, 7, 4, 9, 2},
            {4, 3, 8, 9, 5, 1, 2, 7, 6},
            };
int main(){
    int a[10];
    int count=0;
    int flag,j;
    for(int i=0;i<9;i++)cin>>a[i];
    for(int i=0;i<8;i++)
    {
        for(j=0;j<9;j++)
        {
            if(a[j]!=0&&a[j]!=ans[i][j])
            {
                break;
            }
        }
        if(j==9)
        {
            flag=i;
            count++;
        }
    }
    if(count==1)
    {
        for(int i=0;i<9;i++)
        {
            if(i%3==2)cout<<ans[flag][i]<<endl;
            else cout<<ans[flag][i]<<" ";
        }
    }
    else cout<<"Too Many"<<endl;
    return 0;
}