【LeetCode热题100】51. N 皇后(回溯)

一.题目要求

按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

二.题目难度

困难

三.输入样例

示例 1:
在这里插入图片描述
输入:n = 4
输出:[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解释:如上图所示,4 皇后问题存在两个不同的解法。

示例 2:
输入:n = 1
输出:[[“Q”]]

提示:
1 <= n <= 9

四.解题思路

N皇后问题在某种程度上可以看作是一种“升维”的全排列问题。在N皇后问题中,我们需要在一个N×N的棋盘上放置N个皇后,使得这些皇后不能相互攻击,即它们不能位于同一行、同一列或同一对角线上。如果我们将每个皇后的位置看作一个决策(即在某行放置一个皇后),那么这个问题就转化为了在每一行选取一个列位置来放置皇后,而且每一列只能选择一次。

全排列与N皇后的联系
全排列:在全排列问题中,我们需要对一个包含N个元素的集合进行排列,每个元素恰好出现一次,顺序可以不同。可以将N个元素的全排列看作是从N个位置中选取N个位置放置这N个元素,每个位置恰好使用一次。

N皇后问题:如果我们将每一行看作是选择的“元素”,将每一列看作是可选择的“位置”,那么在每一行选择一个列位置来放置皇后的过程,与全排列问题中从N个位置中选择位置来放置N个元素的过程相似。每一行选择一个列位置来放置皇后,确保每一列都恰好被选用一次,这就形成了一个排列。不过,N皇后问题还需要满足附加的约束条件——即放置的皇后之间不能互相攻击,这需要检查对角线方向的冲突。

对于升维的理解
将N皇后问题视为一种“升维”的全排列问题,是因为除了需要满足全排列的基本要求(每行放置一个皇后,且每列只能放置一个皇后,形成一个排列)之外,还需要额外满足不在同一对角线上的约束。这个额外的约束条件相当于在传统的全排列问题基础上增加了新的维度的考虑(即对角线的检查),使问题变得更加复杂。

五.代码实现

class Solution {
public:
    bool checkCol(vector<vector<char>>& board, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q')
                return false;
        }
        return true;
    }

    bool checkLT(vector<vector<char>>& board, int row, int col) {
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q')
                return false;
        }
        return true;
    }
    bool checkRT(vector<vector<char>>& board, int row, int col) {
        for (int i = row - 1, j = col + 1; i >= 0 && j < board.size(); i--, j++) {
            if (board[i][j] == 'Q')
                return false;
        }
        return true;
    }

    vector<vector<string>> solveNQueens(int n) {
        vector<vector<char>> board(n, vector<char>(n, '.'));
        vector<vector<string>> ans;
        dfs(ans, board, 0, n);
        return ans;
    }

    void dfs(vector<vector<string>>& ans, vector<vector<char>>& board, int row, int n) 
    {
        if (row == n) 
        {
            vector<string> oneAns;
            for (int i = 0; i < n; i++) 
            {
                string r;
                for (int j = 0; j < n; j++) 
                {
                    r += board[i][j];
                }
                oneAns.push_back(r);
            }
            ans.push_back(oneAns);
        }

        for (int i = 0; i < n; i++) 
        {
            if (checkCol(board, row, i) && checkLT(board, row, i) && checkRT(board, row, i))
            {
                board[row][i] = 'Q';
                dfs(ans, board, row + 1, n);
                board[row][i] = '.';
            }
        }
    }
};

六.题目总结

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/514989.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

渐进式图片解决前端在页面中使用大图,图片体积过大导致页面出现白屏现象

1、演示 可以看到&#xff0c;图片还在拼命加载的时候&#xff0c; 页面上就已经有内容了 2、什么渐进式图片 图片一开始是模糊的&#xff0c;然后逐渐的开始变的清晰。如果页面上有一些大图&#xff0c;如果直接扔给浏览器的话那么图片的传输时间就会比较长&#xff0c;用户就…

fastadmin学习08-查询数据渲染到前端

index.php查询&#xff0c;这个是前台的index.php public function index() {$slideImgs Db::name("slideimg")->where("status",,normal)->limit(5)->order(sort,desc)->select();$productList Db::name("product")->where(…

windows10 上安装 docker

windows 10 上安装 docker 官方目前给的方案是利用 Docker Desktop 来安装 docker 环境 一、安装前准备工作 1.1 检查系统要求 Windows 10 64 位&#xff1a;Home 或 Pro 2004&#xff08;内部版本 19041&#xff09;或更高版本&#xff0c;或者 Enterprise 或 Education 1…

每日一题————P5725 【深基4.习8】求三角形

题目&#xff1a; 题目乍一看非常的简单&#xff0c;属于初学者都会的问题——————————但是实际上呢&#xff0c;有一些小小的坑在里面。 就是三角形的打印。 平常我们在写代码的时候&#xff0c;遇到打印三角形的题&#xff0c;一般简简单单两个for循环搞定 #inclu…

【Clang+LLVM+honggfuzz学习】(二)honggfuzz的安装与试用

书接上篇【ClangLLVMhonggfuzz学习】&#xff08;一&#xff09;LLVM简介、安装和第一个Hello Pass 本篇介绍honggfuzz的安装与简单使用 本文架构&#xff0c;PS:可选择观看哦 前言git安装试用编写测试文件demo.c设置环境变量开始fuzzFuzz-ing疑问 前言 漏洞检测做毕设&#…

【leetcode】 c++ 数字全排列, test ok

1. 问题 2. 思路 3. 代码实现 #if 0 class Solution { private:vector<int> path; // 满足条件的一个结果 vector<vector<int>> res; // 结果集 void backtracking(vector<int> nums, vector<bool> used){// 若path的个数和nums个数相等&…

