queens

package practise;

import java.util.Scanner;

public class queens {
	
	static int n = 8, count;
	static int[][] cases = new int[100][n];
	static boolean[] col , diagup, diagdown;
	static int [] trace = new int[n];
	
	private static void check(int i) {
		for(int j = 0; j < n; j++) {
			if(!col[j] && !diagup[i - j + n - 1] && !diagdown[i + j]) {
				trace[i] = j; 
				col[j] = true; diagup[i - j + n - 1] = true; diagdown[i + j] = true;
				if(i == n - 1) {
//					System.out.println("Case " + count);
					for(int k = 0; k < n; k++) {
						cases[count][k] = trace[k];
//						System.out.print(cases[count][k] + " ");
					}
					count++;
//					System.out.println();
				}
				else check(i + 1);
				col[j] = false; diagup[i - j + n - 1] = false; diagdown[i + j] = false;
			}
			
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		count = 0;
		col = new boolean[n]; diagup = new boolean[2 * n]; diagdown = new boolean[2 * n];
		check(0);
		
		int testcase = sc.nextInt();
		int[][] board = new int[n][n];
		for(int tc = 0; tc < testcase; tc++) {
			int nb = sc.nextInt();
			for(int i = 0; i < nb; i++) {
				for(int j = 0; j < n; j++) {
					for(int k = 0; k < n; k++) {
						board[j][k] = sc.nextInt();
					}
				}
				int max = 0, sum;
				for(int j = 0; j < count; j++) {
					sum = 0;
					for(int k = 0; k < n; k++) {
						sum += board[k][cases[j][k]];
					}
					if(max < sum) max = sum;
				}
				System.out.println(max);
			}
		}
		
	}

}