12782 - Magic Squares

[dlorah01]

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]

I used backtracking.
DFS uses backtracking.

[ocin_lr]

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]

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