How many semi magic squares are there?

Question

I want to write a program to work out how many semi-magic squares there are.

Here is the definition of semi-magic squares

If we define \$H_n(t)\$ is the number of semi magic squares which satisfy:

1. The square is \$n*n\$ dimension
2. The sum of each row elements and sum of each column elements equal to \$t\$

The first idea came to me is brute force searching. I know backtracing may be better, but I don't know how to write the program.

For example, when \$n = 3\$, \$t = 1\$.

The third constraint:

I need to clearly point out that all the matrix elements are non-negative integers. Apparently, we can get that elements \$\in[0,t]\$

According to this, we can get this table:

n\t      | 1|2|3|4|5|6|7|8
---------| -----
1        | 1|1|1|1|1|1|1|1
2        | 2|3|4|5|6|7|8|9
3        | 6|21|55|120|231|406|666|1035
4        | 24|282|2008|10147|40176|132724|381424|981541

When \$n = 3\$, it's something like this sequence.

#include<iostream>
using namespace std;
int square[3][3];

//check whether it is a semi-square
bool final_check(int n,int t)
{
    for(int i=0;i<n;i++)
    {
        int sum_col=0;
        int sum_row=0;
        for(int j=0;j<n;j++)
        {
            sum_row+=square[i][j];
            sum_col+=square[j][i];
        }
        if(sum_col!=t||sum_row!=t)
            return false;
    }
    return true;
}
void display(int n)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
            cout<<square[i][j]<<"\t";
        cout<<endl;
    }
    cout<<"************"<<endl;
}

