N-Queens II

 1 public class Solution {
 2     public int totalNQueens(int n) {
 3         // IMPORTANT: Please reset any member data you declared, as
 4         // the same Solution instance will be reused for each test case.
 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.size();
13     }
14     
15     private 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     private 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 }