## 12782 - Magic Squares

All about problems in Volume 127. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

dlorah01
New poster
Posts: 1
Joined: Sun Nov 30, 2014 6:21 am

### Re: 12782 - Magic Squares

Hi.
I don´t know how to solve this problem. I want to know if this problem can be solved using graph theorem. In this case what is the procedure to solve this: BFS, DFS, Dijkstra, Bellman-Ford? Sorry but im a completely newbie on this. Thanks!!!
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 12782 - Magic Squares

I used backtracking.
DFS uses backtracking.
Check input and AC output for thousands of problems on uDebug!
ocin_lr
New poster
Posts: 3
Joined: Sat Jun 27, 2015 7:52 pm

### Re: 12782 - Magic Squares

Hi,

I have tried this problem using Backtracking with pruning in C++, but so far my code is not fast enough.

The pruning I do is the following(lets call N the amount of numbers, nn the square root of N, S the modulo of the Magic Square):
- if N==1, then Yes
- otherwise if N!=4 && N!=9 && N!=16 then No
- if the sum of the N numbers is not divisible by nn, then No
sort the numbers and permute them using next_permutation:
if the numbers of the first .. nn-1 block of nn numbers does not sum up to S, then continue with next permutation
otherwise, if all nn disjoint blocks of nn numbers sum up to S, then verify vertically and diagonally

what other pruning might be missing?
Here is my code:

Code: Select all

``````#define loop(i,a,b) for(i=a;i<b;++i)
#define LIM 1005
...
char cad[LIM], *pt;
int n, nn, s, a[16], fac;

bool verify(){
int i, j, m;
loop(i, 0, nn){
m=0;
loop(j, 0, nn) m+=a[i+j*nn];
if (m!=s) return false;
}
loop(i, 0, nn){
m=0;
loop(j, 0, nn) m+=a[i*nn+j];
if (m!=s) return false;
}
loop(j, 0, nn){
m=0;
loop(i, 0, nn) m+=a[((j+i)%nn)*nn+(i+j)%nn];
if (m!=s) continue;
m=0;
loop(i, 0, nn) m+=a[((i+j)%nn)*nn+(nn-((i+j)%nn)-1)];
if (m!=s) continue;
return true;
}
return false;
}

int main(){
int i, j, b;
bool found=false;
freopen("MagicSquares12782.txt","r",stdin);
while (gets(cad)){
n=s=0;
pt=strtok(cad, " ");
while(pt!=NULL){
a[n++]=atoi(pt);
s+=a[n-1];
//printf("s=%d\n", s);
pt=strtok(NULL, " ");
}
//loop(i, 0, n) printf("%d ", a[i]); puts("");
if (n==0) {puts("N"); continue; }
if(n==1){ puts("Y"); continue; }
if (n!=4 && n!=9 && n!=16){ puts("N"); continue; }
loop(nn, 1, 5) if (nn*nn==n) break;
if (abs(s)%nn!=0){ puts("N"); continue; }
s/=nn;
fac=1;
loop(i, 2, nn+1) fac*=i;
//printf("->%d\n", fac);
sort(a, a+n);
found=false;
//printf("%d %d %d %d\n", n, nn, s, abs(s));
do{
loop(i, 0, nn){
b=0;
loop(j, i*nn, (i+1)*nn) b+=a[j];
if (i<nn-1 && b!=s){
sort(a+(i+1)*nn, a+n, greater<int>());
break;
}
}
if (i==nn) found=verify();
}while(!found && next_permutation(a, a+n));
//loop(i, 0, n) printf("%d ", a[i]); puts("");
puts(found?"Y":"N");
}
return 0;
}
``````
ocin_lr
New poster
Posts: 3
Joined: Sat Jun 27, 2015 7:52 pm

### Re: 12782 - Magic Squares

Here there are some test cases you might try. The solution is in http://www.udebug.com/UVa/12782:

Code: Select all

``````1 2 3 4 5 6 7 8 9
1 14 4 14 11 7 6 9 8 13 10 2 10 3 5 15
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 8
1 2 3 4
1 1 -1 -1
1 1 1 1
-1 -1 -1 -1
1 1 1
0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 2 3 1 2 3 1 2 3
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
1 0 3 4 1 0 3 4 1 0 3 4 1 0 3 4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
-1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16
1
0
-42
13``````