How many semi magic squares are there?

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?

-
Hi! Sorry - are you not missing the big constraint: 3. A semi-Magic Square must contain all numbers from 1..n*n exactly once? Otherwise you don't even need a program... – Falco Jul 7 '14 at 14:35
No, we don't need this constraint, for example, when n=3, t=1, the square $$\left( \begin{matrix} 1&0&0\\ 0&1&0\\ 0&0&1\\ \end{matrix} \right)$$is good. What's more, you can see [this](math.binghamton.edu/dennis/Birkhoff/polynomials.html), $$H_3(t)=1+9t/4+15t^2/8+3t^3/4+t^4/8$$ Apparently, $H_3(15)$ is very big, but this link only show $H_3(15)=8$ it said "treating squares differing by rotations and reflections as identical". – user1024 Jul 8 '14 at 2:44

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.

-
Good review. But with the flawed definition of semi-magic-squares the whole problem becomes tirival, since we can find exactly 1 solution for each possible combination of (n-1)² fields each having values in [1,t] you can just calculate the number of possible flawed squares as (t-1)^((n-1)^2) – Falco Jul 7 '14 at 14:38
Seems like a very interesting comment. Would you be able to share your thoughts with more details in a dedicated answer ? – Josay Jul 7 '14 at 14:56
See my answer ;-) – Falco Jul 7 '14 at 15:37
First, thank you for your answer, it really shorted my program running time, but i still can't expand it to other situation, for example when n=4 or 5. – user1024 Jul 8 '14 at 3:34

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.

-
Thanks for your remind, global variables are not good. By the way, does vector<int> have the same efficiency compared with int[]. – user1024 Jul 8 '14 at 3:38
@user2468587: There's not a great difference since std::vector is mainly a class wrapped around a dynamically-allocated array. You could instead use std::array (fixed-size), but that would require C++11. – Jamal Jul 8 '14 at 3:40
@user2468587: On another note, please consider upvoting any answers you've found helpful. You may also accept the one answer that has helped you the most. – Jamal Jul 8 '14 at 3:41

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.

-
Your analysis seems interesting. However, I think you have forgotten a restriction somewhere (I reckon the fact that the automatically defined variables must be in the range [0, t]). After performing test for multiple values of t (from -1, to 30, it seems like the values follow the following sequence : oeis.org/A002817 ). – Josay Jul 7 '14 at 15:58
Thanks for your analysis, but my semi-magic's variables are in the range [0,t], all are integers. the magic squares needs your third constraint. – user1024 Jul 8 '14 at 3:41
Yes... but the range 0,t is not the big constraint - the big constraint for a REAL semi-magic square is that each number in [1,t] (zero is usually not allowed) can only be used ONCE in the whole square!!! So you can use no number twice... this makes it interesting ;) – Falco Jul 8 '14 at 7:32