Chess Rook (Thuật toán quay lui BackTracking)

package Advance;

import java.io.FileInputStream;
import java.util.Scanner;

public class ChessRook {
public static void main(String[] args) throws Exception {
new ChessRook().inIt();
}

int N;
int[][] chess;
int max;

private void inIt() throws Exception {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int test_case = 1; test_case <= T; test_case++) {
N = sc.nextInt();
chess = new int[N][N];
max = 0;
for (int i = 0; i < N; i++) {
String s = sc.next();
for (int j = 0; j < s.length(); j++) {
if (s.charAt(j) == 'X') {
chess[i][j] = 2;
}
}
}
back(0, 0);
System.out.println("Case #" + test_case);
System.out.println(max);
}
}

private void back(int row, int dem) {
if(dem > max){
max = dem;
}
int i,j;
for (i = row; i < N; i++) {
for (j = 0; j < N; j++) {
if (check(i, j) == true) {
chess[i][j] = 1;
back(i, dem + 1);
chess[i][j] = 0;
}
}
}
}

private boolean check(int row, int col) {
if (chess[row][col] == 1 || chess[row][col] == 2)
return false;
for (int i = 1; i <= row; i++) {
if (chess[row - i][col] == 1) {
return false;
}
else if (chess[row - i][col] == 2)
break;
}
for (int i = col; i < N; i++) {
if (chess[row][i] == 1) {
return false;
}
else if (chess[row][i] == 2)
break;
}
for (int i = col - 1; i >= 0; i--) {
if (chess[row][i] == 1) {
return false;
}
else if (chess[row][i] == 2)
break;
}

return true;
}
}