N-Queens

 1 public class Solution {
 2     public ArrayList<String[]> solveNQueens(int n) {
 3         ArrayList<String[]> res = new ArrayList<String[]>();
 4         if(n<=0) return res;
 5         DFS(n,0,new int[n],res);
 6         return res;
 7     }
 8     public void DFS(int n,int row,int []queenList,ArrayList<String[]>res){
 9         if(row==n){
10             StringBuilder [] sb = new StringBuilder[n];
11             for(int i=0;i<n;i++){
12                 sb[i]=new StringBuilder();
13                 for(int j=0;j<n;j++){
14                     sb[i].append(‘.‘);
15                 }
16             }
17             for(int i=0;i<n;i++){
18                 int colIndex = queenList[i];
19                 sb[i].setCharAt(colIndex,‘Q‘);
20             }
21             String[] output= new String[n];
22             for(int i=0;i<n;i++){
23                 output[i] = sb[i].toString();
24             }
25             res.add(output);
26         }
27         for(int col=0;col<n;col++){
28             if(isValid(queenList,row,col)){
29                 queenList[row] = col;
30                 DFS(n,row+1,queenList,res);
31             }
32         }
33     }
34     public boolean isValid(int []queenList,int row,int col){
35         for(int preRow=0;preRow<row;preRow++){
36             int preCol = queenList[preRow];
37             if(preCol==col) return false;
38             if(Math.abs(preCol-col)==Math.abs(preRow-row))return false;
39         }
40         return true;
41     }
42 }