DFS, Backtracking1
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
36class Solution {
private int count=0;
private void dfs(char[][] board,int colIndex){
if(colIndex==board.length){
count++;
return;
}
for(int i=0;i<board.length;i++){
if(isValid(board,i,colIndex)){
board[i][colIndex]='Q';
dfs(board,colIndex+1);
board[i][colIndex]='.';
}
}
}
private boolean isValid(char[][] board,int r,int c){
for(int i=0;i<board.length;i++){
for(int j=0;j<=c;j++){
if(board[i][j]=='Q'&&(i==r||Math.abs(r-i)==Math.abs(c-j))) return false;
}
}
return true;
}
public int totalNQueens(int n) {
char[][] board=new char[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
board[i][j]='.';
}
}
dfs(board,0);
return count;
}
}