How to create a magic square which already has some numbers filled?

Question

I would like to do this: I've got a matrix N x N. It can contain number from 1 to n^2. This matrix has a few cells filled with positive numbers. I have to decide, that this already filled matrix can be a magic matrix (magic square). For example:

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 

We can create from this matrix a magic square. Is there any algorithm to decide this? Could you recommend me something? Thank You!

Answer 1

I'm not sure if it is the most efficient approach, but you can determine the magic constant: as

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

Once you have the magic constant, you can work it similar to a Sudoku puzzle, where you determine which possible values could work for each unfilled cell, and then try each one starting with the cell that has the fewest possible values. When you fill a cell with a number, you update the possible values for the rest of the unfilled cells. If you run into a case where a cell has no possible values, then you backtrack. If you run out of possibilities, then the answer is "no". If you run out of unfilled cells, then the answer is "yes".

Answer 2

There is an algorithm than just works on odd number of row and columns:

1. Put 1 in the middle of first row
2. Go one cell up then one cell left (You should consider a cyclic matrix)
3. Put increasing numbers in this cell
4. Go to step 2 as long as reaching n^2

Here is a C++ code for this:

#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;
}