2

私はこれをしたいと思います: 私は行列 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

この行列から魔方陣を作成できます。これを決定するアルゴリズムはありますか？何かお勧めできますか？ありがとう！

4

2 に答える 2

1

それが最も効率的なアプローチであるかどうかはわかりませんが、魔法の定数を決定することができます。

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

魔法の定数を取得したら、数独パズルのように操作できます。このパズルでは、塗りつぶされていない各セルで機能する可能性のある値を決定し、可能な値が最も少ないセルから始めて、それぞれを試します。セルに数値を入力すると、入力されていない残りのセルの可能な値が更新されます。セルに可能な値がない場合に遭遇した場合は、バックトラックします。可能性がなくなった場合、答えは「いいえ」です。埋められていないセルが足りなくなった場合、答えは「はい」です。

于 2012-12-15T16:01:40.250 に答える
1

奇数の行と列でのみ機能するアルゴリズムがあります。

  1. 1 行目の真ん中に 1 を入れる
  2. 1 セル上に移動し、1 セル左に移動します (循環行列を考慮する必要があります)。
  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;
}
于 2013-03-31T20:53:10.663 に答える