queens
unknown
plain_text
2 years ago
1.6 kB
7
Indexable
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); } } } }
Editor is loading...