algorithm - 如何创建一个已经填充了一些数字的幻方？

Question

我想这样做：我有一个矩阵 N x N。它可以包含从 1 到 n^2 的数字。这个矩阵有几个用正数填充的单元格。我必须决定，这个已经填充的矩阵可以是一个魔法矩阵（魔方）。例如：

0 0 0 7 4

0 1 0 0 8

0 0 3 0 0

0 0 0 0 0

0 0 0 0 0 

我们可以从这个矩阵创建一个幻方。有什么算法可以决定这个吗？你能给我推荐点什么吗？谢谢你！

Answer 1

我不确定这是否是最有效的方法，但您可以确定魔法常数：如

magic_constant = n*(n^2+1)/2

一旦你有了魔法常数，你就可以像数独谜题一样工作，确定哪些可能的值适用于每个未填充的单元格，然后从具有最少可能值的单元格开始尝试每个值。当您用数字填充单元格时，您会更新其余未填充单元格的可能值。如果您遇到单元格没有可能值的情况，那么您将回溯。如果你用尽了可能性，那么答案是“不”。如果您用完了未填充的单元格，那么答案是“是”。

Answer 2

有一种算法不仅仅适用于奇数行和列：

1. 将 1 放在第一行的中间
2. 向上移动一个单元格，然后向左移动一个单元格（您应该考虑一个循环矩阵）
3. 在这个单元格中输入越来越多的数字
4. 只要达到 n^2 就转到第 2 步

这是一个 C++ 代码：

#include <iostream>
#include <iomanip>
#define For(i,n) for(int i=0; i<n; i++)
#define FOR(i,j,n) for(int i=0; i<n; i++) for(int j=0; j<n; j++)
using namespace std;

void print(int**, int);
void calc(int**, int);
void test(int**, int);

int main()
{
    int n;
    a:cout<<"Enter an odd number:";
    cin>>n;
    if (n % 2 == 0)
    {
        cout<<"You entered an even number!\n\n";
        goto a;
    }
    int** ary = new int*[n];
    For(i,n)
        ary[i] = new int[n];

    //Fill array entires with NULL
    FOR(i,j,n)
        ary[i][j] = NULL;   

    calc(ary,n);
    print(ary,n);
    test(ary,n);

    cin>>n;
}
void print(int** ary, int n)
{
    cout<<endl;
    For(i,n)
    {
        For(j,n)
        {
            if (ary[i][j] == NULL) {cout<<"N  "; continue;}
        cout<<setw(4)<<ary[i][j];
        }
        cout<<endl;
    }
}

void calc(int** ary, int n)
{
    int c=1, i=0, j=n/2;
    while(true)
    {
        if (ary[i][j] == NULL) ary[i][j] = c++;
        else
        {
            j++;
            i+=2;
            if (j == n) j = 0;
            if (i == n) i = 0;
            else if (i == n+1) i = 1;
            continue;
        }
        //cout<<"Filled ary["<<i<<"]["<<j<<"]\n";
        i--;
        j--;
        if (i < 0) i = n-1;
        if (j < 0) j = n-1;
        if (c> n*n) break;
    }
}

void test(int** ary, int n)
{
    cout<<"\nTesting Sums. . .";
    int rSum = 0, cSum = 0, mDiagSum = 0, sDiagSum = 0;
    For(i,n)
    {
        For(j,n)
        {
            rSum += ary[i][j];
            cSum += ary[j][i];
            if (i == j) mDiagSum +=ary[i][j];
            if (n - 1 == i + j) sDiagSum += ary[i][j];
        }
        cout<<"\nSum of row #"<<i+1<<"= "<<rSum
            <<"\nSum of Column #"<<i+1<<"= "<<cSum;
        rSum = 0;
        cSum = 0;
    }
    cout<<"\nSum of main diagonal= "<<mDiagSum
        <<"\nSum of sub diagonal= "<<sDiagSum<<endl;
}