patterncppMinor
How many semi magic squares are there?
Viewed 0 times
semihowaremagicsquaresmanythere
Problem
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 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:
When \$n = 3\$, it's something like this sequence.
```
#include
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++)
{
squ
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|981541When \$n = 3\$, it's something like this sequence.
```
#include
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++)
{
squ
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 :
by making the different values go from
Once, this is done, the corresponding code becomes :
Once this is done, the
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 :
A few last things I'd like to tell :
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.
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 iby 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=0)
{
square[0][2]=c;
for(int d=0;d= 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 =0);
for(int d=0;d= 0);
for(int e=0;e= 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 acppfile (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
tis 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.
Code Snippets
a b c
d e f
g h iint 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;
}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;
}Context
StackExchange Code Review Q#56319, answer score: 4
Revisions (0)
No revisions yet.