//count \$H_3(1)\$
int main()
{
    int n=3,t=5;
    int total_num=0;
    for(int a=0;a<=t;a++)
    {
        square[0][0]=a;
        for(int b=0;b<=t;b++)
        {
            square[0][1]=b;
            for(int c=0;c<=t;c++)
            {
                square[0][2]=c;
                for(int d=0;d<=t;d++)
                {
                    square[1][0]=d;
                    for(int e=0;e<=t;e++)
                    {
                        square[1][1]=e;
                        for(int f=0;f<=t;f++)
                        {
                            square[1][2]=f;
                            for(int g=0;g<=t;g++)
                            {
                                square[2][0]=g;
                                for(int h=0;h<=t;h++)
                                {
                                    square[2][1]=h;
                                    for(int i=0;i<=t;i++)
                                    {
                                        square[2][2]=i;
                                        if(final_check(n,t))  //check
                                        {
                                            display(n);
                                            total_num++;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout<<"total number of semi magic square: "<<total_num<<endl;
    getchar();
    return 0;
}

I know that my code is very bad. Could anyone help me improve the code? There are so many for loops. If \$n = 5\$, I would have to write 25 for loops.

Does anyone have a better solution?

Answer 1

There could be smarter ways to write your code in such a way that it would scale better (for instance, if you were to consider squares of side 4 or 5, you'd have 16 or 25 nested loops and local variables to handle).

First thing first, let's try to see what can easily be improved in your code.

You are considering all matrices of the following form :

 a b c
 d e f
 g h i

by making the different values go from 0 to t (included) and then check that a+b+c == d+e+f == g+h+i == a+d+g == b+e+h == c+f+i. However, things could be done in a much faster way : once a and b are fixed, you know that c == t - (a+b). Similarly, you can define f as t - (d+e). Then you can go one step further as g, h and i can also be determined using column values.

Once, this is done, the corresponding code becomes :

int main()
{
    int n=3,t=5;
    int total_num=0;
    for(int a=0;a<=t;a++)
    {
        square[0][0]=a;
        for(int b=0;b<=t;b++)
        {
            square[0][1]=b;
            int c = t - (a+b);
            if (c>=0)
            {
                square[0][2]=c;
                for(int d=0;d<=t;d++)
                {
                    square[1][0]=d;
                    for(int e=0;e<=t;e++)
                    {
                        square[1][1]=e;
                        int f = t - (d+e);
                        if (f >= 0)
                        {
                            square[1][2]=f;
                            int g = t - (a+d);
                            if (g >= 0)
                            {
                                square[2][0]=g;
                                int h = t - (b+e);
                                if (h >= 0)
                                {
                                    square[2][1]=h;
                                    int i = t - (g+h);
                                    assert(i == (t - (c+f)));
                                    if (i >= 0)
                                    {
                                        square[2][2]=i;
                                        if(final_check(n,t))  //check
                                        {
                                            display(n);
                                            total_num++;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout<<"total number of semi magic square: "<<total_num<<endl;
    return 0;
}

Once this is done, the final_check method becomes useless as all the generated squares are "magic".

Something else could easily be improved : you shouldn't use global variables as they make things hard to follow. In your case, it is quite easy to get rid of it. I also take this chance to re-organise the different loops/checks and change the limits for the loops so that we do not need to check that values are in the right ranger afterwards :

void display(int a, int b, int c, int d, int e, int f, int g, int h, int i)
{
    cout << a << "\t" << b << "\t" << c << endl;
    cout << d << "\t" << e << "\t" << f << endl;
    cout << g << "\t" << h << "\t" << i << endl;
    cout <<"************"<<endl;
}

/*
   a b c
   d e f
   g h i */

//count $H_3(1)$
int main()
{
    int t=5;
    int total_num=0;
    for(int a=0;a<=t;a++)
    {
        for(int b=0;b<=t-a;b++)
        {
            int c = t - (a+b);
            assert(c>=0);
            for(int d=0;d<=t-a;d++)
            {
                int g = t - (a+d);
                assert(g >= 0);
                for(int e=0;e<=t-d && e<=t-b;e++)
                {
                    int f = t - (d+e);
                    assert(f >= 0);
                    int h = t - (b+e);
                    assert(h >= 0);
                    int i = t - (g+h);
                    assert(i == (t - (c+f)));
                    if (i >= 0)
                    {
                        display(a, b, c, d, e, f, g, h, i);
                        total_num++;
                    }
                }
            }
        }
    }
    cout<<"total number of semi magic square: "<<total_num<<endl;
    return 0;
}

A few last things I'd like to tell :

• using namespace std; is sometimes considered a bad practice. Some might say it is ok in a cpp file (by opposition to header file)
• one could easily do with a few more comments
• I am quite surprised that your code seems to assume that t is known.

This is as far as I can go re-using your code. A more interesting approach would use backtracking. You should be able to find already implemented algorithms using it to generate magic squares.

Answer 2

Don't make this global:

int square[3][3];

You'll encounter bugs if it gets modified somewhere without your knowledge. Instead, create the array in main() and pass it to the functions that need it.

You should also use a storage container, such as std::vector (assuming you're not using C++11), instead of a 2D C-style array. Always try to avoid using C-style arrays in C++, especially when you need to pass them around to functions (a pointer is passed and not the array itself).

The initialization should look like this:

std::vector<std::vector<int> > square(3, std::vector<int>(3));

It is rather long, but you can first use a typedef to make the type shorter:

typedef std::vector<std::vector<int> > Matrix;

The above initialization will then look like this:

Matrix square(3, std::vector<int>(3));

Feel free to change the typedef name; it was just used as a demonstration.

Answer 3

Ok - if the OP doesn't change its question i.e. the (flawed) definition of a semi-magic-square the solution to the whole problem becomes trivial:

If a semi-magic square can contain any number as many times as it needs to, I can just define one like this:

2 2
2 2

In fact as Josay pointed out for any possible combination of numbers in all fields except the outermost column, there will be exactly one set of numbers which will statisfy the row/column condition for all rows/columns except the last one. If I have a square of any size like this:

     1  2  3  4  5

1    A  A  A  A  B
2    A  A  A  A  B
3    A  A  A  A  B
4    A  A  A  A  B
5    B  B  B  B  C

For any combination of A values, all the values of B are automatically defines as a11+a12+a13+a14+b15 = t, so b15 = t-a11-a12-a13-a14 so I can always find these values, the only problem remaining is C. Since C is defined by two constraints: C = t-b15-b25-b35-b45 && C = t-b51-b52-b53-b54 So the only thing you need to check is if b51+b52+b53+b54 == b15+b25+b35+b45

This expands to:

(t-a11-a21-a31-a41)+(t-a12-a22-a32-a42)+(t-a13-a23-a33-a43)+(t-a14-a24-a34-a44) == (t-a11-a12-a13-a14)+(t-a21-a22-a23-a24)+(t-a31-a32-a33-a34)+(t-a41-a42-a43-a44)
minimizes to: 1 == 1

Since each A-value is present exactly once on each side of the equation it always holds true. So we can always find a matching C-Value.

So we can find exactly one set of matching values for each combination of A-Values, so for each combination of A-Values there is exactly one semi-magic-square (per the flawed definition above) The number of possible A-Values can be calculated by just combining the Number of A-Values with the number of possible values... But since the opening definition never restricted the number of possible values it would always be infinity ^^ Otherwise: Number of squares = x^((n-1)^2)

The whole thing would actually be quite different for ACTUAL semi-magic squares:

Real semi-magic-squares have the interesting third requirement: 3. Each number in the interval [1,(n*n)] must be present exactly once in the semi-magic-square.