回溯——51. N皇后——必须攻克的经典回溯难题

简介: 本专栏按照数组—链表—哈希—字符串—栈与队列—二叉树—回溯—贪心—动态规划—单调栈的顺序刷题,采用代码随想录所给的刷题顺序,一个正确的刷题顺序对算法学习是非常重要的,希望对大家有帮助

1 题目描述

按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

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

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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/n-queens

2 题目示例

image.png

示例 2:

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

3 题目提示

1 <= n <= 9

4 思路

「N皇后问题」研究的是如何将N个皇后放置在NxN的棋盘上,并且使皇后彼此之间不能相互攻击。
皇后的走法是:可以横直斜走,格数不限。因此要求皇后彼此之间不能相互攻击,等价于要求任何两个皇后都不能在同一行、同—列以及同—条斜线上。
直观的做法是暴力枚举将N个皇后放置在N×N的棋盘上的所有可能的情况,并对每一种情况判断是否满足皇后彼此之间不相互攻击。暴力枚举的时间复杂度是非常高的,因此必须利用限制条件加以优化。
显然,每个皇后必须位于不同行和不同列,因此将N个皇后放置在N xN的棋盘上,—定是每—行有且仅有一个皇后,每一列有且仅有一个皇后,且任何两个皇后都不能在同—条斜线上。基于上述发现,可以通过回溯的方式寻找可能的解。
回溯的具体做法是:使用一个数组记录每行放置的皇后的列下标,依次在每一行放置一个皇后。每次新放置的皇后都不能和已经放置的皇后之间有攻击:即新放置的皇后不能和任何一个已经放置的皇后在同一列以及同—条斜线上,并更新数组中的当前行的皇后列下标。当N个皇后都放置完毕,则找到一个可能的解。当找到一个可能的解之后,将数组转换成表示棋盘状态的列表,并将该棋盘状态的列表加入返回列表。
由于每个皇后必须位于不同列,因此已经放置的皇后所在的列不能放置别的皇后。第一个皇后有N列可以选择,第二个皇后最多有N―1列可以选择,第三个皇后最多有N-2列可以选择(如果考虑到不能在同一条斜线上,可能的选择数量更少),因此所有可能的情况不会超过N!种,遍历这些情况的时间复杂度是O(N!)。
为了降低总时间复杂度,每次放置皇后时需要快速判断每个位置是否可以放置皇后,显然,最理想的情况是在O(1)的时间内判断该位置所在的列和两条斜线上是否已经有皇后。

为了判断—个位置所在的列和两条斜线上是否已经有皇后,使用三个集合columns、diagonals,和diagonalsg分别记录每一列以及两个方向的每条斜线上是否有皇后。
列的表示法很直观,一共有Ⅳ列,每—列的下标范围从О到N -1,使用列的下标即可明确表示每—列。
如何表示两个方向的斜线呢?对于每个方向的斜线,需要找到斜线上的每个位置的行下标与列下标之间的关系。

方向一的斜线为从左上到右下方向,同—条斜线上的每个位置满足行下标与列下标之差相等,例如(0,0)和(3,3)在同一条方向一的斜线上。因此使用行下标与列下标之差即可明确表示每—条方向一的斜线。
image.png

方向二的斜线为从右上到左下方向,同一条斜线上的每个位置满足行下标与列下标之和相等,例如 (3,0)(3,0) 和 (1,2)(1,2) 在同一条方向二的斜线上。因此使用行下标与列下标之和即可明确表示每一条方向二的斜线。
在这里插入图片描述
每次放置皇后时,对于每个位置判断其是否在三个集合中,如果三个集合都不包含当前位置,则当前位置是可以放置皇后的位置。
复杂度分析

  • 时间复杂度:O(N!),其中N是皇后数量。
  • 空间复杂度:O(N),其中N是皇后数量。空间复杂度主要取决于递归调用层数、记录每行放置的皇后的列下标的数组以及三个集合,递归调用层数不会超过N,数组的长度为N,每个集合的元素个数都不会超过N。

5 我的答案

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<List<String>>();
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        Set<Integer> columns = new HashSet<Integer>();
        Set<Integer> diagonals1 = new HashSet<Integer>();
        Set<Integer> diagonals2 = new HashSet<Integer>();
        backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);
        return solutions;
    }

    public void backtrack(List<List<String>> solutions, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
        if (row == n) {
            List<String> board = generateBoard(queens, n);
            solutions.add(board);
        } else {
            for (int i = 0; i < n; i++) {
                if (columns.contains(i)) {
                    continue;
                }
                int diagonal1 = row - i;
                if (diagonals1.contains(diagonal1)) {
                    continue;
                }
                int diagonal2 = row + i;
                if (diagonals2.contains(diagonal2)) {
                    continue;
                }
                queens[row] = i;
                columns.add(i);
                diagonals1.add(diagonal1);
                diagonals2.add(diagonal2);
                backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);
                queens[row] = -1;
                columns.remove(i);
                diagonals1.remove(diagonal1);
                diagonals2.remove(diagonal2);
            }
        }
    }

    public List<String> generateBoard(int[] queens, int n) {
        List<String> board = new ArrayList<String>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }
}
相关文章
|
6月前
|
算法
【算法沉淀】最长回文子串
【算法沉淀】最长回文子串
|
6月前
|
算法
【错题集-编程题】腐烂的苹果(多源 BFS + 最短路)
【错题集-编程题】腐烂的苹果(多源 BFS + 最短路)
|
4月前
|
存储 算法 Python
Python算法界的秘密武器:分治法巧解难题,贪心算法快速决策,动态规划优化未来!
【7月更文挑战第9天】Python中的分治、贪心和动态规划是三大关键算法。分治法将大问题分解为小问题求解,如归并排序;贪心算法每步选局部最优解,不保证全局最优,如找零钱;动态规划存储子问题解求全局最优,如斐波那契数列。选择合适算法能提升编程效率。
64 1
|
5月前
|
算法 C++
计算机算法设计与分析 第2章 递归与分治策略 (笔记)
计算机算法设计与分析 第2章 递归与分治策略 (笔记)
|
6月前
|
算法 Java 定位技术
【数据结构与算法】递归、回溯、八皇后 一文打尽!
【数据结构与算法】递归、回溯、八皇后 一文打尽!
|
6月前
|
算法
我对双指针算法认知
我对双指针算法认知
快乐学算法or二分查找深度刨析
快乐学算法or二分查找深度刨析
|
机器学习/深度学习 算法 搜索推荐
<<算法很美>>——(二)详解递归思想
<<算法很美>>——(二)详解递归思想
<<算法很美>>——(二)详解递归思想
算法竞赛之查找算法(持续补充...)
算法竞赛之查找算法(持续补充...)