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

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

Re: 12782 - Magic Squares

Post by dlorah01 » Sun Nov 30, 2014 6:27 am

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

Post by brianfry713 » Wed Dec 03, 2014 1:16 am

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

Post by ocin_lr » Sat Aug 01, 2015 5:48 pm

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

Post by ocin_lr » Sat Aug 01, 2015 5:50 pm

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

Post Reply

Return to “Volume 127 (12700-12799)”