[LeetCode] 51. N-Queens

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1
Output: [["Q"]]

Constraints:

• 1 <= n <= 9

N 皇后。

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

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

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

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

思路是 DFS 回溯。这是一道经典的回溯题，建议先尝试回溯类型的其他题目再尝试这道题目。我参考了这个帖子。

对于一个边长为 n 的棋盘，我们需要去找出所有方案，看看 N 个皇后可以怎么摆。基本思路是先创建一个边长为 n 的棋盘，用点表示没有棋子的位置，然后每放置一个皇后就去判断当前棋盘是否合法，如此试探出所有可行解。

时间O(N * N!) - 放置皇后有 N! 种方式 * 每放置一个棋子就要检查整个棋盘（N 行）是否合法

空间O(N * N)

Java实现

 1 class Solution {
 2     List<List<String>> res = new ArrayList<>();
 3     
 4     public List<List<String>> solveNQueens(int n) {
 5         List<String> board = new ArrayList<>();
 6         for (int i = 0; i < n; i++) {
 7             StringBuilder sb = new StringBuilder();
 8             for (int j = 0; j < n; j++) {
 9                 sb.append('.');
10             }
11             board.add(sb.toString());
12         }
13         helper(board, 0);
14         return res;
15     }
16     
17     private void helper(List<String> board, int row) {
18         if (row == board.size()) {
19             res.add(new ArrayList<>(board));
20             return;
21         }
22         
23         int n = board.get(row).length();
24         for (int col = 0; col < n; col++) {
25             if (!isValid(board, row, col)) {
26                 continue;
27             }
28             StringBuilder sb = new StringBuilder(board.get(row));
29             sb.setCharAt(col, 'Q');
30             board.set(row, sb.toString());
31             // 进入下一行决策
32             helper(board, row + 1);
33             // 撤销选择
34             sb.setCharAt(col, '.');
35             board.set(row, sb.toString());
36         }
37     }
38     
39     private boolean isValid(List<String> board, int row, int col) {
40         int n = board.size();
41         // 检查列是否有皇后互相冲突
42         for (int i = 0; i < n; i++) {
43             if (board.get(i).charAt(col) == 'Q') {
44                 return false;
45             }
46         }
47         
48         // 检查右上方是否有皇后互相冲突
49         for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
50             if (board.get(i).charAt(j) == 'Q') {
51                 return false;
52             }
53         }
54         
55         // 检查左上方是否有皇后互相冲突
56         for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
57             if (board.get(i).charAt(j) == 'Q') {
58                 return false;
59             }
60         }
61         return true;
62     }
63 }

LeetCode 题目总结