LeetCode 51.n皇后问题

小鱼儿 2022-12-21 15:50 154阅读 0赞

### LeetCode 51.n皇后问题 ###

*  题目：
 *  解题方法：
 *   *  方法1：回溯法
     *   *  Java实现

# 题目： #

[LeetCode 51.子集][LeetCode 51.]

> n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。  
> 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。  
> 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

**Example 1:**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Blbmd4aWFvemhlbjExMTE_size_16_color_FFFFFF_t_70_pic_center]

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

# 解题方法： #

## 方法1：回溯法 ##

思路：重点是要懂得 蓝色线对角线：横坐标+纵坐标 = 常数；  
红色对角线：横坐标 - 纵坐标 = 常数。

我们就可以存储这些常数值，来判断是否要放置皇后的位置是否会被攻击到。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Blbmd4aWFvemhlbjExMTE_size_16_color_FFFFFF_t_70_pic_center 1]

### Java实现 ###

class Solution {
        public List<List<String>> solveNQueens(int n) {
            List<List<String>> res = new ArrayList<>();
            char[][] curr = init(n);
            boolean[] col = new boolean[n];
            boolean[] diag1 = new boolean[2*n-1];
            boolean[] diag2 = new boolean[2*n-1];
            solve(curr, 0, n, col, diag1, diag2, res);
            return res;
        }
        
        public char[][] init(int n) {
            char[][] curr = new char[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    curr[i][j] = '.';
                }
            }
            return curr;
        }
        
        public void solve(char[][] curr,
                          int level, 
                          int n,
                          boolean[] col,
                          boolean[] diag1,
                          boolean[] diag2,
                          List<List<String>> res) {
            // terminator
            if (level == n) {
                List<String> toAdd = new ArrayList<>();
                for (int i = 0; i < n; i++) {
                    // 将每一行的排列转化为字符串保存
                    toAdd.add(String.valueOf(curr[i]));
                }
                res.add(toAdd);
                return;
            }
            
            
            for (int j = 0; j < n; j++) {
                // process current level
                if (col[j] || diag1[level + n - j - 1] || diag2[level + j]) {
                    continue;
                }
                col[j] = true;
                diag1[level + n - j - 1] = true;
                diag2[level + j]  = true;
                curr[level][j] = 'Q';
                solve(curr, level + 1, n, col, diag1, diag2, res);
                // reverse current logic
                col[j] = false;
                diag1[level + n -  j - 1] = false;
                diag2[level + j]  = false;
                curr[level][j] = '.';
            }
        }
    }

[LeetCode 51.]: https://leetcode-cn.com/problems/n-queens/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Blbmd4aWFvemhlbjExMTE_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/3c7500a69d644abba3ac419746e79d30.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Blbmd4aWFvemhlbjExMTE_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/6410b3afb25c452485b26dd7d88b6b4f.png