【LeetCode】回溯问题：N 皇后问题

小鱼儿 2022-10-29 09:13 222阅读 0赞

### N 皇后 ###

#### [51. N 皇后][51. N] ####

难度困难745收藏分享切换为英文接收动态反馈

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

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

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

**示例 1：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70]

输入：n = 4
    输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
    解释：如上图所示，4 皇后问题存在两个不同的解法。

**示例 2：**

输入：n = 1
    输出：[["Q"]]

**题解**

*  难点在于怎么判断对角线不可以重复

class Solution { 
        public List<List<String>> solveNQueens(int n) { 
            boolean[] col = new boolean[n];
            boolean[] leftDiagonal = new boolean[2 * n - 1];
            boolean[] rightDiagonal = new boolean[2 * n - 1];
    
            int[] record  = new int[n];
            List<List<String>> res = new ArrayList<>();
    
            func(0 , n , col , leftDiagonal , rightDiagonal , record , res);
            return res;
        }
        
        void func(int idx , int n , boolean[] col , boolean[] leftDiagonal , boolean[] rightDiagonal , int[] record , List<List<String>> res){ 
            if(idx == n){ 
                List<String> l = new ArrayList<>();
                for(int i = 0; i < n ; i ++){ 
                    String s ="";
                    for(int j = 0 ; j < n ; j ++){ 
                        s = s + (record[i] == j ? "Q" : ".");
                    }
                    l.add(s);
                }
                res.add(l);
                return;
            }
    
            for(int i = 0 ; i < n ; i ++){ 
                if(! col[i] && ! leftDiagonal[idx - i + n - 1] && ! rightDiagonal[idx + i]){ 
                    col[i] = true;
                    leftDiagonal[idx - i + n - 1] = true;
                    rightDiagonal[idx + i] = true;
    
                    record[idx] = i;
                    func(idx + 1 , n , col , leftDiagonal , rightDiagonal , record , res);
                    record[idx] = i;
                    
                    col[i] = false;
                    leftDiagonal[idx - i + n - 1] = false;
                    rightDiagonal[idx + i] = false;
                }
            }
        }
    }

#### [52. N皇后 II][52. N_ II] ####

难度困难233收藏分享切换为英文接收动态反馈

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

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

**示例 1：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 1]

输入：n = 4
    输出：2
    解释：如上图所示，4 皇后问题存在两个不同的解法。

**示例 2：**

输入：n = 1
    输出：1

\*\*题解 \*\*

class Solution { 
        public int totalNQueens(int n) { 
            boolean[] col = new boolean[n];
            boolean[] leftDiagonal = new boolean[2 * n - 1];
            boolean[] rightDiagonal = new boolean[2 * n - 1];
    
            return func(0 , n , col , leftDiagonal , rightDiagonal);
        }
    
        int func(int idx , int n , boolean[] col , boolean[] left , boolean[] right){ 
            if(idx == n){ 
                return 1;
            }
    
            int res = 0;
            for(int i = 0 ; i < n ; i ++){ 
                if(! col[i] && ! left[idx - i + n - 1] && ! right[idx + i]){ 
                    col[i] = true;
                    left[idx - i + n - 1] = true;
                    right[idx + i] = true;
    
                    res += func(idx + 1 , n , col , left , right);
    
                    col[i] = false;
                    left[idx - i + n - 1] = false;
                    right[idx + i] = false;
                }
            }
    
            return res;
        }
    }

[51. N]: https://leetcode-cn.com/problems/n-queens/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70]: /images/20221024/c030c7904ce249f2b12d8c9f31b598ba.png
[52. N_ II]: https://leetcode-cn.com/problems/n-queens-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 1]: /images/20221024/3d51cb25398a428d84a2ae57f286d42e.png