Jiugong magic square - the 8th Lanqiao provincial competition - group C (DFS and comparison of all magic square types)

Catalog

​

Solution 1 ：DFS（ Deep search ）：

Solution one code ：

Solution 2 ： Just take all the possible magic squares , Is different from the input 0 Compare the number of

Solution II code ：

Xiao Ming is teaching math Olympiad in primary school to the children living in the neighborhood recently , Recently, I just talked about the third order magic square , The magic square of the third order refers to will 1∼9 Fill in one without repetition 3×3 In the matrix of , Make every line 、 The sum of every column and every diagonal is the same .

The third order magic square is also called Jiugongge , There is a famous pithy formula in primary school Olympiad Mathematics ：“ Two four for the shoulder , Sixty eight is enough , Three on the left and seven on the right , Wearing nine shoes one , Five of them ”, Through such a pithy formula, you can construct a nine palace lattice perfectly .

4 9 2

3 5 7

8 1 6

What's interesting is that , All the magic squares of the third order , Can be through such a nine grid after a number of mirror and rotation operations .

Now Xiao Ming is going to put a third-order magic square （ Not necessarily the one in the picture above ） Erase some numbers in , Give it to your neighbor's children to restore it , And I hope she can judge whether there is only one solution .

And you , Xiao Ming has also assigned the same task , But here's the difference , You need to write a program ~

Input format :

One 3×3 Matrix , Among them is 0 The part of represents the part erased by Xiao Ming . The data guarantees that the given matrix can restore at least a set of feasible third-order magic squares .

Output format :

If only a set of feasible third-order magic squares can be restored , Then output it , Otherwise output "Too Many".

sample input

0 7 2
0 5 0
0 3 0

sample output ：

6 7 2
1 5 9
8 3 4

Solution 1 ：DFS（ Deep search ）：

Ideas ： All right , Column , The sum of diagonals is equal , Actually, it's OK , Column , Diagonals and are (1~9)/3=15

use dfs Fill all as 0 Number of numbers , And judge whether it meets the requirements , If the requirements are met count+1, Finally, judge count The value of the can , Be careful ：dfs Pruning is required after filling , Go through the next case .

Solution one code ：

#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;
}

Solution 2 ： Just take all the possible magic squares , Is different from the input 0 Compare the number of

  Ideas ： Find out all the possibilities of magic square directly , The possibility of rotation and mirroring , in total 8 total , Clockwise rotation 4 Time , Rotate clockwise after mirroring 4 Time

 {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},

Then the input is not 0 Compare the number of .

Solution II code ：

#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;
}