leetcode 51. N皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例:

输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],

["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-queens
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 1 class Solution {
 2     private boolean isOk(char[][] res, int i, int j, int n){ // 检测位置(i,j)可不可以放置
 3         if (res[i][j] == 'Q') return false;
 4         // 列 与 行
 5         for (int k = 0; k < n; ++k){
 6             if (k != i && res[k][j] == 'Q')
 7                 return false;
 8             if (k != j && res[i][k] == 'Q')
 9                 return false;
10         }
11         // 皇后左上
12         for (int k = 1; i-k >= 0 && j-k >= 0; ++k)
13             if (res[i-k][j-k] == 'Q')
14                 return false;
15         // 皇后右下
16         for (int k = 1; i+k < n && j+k < n; ++k)
17             if (res[i+k][j+k] == 'Q')
18                 return false;
19         // 皇后右上
20         for (int k = 1; i-k >=0 && j+k < n; ++k)
21             if (res[i-k][j+k] == 'Q')
22                 return false;
23         // 皇后左下
24         for (int k = 1; i+k < n && j-k >= 0; ++k)
25             if (res[i+k][j-k] == 'Q')
26                 return false;
27         return true;
28     }
29     // cur:在第cur行放置皇后
30     // lists:存放不同的放置方案
31     private void result(int n, char[][] res, int cur, List<List<String>> lists){
32         if (cur == n){
33             List<String> list = new ArrayList<>();
34             for (int i = 0; i < n; ++i){
35                 list.add(new String(res[i]));
36             }
37             lists.add(list);
38             return ;
39         }
40         for (int i = 0; i < n; ++i){
41             if (isOk(res, cur, i, n)){
42                 res[cur][i] = 'Q';
43                 result(n, res, cur+1, lists);
44                 res[cur][i] = '.';
45             }
46         }
47     }
48
49
50
51     public List<List<String>> solveNQueens(int n) {
52         char[][] res = new char[n][n];
53         /*
54         .：可以放置皇后
55         Q：已经放置皇后
56         -：和已有皇后冲突
57          */
58         for (int i = 0; i < n; i++)
59             for (int j = 0; j < n; j++)
60                 res[i][j] = '.';
61         List<List<String>> lists = new ArrayList<>();
62         result(n, res, 0, lists);
63         return lists;
64     }
65 }