事件循环(2024 面试题)

答题大纲 先说基本知识点&#xff0c;宏任务、微任务有哪些说事件循环机制过程&#xff0c;边说边画图出来说async/await执行顺序注意&#xff0c;可以把 chrome 的优化&#xff0c;做法其实是违法了规范的&#xff0c;V8 团队的PR这些自信点说出来&#xff0c;显得你很好学&a…

Unsafe类详解

1. Unsafe 概念 Unsafe类位于sun.misc包下&#xff0c;它是java实现高并发的基础&#xff0c;通过它可以执行一些不安全的操作&#xff0c;如像C语言一样直接操作内存资源&#xff0c; 它提供的这些方法增强了java对底层资源的操作能力&#xff0c;但同时也增加了程序出错的风…

typdef:深入理解C语言中typdef关键词的用法

typedef&#xff1a;C语言中的类型重命名关键词 在C语言中&#xff0c;typedef 是一个非常有用的关键词&#xff0c;它允许我们为现有的数据类型定义一个新的名称。这不仅使得代码更加清晰易读&#xff0c;还提高了代码的可维护性。在这篇博客中&#xff0c;我们将深入探讨 ty…

git中对子模块的本地修改、提交和推送远程仓库

场景 当前的某个项目&#xff0c;其使用了另一个项目&#xff0c;我在本地需要对子项目进行修改&#xff0c;并将这些修改提交到github中的子项目和父项目。其实在github中&#xff0c;子项目都是特定的指向子项目的某次提交&#xff0c;因此对于父项目的修改&#xff0c;其实…

Linux-Arm GDB调试(本地和远程)

目录 问题描述 已有coredump 没有coredump 小结 问题描述 Linux本机调试使用GDB非常方便&#xff0c;但嵌入式Linux设备资源有限&#xff0c;通常并没有交叉编译工具&#xff0c;那嵌入式设备上的应用发生问题如何查找问题&#xff1f;通常IDE有远程DEBUG功能&#xff0c;这…

OpenHarmony实战:标准系统移植指南

本文描述了移植一块开发板的通用步骤&#xff0c;和具体芯片相关的详细移植过程无法在此一一列举。后续社区还会陆续发布开发板移植的实例供开发者参考。 定义开发板 本文以移植名为MyProduct的开发板为例讲解移植过程&#xff0c;假定MyProduct是MyProductVendor公司的开发板…

[Arduino学习] ESP8266读取DHT11数字温湿度传感器数据

目录 1、传感器介绍 2、接线 3、DHT.h库 1、传感器介绍 DHT11数字温湿度传感器是一款含有已校准数字信号输出的温湿度复合传感器&#xff0c;是简单环境监测项目的理想选择。 温度分辨率为1C&#xff0c;相对湿度为1&#xff05;。温度范围在0C到50C之间&#xff0c;湿度的测…

自注意力机制详解

视频链接&#xff1a;李宏毅 self-attention讲解上 参考文章&#xff1a;RNN详解      Attention详解      彻底搞懂Attention机制      知乎Transformer详解 传统的编码器解码器架构 一般最简单的编码器-解码器架构都是基于RNN模型的&#xff0c;编码器将输入…

突破校园网限速:使用 iKuai 多拨分流负载均衡(内网带宽限制通用)

文章目录 1. 简介2. iKuai 部署2.1 安装 VMware2.2 安装 iKuai(1) 下载固件(2) 安装 iKuai 虚拟机(3) 配置 iKuai 虚拟机(4) 配置 iKuai(5) 配置多拨分流 2.3 测试速度 1. 简介 由于博主连的内网是限速的&#xff0c;但是不同设备之间的网速却始终差不多&#xff0c;有一天看着…

CSS3新增的语法(三)【2D,3D,过渡,动画】

CSS3新增的语法&#xff08;三&#xff09;【2D,3D,过渡&#xff0c;动画】 10.2D变换10.1. 2D位移10.2. 2D缩放10.3. 2D旋转10.4. 2D扭曲&#xff08;了解&#xff09;10.5. 多重变换10.6. 变换原点 11. 3D变换11.1. 开启3D空间11.2. 设置景深11.3. 透视点位置11.4. 3D 位移11…

R语言中的常用数据结构

目录 R对象的基本类型 R对象的属性 R的数据结构 向量 矩阵 数组 列表 因子 缺失值NA 数据框 R的数据结构总结 R语言可以进行探索性数据分析&#xff0c;统计推断&#xff0c;回归分析&#xff0c;机器学习&#xff0c;数据产品开发 R对象的基本类型 R语言对象有五…

使用OMP复原一维信号(MATLAB)

参考文献 https://github.com/aresmiki/CS-Recovery-Algorithms/tree/master MATLAB代码 %% 含有噪声 % minimize ||x||_1 % subject to: (||Ax-y||_2)^2<eps; % minimize : (||Ax-y||_2)^2lambda*||x||_1 % y传输中可能含噪 yyw % %% clc;clearvars; close all; %% 1.构…

js类型转换

类型转换只有这四种&#xff0c;例如如果要对象转数字&#xff0c;那么就需要先把对象转成原始类型&#xff0c;再从原始类型转到数字。 空数组转原始类型是一个空字符串。空对象转原始类型是[object Object]。 let a {} console.log(a);// NaN //等价于 a->原始 然后原始…

线控悬架系统分析

线控悬架系统分析 附赠自动驾驶学习资料和量产经验&#xff1a;链接 1 线控悬架系统系统发展现状 • 车辆驾乘过程中&#xff0c;操控性和舒适性是两个重要的评价指标&#xff0c;两者很难兼顾&#xff1b; • 线控悬架就是根据路况实际情况自动调节悬架的高度、刚度、阻尼实…