N皇后问题

 1 public class Solution {
 2 
 3     public static List<List<String>> solveNQueens(int n) {
 4         List<List<String>> res = new ArrayList<>();
 5         int[] queenList = new int[n];
 6         placeQueen(queenList, 0, n, res); //在第0行放Q
 7         return res;
 8     }
 9 
10     private static void placeQueen(int[] queenList, int row, int n, List<List<String>> res) {
11         // 已经填满，生成结果
12         if(row == n) {
13             ArrayList<Stirng> list = new ArrayList<>();
14             for(int i = 0; i < n; i++) {
15 
16                 String str = "";
17                 for(int col = 0; col < n; col++) {
18                     if(queenList[i] == col) {
19                         str+="Q";
20                     } else {
21                         str+=".";
22                     }
23                 }
24 
25                 list.add(str);
26             }
27 
28             res.add(list);
29         }
30 
31         for(int col = 0; col < n; col++) {
32             if(isValid(queenList, row, col)) {
33                 // important here
34                 queenList[row] == col;
35 
36                 placeQueen(queenList, row+1, n, res);
37             }
38         }
39     }
40 
41     private static boolean isValid(int[] queenList, int row, int col) {
42         for (int i = 0; i < row; i++) {
43 
44             int pos = queenList[i];
45 
46             if (pos == col) { //和新加入的Q处于同一列
47                 return false;
48             }
49 
50             if (pos + row - i == col) { //在新加入的Q的右对角线上
51                 return false;
52             }
53 
54             if (pos - row + i == col) { //在新加入的Q的左对角线上
55                 return false;
56             }
57         }
58 
59         return true;
60     }
61 }