我想这样做:我有一个矩阵 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
我们可以从这个矩阵创建一个幻方。有什么算法可以决定这个吗?你能给我推荐点什么吗?谢谢你!
我想这样做:我有一个矩阵 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
我们可以从这个矩阵创建一个幻方。有什么算法可以决定这个吗?你能给我推荐点什么吗?谢谢你!
我不确定这是否是最有效的方法,但您可以确定魔法常数:如
magic_constant = n*(n^2+1)/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;
}