-
Notifications
You must be signed in to change notification settings - Fork 23
/
52. N-Queens II
32 lines (30 loc) · 895 Bytes
/
52. N-Queens II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
int count;
public int totalNQueens(int n) {
count = 0;
List<int[]> queens = new ArrayList<>();
dfs(n, 0, queens);
return count;
}
private void dfs(int n, int row, List<int[]> queens) {
if(queens.size() == n) {
count++;
return;
}
for(int col = 0; col < n; col++) {
if(canPlaceQueen(row, col, queens)) {
queens.add(new int[]{row, col});
dfs(n, row+1, queens);
queens.remove(queens.size()-1);
}
}
}
private boolean canPlaceQueen(int row, int col, List<int[]> queens) {
for(int[] q : queens) {
int dx = Math.abs(q[0] - row);
int dy = Math.abs(q[1] - col);
if(dx == 0 || dy == 0 || dx == dy) return false;
}
return true;
}
}