LeetCode_回溯_困难_52.N皇后 II

柔情只为你懂 2023-10-06 19:14 15阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。  
给你一个整数 n ，**返回 n 皇后问题不同的解决方案的数量**。

**示例 1：**  
![在这里插入图片描述][a27b3082ba204b9283baeecf02f6a69f.png]

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

**示例 2：**  
输入：n = 1  
输出：1

**提示：**  
1 <= n <= 9  
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/n-queens-ii

## 2.思路 ##

（1）回溯算法  
在解决此问题之前，可以先弄懂 [LeetCode\_回溯\_困难\_51.N 皇后][LeetCode_51.N] 这题，本题是该题的变形，所求结果由具体的解决方案变成了 n 皇后问题不同的解决方案的数量，所以只需稍微修改该题思路1的代码。具体的做法如下：即每当找到一种解决方案时，全局变量 res 自增，最后当回溯结束后，再返回 res 即可。

相关题目：  
[LeetCode\_回溯\_困难\_51.N 皇后][LeetCode_51.N]

## 3.代码实现（Java） ##

//思路1————回溯算法
    class Solution {
        
        int res = 0;
    
        public int totalNQueens(int n) {
        
            // queens[t] 表示第 t 个皇后放在棋盘的第 t 行的第 queens[t] 列 (0 ≤ t < n)
            int[] queens = new int[n];
            backtrack(queens, 0);
            return res;
        }
    
        public void backtrack(int[] queens, int t) {
        
            int n = queens.length;
            if (t == n) {
        
                res++;
                return;
            }
            for (int i = 0; i < n; i++) {
        
                //将第 t 个皇后放在棋盘的第 t 行的第 queens[t] 列
                queens[t] = i;
                //判断第 t 个皇后能不能放在当前位置
                if (check(queens, t)) {
        
                    //如果能够放在当前位置，则开始判断下一个皇后
                    backtrack(queens, t + 1);
                }
            }
        }
    
        //在一行只放一个皇后的前提下，判断第 k 个皇后能否放在当前位置
        public boolean check(int[] queens, int t) {
        
            //判断当前第 t 个皇后是否与前 0 ~ t - 1 行的皇后能相互攻击
            for (int i = 0; i < t; i++) {
        
                /*
                    Math.abs(t - i) == Math.abs(queens[i] - queens[t]): 判断当前第 t 个皇后是否之前的第 i 个皇后在同一斜线上
                    x[t] == x[i]: 判断当前第 i 个皇后是否之前的第 t 个皇后在同一纵行上
                */
                if (Math.abs(t - i) == Math.abs(queens[i] - queens[t]) || queens[i] == queens[t]) {
        
                    return false;
                }
            }
            return true;
        }
    }

[a27b3082ba204b9283baeecf02f6a69f.png]: https://img-blog.csdnimg.cn/a27b3082ba204b9283baeecf02f6a69f.png
[LeetCode_51.N]: https://blog.csdn.net/weixin_43004044/article/details/119709366