N-Queens

 1 public class Solution {
 2     public static ArrayList<String[]> solveNQueens(int n) {
 3         // Start typing your Java solution below
 4         // DO NOT write main() function
 5         ArrayList<String[]> result = new ArrayList<String[]>();
 6         int depth = 0;
 7         int[] rows = new int[n];
 8         for (int i = 0; i < n; i++) {
 9             rows[i] = n + 1;
10         }
11         dfs(depth, rows, n, result);
12         return result;
13     }
14 
15     public static void dfs(int depth, int[] rows, int n, ArrayList<String[]> result) {
16         if (depth == n) {
17             String[] s = new String[n];
18             for (int i = 0; i < n; i++) {
19                 int m = rows[i];
20                 StringBuilder tmp = new StringBuilder();
21                 for (int j = 0; j < n; j++) {
22                     if (j == m) {
23                         tmp.append("Q");
24                         continue;
25                     }
26                     tmp.append(".");
27                 }
28                 s[i] = tmp.toString();
29             }
30             result.add(s);
31             return;
32         }
33         for (int i = 0; i < n; i++) {
34             rows[depth] = i;
35             if (isValid(rows, depth)) {
36                 dfs(depth + 1, rows, n, result);
37             }
38         }
39 
40     }
41     public static boolean isValid(int[] rows, int depth) {
42         for (int i = 0; i < depth; i++) {
43             if (rows[i] == rows[depth]
44                     || Math.abs(rows[i] - rows[depth]) == Math.abs(i - depth)) {
45                 return false;
46             }
47         }
48         return true;
49     }
50 }