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:
  
  
  The square is \$n*n\$ dimension
  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&lt;iostream&gt;
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&lt;n;i++)
    {
        int sum_col=0;
        int sum_row=0;
        for(int j=0;j&lt;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&lt;n;i++)
    {
        for(int j=0;j&lt;n;j++)
            cout&lt;&lt;square[i][j]&lt;&lt;"\t";
        cout&lt;&lt;endl;
    }
    cout&lt;&lt;"************"&lt;&lt;endl;
}

//count \$H_3(1)\$
int main()
{
    int n=3,t=5;
    int total_num=0;
    for(int a=0;a&lt;=t;a++)
    {
        square[0][0]=a;
        for(int b=0;b&lt;=t;b++)
        {
            square[0][1]=b;
            for(int c=0;c&lt;=t;c++)
            {
                square[0][2]=c;
                for(int d=0;d&lt;=t;d++)
                {
                    square[1][0]=d;
                    for(int e=0;e&lt;=t;e++)
                    {
                        square[1][1]=e;
                        for(int f=0;f&lt;=t;f++)
                        {
                            square[1][2]=f;
                            for(int g=0;g&lt;=t;g++)
                            {
                                square[2][0]=g;
                                for(int h=0;h&lt;=t;h++)
                                {
                                    square[2][1]=h;
                                    for(int i=0;i&lt;=t;i++)
                                    {
                                        square[2][2]=i;
                                        if(final_check(n,t))  //check
                                        {
                                            display(n);
                                            total_num++;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout&lt;&lt;"total number of semi magic square: "&lt;&lt;total_num&lt;&lt;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?
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&lt;=t;a++)
    {
        square[0][0]=a;
        for(int b=0;b&lt;=t;b++)
        {
            square[0][1]=b;
            int c = t - (a+b);
            if (c&gt;=0)
            {
                square[0][2]=c;
                for(int d=0;d&lt;=t;d++)
                {
                    square[1][0]=d;
                    for(int e=0;e&lt;=t;e++)
                    {
                        square[1][1]=e;
                        int f = t - (d+e);
                        if (f &gt;= 0)
                        {
                            square[1][2]=f;
                            int g = t - (a+d);
                            if (g &gt;= 0)
                            {
                                square[2][0]=g;
                                int h = t - (b+e);
                                if (h &gt;= 0)
                                {
                                    square[2][1]=h;
                                    int i = t - (g+h);
                                    assert(i == (t - (c+f)));
                                    if (i &gt;= 0)
                                    {
                                        square[2][2]=i;
                                        if(final_check(n,t))  //check
                                        {
                                            display(n);
                                            total_num++;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout&lt;&lt;"total number of semi magic square: "&lt;&lt;total_num&lt;&lt;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 &lt;&lt; a &lt;&lt; "\t" &lt;&lt; b &lt;&lt; "\t" &lt;&lt; c &lt;&lt; endl;
    cout &lt;&lt; d &lt;&lt; "\t" &lt;&lt; e &lt;&lt; "\t" &lt;&lt; f &lt;&lt; endl;
    cout &lt;&lt; g &lt;&lt; "\t" &lt;&lt; h &lt;&lt; "\t" &lt;&lt; i &lt;&lt; endl;
    cout &lt;&lt;"************"&lt;&lt;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&lt;=t;a++)
    {
        for(int b=0;b&lt;=t-a;b++)
        {
            int c = t - (a+b);
            assert(c&gt;=0);
            for(int d=0;d&lt;=t-a;d++)
            {
                int g = t - (a+d);
                assert(g &gt;= 0);
                for(int e=0;e&lt;=t-d &amp;&amp; e&lt;=t-b;e++)
                {
                    int f = t - (d+e);
                    assert(f &gt;= 0);
                    int h = t - (b+e);
                    assert(h &gt;= 0);
                    int i = t - (g+h);
                    assert(i == (t - (c+f)));
                    if (i &gt;= 0)
                    {
                        display(a, b, c, d, e, f, g, h, i);
                        total_num++;
                    }
                }
            }
        }
    }
    cout&lt;&lt;"total number of semi magic square: "&lt;&lt;total_num&lt;&lt;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.