leetcode51.N 皇后 回溯算法求解 + 效率优化

发布于:2025-03-14 ⋅ 阅读:(13) ⋅ 点赞:(0)

🎯 这篇文章探讨了解决经典N皇后问题的方法,采用回溯算法在标准棋盘上放置皇后,确保它们之间不能相互攻击。文中首先介绍了基本的思路和实现方式,通过递归尝试每个可能的位置并回退错误选择。为了提升效率,进一步提出了优化策略,包括使用额外的数组来标记已占用的列和斜线,避免重复检查。文章详细解释了如何利用这些技术减少时间复杂度,并给出了完整的Java代码实现,展示了从初步方案到性能优化的全过程。

📖 N 皇后 📖

https://leetcode.cn/problems/n-queens/description/

在这里插入图片描述

初步方案

思路

从第一行开始,尝试在该行的每一列放置皇后。

在这里插入图片描述

递归搜索到下一行,尝试在每一列放置皇后,并判断所放置位置是否与同一列或同一斜线的皇后互相攻击。下图中标有 X 的布局,说明皇后之间互相攻击

在这里插入图片描述

对于皇后之间没有互相攻击的布局,继续递归在下一行放置皇后

在这里插入图片描述

当所有行都搜索过,结束搜索

🧑‍💻代码实现🧑‍💻

  • 先初始化一个由 '.' 构成的棋盘
  • 后续递归填充每一行的格子时,遍历该行的所有列,将对应列的格子设置为 'Q' ,然后继续递归搜索到下一行
  • 下一行搜索结束,回到当前行,将当前行当前列的'Q'回退为'.',然后尝试下一列
  • 搜索过程中,一旦能遍历完所有行,就记录结果
public List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    // 初始化棋盘
    char[][] chessboard = new char[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(chessboard[i], '.');
    }
    backtrack(result, chessboard, 0, n);
    return result;
}

private void backtrack(List<List<String>> result, char[][] chessboard, int layer, int n) {
    if (layer == n) {
        // --for-- 遍历到最后一行了,保存结果就结束
        List<String> path = new ArrayList<>();
        for (int i = 0; i < chessboard.length; i++) {
            path.add(new String(chessboard[i]));
        }
        result.add(path);
    }
    for (int j = 0; j < n; j++) {
        // --for-- 遍历棋盘中当前行的每一列
        boolean isCanPlace = true;
        if (layer > 0) {
            // --if-- 如果是第二行以上,需要判断上面行有没有皇后排斥。第一行不需要看
            for (int i = 0; i < layer; i++) {
                // 判断同列是否有皇后
                if (chessboard[i][j] == 'Q') {
                    isCanPlace = false;
                    break;
                }
                // 判断斜对角是否有皇后
                if (((j - (layer - i)) >= 0 && chessboard[i][j - (layer - i)] == 'Q') ||
                        (j + (layer - i) < n && chessboard[i][j + (layer - i)] == 'Q')) {
                    isCanPlace = false;
                    break;
                }
            }
        }
        if (isCanPlace == true) {
            // --if-- 当前位置可以放皇后
            chessboard[layer][j] = 'Q';
            backtrack(result, chessboard, layer + 1, n);
            chessboard[layer][j] = '.';
        }
    }
}

在这里插入图片描述

代码简化

public List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    // 使用char数组,方便后面转化为字符串
    char[][] path = new char[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(path[i], '.');
    }
    backtrack(result, path, 0, n);
    return result;
}

