#include <stdio.h> 
   
  int grid[9] = {0}; 
  void PrintGrid(void); 
  int CheckSolved(void); 
  int TryAt(int n, int at); 
  int Try(int n); 
   
  void main(){ 
  	char c; 
  	PrintGrid(); 
  	printf("Take a pen & paper, and try the puzzle yourself.\n"); 
  	printf("  All you have to do is write numbers from 1 to 9 \n"); 
  	printf("  in a 3x3 grid, such that all rows, columns and \n"); 
  	printf("  diagonals add up to 15.\n"); 
  	printf("Press <Enter> to see who is faster... :)"); 
  	scanf("%c", &c); 
  	printf("solving the puzzle...\n"); 
  	Try(9); 
  	PrintGrid(); 
  } 
   
  int Try(int n){ 
  	int at; 
  	if(n==0){ 
  		if(CheckSolved()){ 
  			return 1; 
  		} 
  		else 
  			return 0; 
  	} 
  		 
  	for(at=0; at<9; at++){ 
  		if(TryAt(n, at)){ 
  			if(Try(n-1)){ 
  				return 1; 
  			} 
  			grid[at]=0; 
  		}		 
  	} 
  	return 0; 
  } 
   
  int TryAt(int n, int at){ 
  	int r,c,sum; 
  	if(! (n>=1 && n<=9)|| 
  	  !(at>=0 && at<=8) ||  
  	  grid[at] ) 
  		return 0; 
  	 
  	grid[at] = n; 
   
  	for(r=0; r<3; r++){ 
  		sum=0; 
  		for(c=0; c<3; c++){ 
  			sum+= grid[3*r+c]; 
  		} 
  		if(sum>15) 
  			goto returnFalse; 
  	} 
  	for(c=0; c<3; c++){ 
  		sum=0; 
  		for(r=0; r<3; r++){ 
  			sum+= grid[3*r+c]; 
  		} 
  		if(sum>15) 
  			goto returnFalse; 
  	} 
  	if(grid[0]+grid[4]+grid[8] > 15) 
  			goto returnFalse; 
  	if(grid[2]+grid[4]+grid[6] >15) 
  			goto returnFalse; 
  	return 1; 
   
  	returnFalse: 
  	grid[at] = 0; 
  	return 0; 
  } 
  void PrintGrid(){ 
  	int r,c; 
  	printf("+-+-+-+\n"); 
  	for(r=0; r<3; r++){ 
  		printf("|"); 
  		for(c=0; c<3; c++){ 
  			if(!grid[3*r+c]) 
  				printf(" |"); 
  			else 
  				printf("%d|", grid[3*r+c]); 
  		} 
  		printf("\n+-+-+-+\n"); 
  	} 
  } 
  int CheckSolved(){ 
  	int r,c,sum; 
  	for(r=0; r<3; r++){ 
  		sum=0; 
  		for(c=0; c<3; c++){ 
  			sum+= grid[3*r+c]; 
  		} 
  		if(sum != 15) 
  			return 0; 
  	} 
  	for(c=0; c<3; c++){ 
  		sum=0; 
  		for(r=0; r<3; r++){ 
  			sum+= grid[3*r+c]; 
  		} 
  		if(sum!=15) 
  			return 0; 
  	} 
  	if(grid[0]+grid[4]+grid[8] != 15) 
  		return 0; 
  	if(grid[2]+grid[4]+grid[6] !=15) 
  		return 0; 
  	 
  	return 1; 
  }