
import java.util.Arrays;

public class Maerz14_Backtrack {
	public static void main(String[] args) {
		int[][] sq={
						{2 ,7, 6},
						{9, 5 ,1}, 
						{4 ,3 ,8}
						};
		
		System.out.println(isSolved(sq));
		
		MagicSquare(3);
		
	}

	static void MagicSquare(int n) {
		int[][] sq = new int[n][n];
		if (solve(sq, 0, new boolean[n * n]))
			print(sq);
	}

	private static void print(int[][] sq) {
		for (int[] s : sq) {
			System.out.println(Arrays.toString(s));
		}
	}
	static boolean isSolved(int[][] sq) {
		int n = sq.length;
		int checkSum = ((n * n * n) + n) / 2;
		int rowSum = 0, colSum = 0, diag1Sum = 0, diag2Sum = 0;
		
		for(int y= 0 ; y< n; y++){
			
			diag1Sum += sq[y][y];
			diag2Sum += sq[n-1-y][n-1-y];
			
			for(int x=0; x < n ; x++){
				rowSum += sq[y][x];
				colSum += sq[x][y];
			}
			
			if(rowSum != checkSum || colSum != checkSum)
				return false;

			rowSum=colSum=0;
		}

		if(diag1Sum != checkSum || diag2Sum != checkSum)
			return false;
		
		return true;
	}
	
	static boolean solve(int[][] sq, int pos, boolean[] used) {
		int n = sq.length;
		int col = pos % n;
		int row = (pos - col) / n;
		
		// Basisfall
		if(isSolved(sq))
			return true;
		
		//Rekursion
		for(int i=0; i < n*n; i++){
			if(!used[i]){
				used[i]=true;
				int c=i+1;
				sq[col][row]=c;
				
				if(solve(sq,pos+1,used))
					return true;
				
				sq[col][row]=0;
				used[i]=false;
			}
		}
		return false;
	}
	
}