forked from algorithm009-class01/algorithm009-class01
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolveNQueensN.java
More file actions
52 lines (48 loc) · 1.58 KB
/
SolveNQueensN.java
File metadata and controls
52 lines (48 loc) · 1.58 KB
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
package recur;
import java.util.ArrayList;
import java.util.List;
public class SolveNQueensN {
public List<List<String>> solveNQueens(int n) {
List<List<String>> ret = new ArrayList<>();
char[][] curr = new char[n][n];
for(int i = 0;i<n;i++){
for(int j = 0;j < n;j++){
curr[i][j] = '.';
}
}
boolean[] col = new boolean[n];
boolean[] diag1 = new boolean[2*n - 1];
boolean[] diag2 = new boolean[2*n - 1];
solve(curr,0,n,ret,col,diag1,diag2);
return ret;
}
private void solve(char[][] curr,int idx,int n,List<List<String>> ret,boolean[] col,boolean[] diag1,boolean[] diag2){
if(idx == n){
List<String> toAdd = new ArrayList<>();
for(int i =0;i<n;i++){
toAdd.add(String.valueOf(curr[i]));
}
ret.add(toAdd);
return;
}
for(int j = 0;j < n;j++){
if(col[j] || diag1[idx + n -j -1] || diag2[idx + j]){
continue;
}
col[j] = true;
diag1[idx + n - j -1] = true;
diag2[idx + j] = true;
curr[idx][j] = 'Q';
solve(curr,idx + 1,n,ret,col,diag1,diag2);
curr[idx][j] = '.';
col[j] = false;
diag1[idx + n -j -1] = false;
diag2[idx + j] = false;
}
}
public static void main(String[] args) {
SolveNQueensN solveNQueensN = new SolveNQueensN();
List<List<String>> r = solveNQueensN.solveNQueens(4);
System.out.println(r);
}
}