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;
            }
        }
    }
}