Как создать волшебный квадрат, в котором уже заполнено несколько чисел?

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. Переходите к шагу 2 до тех пор, пока не достигнете n^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;
}