蓝桥杯 九宫幻方

 

 

 

注意：第一次写dfs内用了二重循环，外层为位置，内层为未使用过的数字，存在先填充了后面又返回填充前面的情况，导致许多重复，按照样例给出的得出5!=120的结果......还是太菜了

后来参考了此博客：https://blog.****.net/h_hui_hui/article/details/79499183?utm_source=blogxgwz7

应该是按位置dfs，已经存在数据的位置跳过，直接下一个位置。此篇博客仅供记录错误

#include<bits/stdc++.h>
using namespace std;

int a[10];
int out[10];
bool vis[10];
int ans;

bool check()
{
    int sum = a[1] + a[2] + a[3];
    for(int i = 4; i <= 7; i += 3)
    {
        if(a[i] + a[i + 1] + a[i + 2] != sum)
            return false;
    }

    for(int i = 1; i <= 3;  i++)
    {
        if(a[i] + a[i + 3] + a[i + 6] != sum)
            return false;
    }

    if((a[1] + a[5] + a[9] != sum )|| (a[3] + a[5] + a[7] != sum) )
        return false;

    return true;
}

void dfs(int pos)
{
    if(pos == 10)
    {
        if(check())
        {
            ans++;
            if(ans == 1)
                memcpy(out, a, sizeof(a));
            return;
        }
        return;
    }

    if(a[pos])
    {
        dfs(pos + 1);
        return;
    }

    for(int i = 1; i <= 9; i++)
    {
        if(!vis[i])
        {
            a[pos] = i;
            vis[i] = 1;
            pos++;
            dfs(pos);
            vis[i] = 0;
            pos--;
            a[pos] = 0;
        }
    }
}

int main()
{
    for(int i = 1; i <= 9; i++)
    {
        scanf("%d", &a[i]);
        if(a[i])
        {
            vis[a[i]] = 1;
        }
    }
    ans = 0;
    dfs(1);
    if(ans == 1)
    {
        for(int i = 1; i <= 9; i++)
        {
            if(i % 3 == 0)
                cout << out[i] << endl;
            else
                cout << out[i] << " ";
        }
    }
    else
        cout << "Too Many" << endl;

    return 0;
}