N 皇后问题的算法原理及实现 【新手详解 回溯】

引言

N 皇后问题是一个经典的回溯算法问题，基本上不管是打算法还是学数据结构的同学们肯定都写过至少听说过这题，n 皇后问题是在一个 N×N 的棋盘上放置 N 个皇后，使得任意两个皇后都不能在同一行、同一列或同一条对角线上。这里将详细介绍 N 皇后问题的算法原理，并通过 Java 代码示例来展示如何实现这一算法。

---

1. 问题描述

51. N 皇后 - 力扣（LeetCode）

给定一个整数 n，返回所有不同的解决方案，每种方案中 n 个皇后在 n × n 的棋盘上放置，且不能互相攻击。

• 每个解决方案包含一个明确的 n × n 棋盘布局。
• 'Q' 表示皇后，. 表示空位。

---

2. 算法原理

2.1 回溯算法

回溯算法是一种通过递归来解决问题的方法，它尝试所有可能的候选解，并在发现不符合条件时回退（撤销之前的决策），继续尝试其他可能的解。N 皇后问题非常适合使用回溯算法，因为我们需要尝试所有可能的位置来放置皇后，并在发现冲突时进行剪枝。

2.2 剪枝优化⭐⭐⭐

这里可以无脑对每个放置的皇后的位置的横纵对角线遍历是否已经有其他皇后，但是这样遍历的效率太低了，虽然leetcode 还是能过。

为了提高效率，我们可以利用以下剪枝优化：

• 列检查：使用一个布尔数组 CheckCol 来记录每一列是否已经放置了皇后。
• 正对角线检查：使用一个布尔数组 dig1 来记录从左下到右上的每条对角线是否已经放置了皇后。
• 反对角线检查：使用一个布尔数组 dig2 来记录从左上到右下的每条对角线是否已经放置了皇后。

通过这些剪枝优化，我们可以快速判断当前格子是否可以放置皇后，从而避免无效的递归调用。

---

3. 代码实现

public class Solution {
    boolean[] CheckCol, dig1, dig2;
    char[][] path;
    List<List<String>> ret;
    int n;

    public List<List<String>> solveNQueens(int _n) {
        // 初始化变量
        n = _n;    
        CheckCol = new boolean[n];
        dig1 = new boolean[2 * n];
        dig2 = new boolean[2 * n];
        path = new char[n][n];
        ret = new ArrayList<>();
        
        // 初始化棋盘
        for (int i = 0; i < n; i++) {
            Arrays.fill(path[i], '.');
        }
        
        // 从第 0 行开始进行深度优先搜索
        dfs(0);
        
        return ret;
    }

    private void dfs(int row) {
        if (row == n) {
            // 找到一个解决方案
            List<String> tmp = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                tmp.add(new String(path[i]));
            }
            ret.add(tmp);
            return;
        }
        
        for (int col = 0; col < n; col++) {
            // 检查当前位置是否可以放置皇后
            if (!CheckCol[col] && !dig1[row - col + n] && !dig2[row + col]) {
                // 放置皇后
                path[row][col] = 'Q';
                CheckCol[col] = true;
                dig1[row - col + n] = true;
                dig2[row + col] = true;
                
                // 递归处理下一行
                dfs(row + 1);
                
                // 回溯，撤销之前的操作
                path[row][col] = '.';
                CheckCol[col] = false;
                dig1[row - col + n] = false;
                dig2[row + col] = false;
            }
        }
    }
}

---

4. 代码详解

4.1 变量初始化

• CheckCol：用于记录每一列是否已经放置了皇后。
• dig1 和 dig2：分别用于记录两条对角线是否已经放置了皇后。
• path：表示当前的棋盘状态。
• ret：存储所有的解决方案。
• n：表示棋盘的大小。

4.2 初始化棋盘

• 使用 Arrays.fill 方法将棋盘中的每个格子初始化为 .。

4.3 深度优先搜索 (DFS

• 从第 0 行开始，逐行尝试放置皇后。
• 对于每一行，遍历每一列，检查当前位置是否可以放置皇后。
• 如果可以放置皇后，则更新棋盘状态和相关标志，并递归处理下一行。
• 如果到达最后一行并成功放置皇后，则记录当前解决方案。
• 递归结束后，回溯撤销之前的操作，继续尝试其他可能的位置。

5. 总结

其实很早之前就写过这道题了，这次重刷算法的时候又遇见了，就写篇博客啦。这里只介绍回溯法。有问题评论区dd，感谢阅览！

原文地址：https://blog.csdn.net/Y_1215/article/details/142618187

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！