private void backtrack(List<List<String>> result, char[][] path, int row, int n) {
    if (row == n) {
        List<String> temp = new ArrayList<>(n);
        for (int i = 0; i < path.length; i++) {
            temp.add(new String(path[i]));
        }
        result.add(temp);
    }

    for (int j = 0; j < n; j++) {
        // 检测当前列、同一斜线是否有皇后
        boolean flag = false;
        for (int i = 0; i < row; i++) {
            if (path[i][j] == 'Q'// 检测竖线
                    || (j + row - i < n && path[i][j + row - i] == 'Q')// 检测左下-右上斜线
                    || (j - row + i >= 0 && path[i][j - row + i] == 'Q')// 检测又下-左上斜线
            ) {
                flag = true;
                break;
            }
        }
        if (flag) continue;
        path[row][j] = 'Q';
        backtrack(result, path, row + 1, n);
        path[row][j] = '.';
    }
}

在这里插入图片描述

性能优化

优化思路

上面的实现中,在放置皇后之前,需要遍历之前的行,检查前面的行是否有同列、同斜线的皇后与当前皇后相互攻击,这个过程性能较差,可以优化

比如对同列皇后的判断,其实可以在搜索之前先创建一个长度为 n 的数组 usedColusedCol[j] 表示第 j 列是否有皇后,后续在搜索第 j 列时,如果判断usedCol[j]为 true ,则说明该列已经有皇后,跳过当前列,尝试下一列

对列的判断容易优化,那斜线要怎么判断?

首先看 45 度斜线,如下图所示,相同颜色的格子表示处于同一斜线,这些处于同一 45° 斜线的格子,它们的行索引+列索引都是一个相等的值。例如 n = 4 的棋盘,值行索引 + 列索引从左上角到右下角依次从 0 变化到 6 ,那么我们只需要创建一个数组来表示每一斜线上是否有皇后即可,数组的长度为 2 * n - 1

在这里插入图片描述

再看 135 度斜线,如下图所示。每一条 135 度斜线的行索引 - 列索引也是一个定值,虽然有的定值是负数,但是我们可以通过将行索引 - 列索引添加n - 1,将其转化为正值,该值从右上角到左下角依次从 0 变化到 6,因此也可以创建一个数组来表示每一 135 度斜线上是否有皇后,数组的长度为 2 * n - 1

在这里插入图片描述

其实这个思路就是用空间换时间,通过使用数组,减少后面的循环判断用时

🧑‍💻代码实现🧑‍💻

public List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    // 使用char数组,方便后面转化为字符串
    char[][] path = new char[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(path[i], '.');
    }
    // 用来标记每一列是否有皇后
    boolean[] usedCol = new boolean[n];
    // 用来标记每一条 45 度斜线是否有皇后
    boolean[] usedDiag45 = new boolean[2 * n - 1];
    // 用来标记每一条 135 度斜线是否有皇后
    boolean[] usedDiag135 = new boolean[2 * n - 1];
    backtrack(result, path, 0, n, usedCol, usedDiag45, usedDiag135);
    return result;
}

private void backtrack(List<List<String>> result, char[][] path, int row, int n, boolean[] usedCol, boolean[] usedDiag45, boolean[] usedDiag135) {
    if (row == n) {
        List<String> temp = new ArrayList<>(n);
        for (int i = 0; i < path.length; i++) {
            temp.add(new String(path[i]));
        }
        result.add(temp);
        return;
    }

    for (int col = 0; col < n; col++) {
        // 检测当前列、同一斜线是否有皇后
        if (usedCol[col] || usedDiag45[row + col] || usedDiag135[row - col + n - 1]) {
            continue;
        }
        // 标记列、45斜线、135斜线已有皇后
        usedCol[col] = true;
        usedDiag45[row + col] = true;
        usedDiag135[row - col + n - 1] = true;
        path[row][col] = 'Q';
        backtrack(result, path, row + 1, n, usedCol, usedDiag45, usedDiag135);
        // 取消标记列、45斜线、135斜线的皇后
        usedCol[col] = false;
        usedDiag45[row + col] = false;
        usedDiag135[row - col + n - 1] = false;
        path[row][col] = '.';
    }
}

在这里插入图片描述

经过优化,算法效率确实有显著的改进


网站公告

今日签到

点亮在社区的每一天
去签到