当前位置: 首页 > news >正文

LeetCode.51N皇后详解

问题描述

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

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

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

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

n 皇后问题是一个经典的回溯算法问题,其目标是在一个 n×n 的棋盘上放置 n 个皇后,使得这些皇后不能相互攻击。这意味着任何两个皇后不能处在同一行、同一列或同一斜线上。这个问题不仅是计算机科学中的一个重要问题,也是数学和人工智能领域的研究对象,涉及到组合数学、图论、算法设计等多个领域。

解题思路

回溯法的应用

n 皇后问题的核心解法是回溯算法,这是一种通过试错来寻找问题解决方法的算法。当它通过尝试可能的分步解决方案后发现当前解决方案不可能成立(即不能满足问题的约束条件),它会取消上一步甚至是几步的计算,再通过其他的可能的分步解决方案继续尝试。

检查冲突

在 n 皇后问题中,核心的挑战是如何有效地检查“攻击”(冲突)情况。这通常涉及以下检查:

  1. 列冲突:确保在同一列不放置多于一个皇后。
  2. 行冲突:通常通过算法的设计(一行只放置一个皇后)自然避免。
  3. 对角线冲突:需要检查两种对角线——从左上到右下和从左下到右上。这可以通过计算线性方程来实现,例如使用对角线的索引差和和来标识每条对角线。

数据结构的选择

使用数组来追踪哪些位置是被攻击状态是解决问题的关键:

  • 列标记:使用一个大小为 n 的数组来标记哪些列已被占用。
  • 对角线标记:使用两个大小为 2n-1 的数组来标记两组对角线的占用情况。对于每个皇后在 (r, c) 的位置,它会占用第 c 列,第 r+c"/" 方向对角线和第 r-c+n-1"\" 方向对角线。

代码示例

class Solution {
public:std::vector<std::vector<std::string>> solveNQueens(int n) {std::vector<std::vector<std::string>> solutions;std::vector<std::string> board(n, std::string(n, '.'));std::vector<int> cols(n, 0), diag1(2 * n - 1, 0), diag2(2 * n - 1, 0);backtrack(solutions, board, cols, diag1, diag2, 0, n);return solutions;}private:void backtrack(std::vector<std::vector<std::string>>& solutions,std::vector<std::string>& board, std::vector<int>& cols,std::vector<int>& diag1, std::vector<int>& diag2, int row,int n) {if (row == n) {solutions.push_back(board);return;}for (int col = 0; col < n; col++) {if (cols[col] || diag1[row + col] || diag2[row - col + n - 1]) {continue;}board[row][col] = 'Q';cols[col] = diag1[row + col] = diag2[row - col + n - 1] = 1;backtrack(solutions, board, cols, diag1, diag2, row + 1, n);board[row][col] = '.';cols[col] = diag1[row + col] = diag2[row - col + n - 1] = 0;}}
};

扩展

组合数学

n 皇后问题是组合数学的一个实例,特别是在它涉及到排列和组合的计算上。每种有效的解决方案实际上是对 n 个数字的一个排列,每个数字代表皇后在特定行的列位置。

复杂度分析

虽然回溯算法在理论上是一种暴力搜索方法,它的时间复杂度在最坏情况下是指数级的,但通过有效的剪枝,实际的运行时间可以大大减少。这种算法通常是用于解决复杂度较高、解空间庞大的问题。

图论的视角

从图论的角度看,n 皇后问题可以被看作是在 n×n 的图中找到一个安全的顶点集合,其中任意两个顶点都不是相互可达的。这种图的特殊构造使其成为图着色问题的一个变种。

相关文章:

LeetCode.51N皇后详解

问题描述 按照国际象棋的规则&#xff0c;皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上&#xff0c;并且使皇后彼此之间不能相互攻击。 给你一个整数 n &#xff0c;返回所有不同的 n 皇后问题 的解决方案…...

计算机网络之奇偶校验码和CRC冗余校验码

今天我们来看看有关于计算机网络的知识——奇偶校验码和CRC冗余校验码&#xff0c;这两种检测编码的方式相信大家在计算机组成原理当中也有所耳闻&#xff0c;所以今天我就来跟大家分享有关他们的知识。 奇偶校验码 奇偶校验码是通过增加冗余位使得码字中1的个数恒为奇数或偶数…...

二叉树经典OJ练习

个人主页&#xff1a;C忠实粉丝 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 C忠实粉丝 原创 二叉树经典OJ练习 收录于专栏【数据结构初阶】 本专栏旨在分享学习数据结构学习的一点学习笔记&#xff0c;欢迎大家在评论区交流讨论&#x1f48c; 目录 前置说…...

【OpenHarmony4.1 之 U-Boot 2024.07源码深度解析】008 - make distclean 命令解析

【OpenHarmony4.1 之 U-Boot 2024.07源码深度解析】008 - make distclean 命令解析 一、make V=1 distclean 命令解析系列文章汇总:《【OpenHarmony4.1 之 U-Boot 源码深度解析】000 - 文章链接汇总》 本文链接:《【OpenHarmony4.1 之 U-Boot 2024.07源码深度解析】008 - mak…...

QTreeView双击任意列展开

一.效果 二.原理 重点是如何通过其他列的QModelIndex(假设为index),获取第一列的QModelIndex(假设为firstColumnIndex)。代码如下所示: QModelIndex firstColumnIndex = model->index(index.row(), 0, index.parent()); 这里要注意index函数的第三个参数,第三个参…...

Linux入门攻坚——26、Web Service基础知识与httpd配置-2

http协议 URL&#xff1a;Uniform Resource Locator&#xff0c;统一资源定位符 URL方案&#xff1a;scheme&#xff0c;如http://&#xff0c;https:// 服务器地址&#xff1a;IP&#xff1a;port 资源路径&#xff1a; 示例&#xff1a;http://www.test.com:80/bbs/…...

相由心生与事出反常必有妖

从端午节之日生病起&#xff0c;已就医三次&#xff0c;快半个月了。医检的结论是老病复发—— 上呼吸道感染 。原本并无大碍&#xff0c;加之“水不在深&#xff0c;有龙则灵”的张龙医生处方得当&#xff0c;现已病情好转。只是“800727”趁人之危&#xff0c;兴灾乐祸地欲从…...

微信小程序---支付

一、判断是否登录 如果没有登录&#xff0c;走前端登录流程&#xff0c;不再赘述 二、获取订单编号 跟自己的后端商议入参&#xff0c;然后获取订单编号 三、通过订单编号获取wx.requestPayment()需要的参数 获取订单编号再次请求后端接口&#xff0c;拿到wx.requestPayme…...

Git学习2 -- VSCode中的Git

看了下&#xff0c;主要的插件有3个。自带的Source Control。第1个是Gitlens&#xff0c;第2个是Git Graph。第三个还有个git history。 首先是Source Control。界面大概是这样的。 还是挺直观的。在第一栏source control&#xff0c;可以进行基本的git操作。主要的git操作都是…...

VC++支持断点续下或续传的功能

VC使用多线程和Socket实现断点续下 一、断点续下的基本原理&#xff1a; 1.断点续传的理解可以分为两部分&#xff1a;一部分是断点&#xff0c;一部分是续传。断点的由来是在下载过程中&#xff0c;将一个下载文件分成了多个部分&#xff0c;同时进行多个部分一起的下载&…...

机器学习数学原理专题——线性分类模型:损失函数推导新视角——交叉熵

目录 二、从回归到线性分类模型&#xff1a;分类 3.分类模型损失函数推导——极大似然估计法 &#xff08;1&#xff09;二分类损失函数——极大似然估计 &#xff08;2&#xff09;多分类损失函数——极大似然估计 4.模型损失函数推导新视角——交叉熵 &#xff08;1&#x…...

windows和linux路径斜杆转换脚本,打开即用

前言&#xff1a; windows和linux的目录路径斜杆是相反的&#xff0c;在ssh或者其他什么工具在win和ubuntu传文件时候经常需要用到两边的路径&#xff0c;有这个工具就不用手动去修改斜杆反斜杠了。之前有个在线网站&#xff0c;后来挂了&#xff0c;就想着自己搞一个脚本来用。…...

在Android系统中,查看apk安装路径

在Android系统中&#xff0c;应用通常安装在内部存储的特定目录下。要找到已安装应用的路径&#xff0c;可以通过ADB&#xff08;Android Debug Bridge&#xff09;工具来查询。以下是一些步骤和命令&#xff0c;可以帮助你找到应用的安装路径&#xff1a; 使用pm list package…...

管理不到位,活该执行力差?狠抓这4点要素,强化执行力

管理不到位&#xff0c;活该执行力差&#xff1f;狠抓这4点要素&#xff0c;强化执行力 一&#xff1a;强化制度管理 1、权责分明&#xff0c;追责管理 要知道&#xff0c;规章制度其实就是一种“契约”。 在制定制度和规则的时候&#xff0c;民主一点&#xff0c;征求团队成员…...

应届毕业之本科简历制作

因为毕设以及编制岗位面试&#xff0c;最近好久没有更新了&#xff0c;刚好有同学问如何制作简历&#xff0c;我就准备将我自己制作简历的流程分享给各位&#xff0c;到此也算是一个小的结束&#xff0c;拿了工科学位证书毕业去做&#x1f402;&#x1f40e;了。 简历主要包含内…...

SparkOnHive_列转行、行转列生产操作(透视和逆透视)

前言 行专列&#xff0c;列转行是数开不可避免的一步&#xff0c;尤其是在最初接触Hive的时候&#xff0c;看到什么炸裂函数&#xff0c;各种udf&#xff0c;有点发憷&#xff0c;无从下手&#xff0c;时常产生这t怎么搞&#xff0c;我不会啊&#xff1f; 好吧&#xff…...

【人机交互 复习】第2章 Hadoop

一、概念 1.Hadoop 是一个能够对大量数据进行分布式处理的软件框架&#xff0c;并 且是以一种可靠、高效、可伸缩的方式进行处理的&#xff0c; 2.特点&#xff1a; 高可靠性&#xff0c;高效性&#xff0c;高可扩展性&#xff0c;高容错性 运行在Linux平台上&#xff0c;支持…...

国产自研编程语言“仓颉”来了!

在 6.21 召开的华为开发者大会&#xff08;HDC2024&#xff09;上,华为自研的国产编程语言“仓颉”终于对外正式发布了&#xff01; 随着万物互联以及智能时代的到来&#xff0c;软件的形态将发生巨大的变化。一方面&#xff0c;移动应用和移动互联网领域仍然强力驱动人机交互…...

Swarm 集群管理

Swarm 集群管理 简介 Docker Swarm 是 Docker 的集群管理工具。它将 Docker 主机池转变为单个虚拟 Docker 主机。 Docker Swarm 提供了标准的 Docker API&#xff0c;所有任何已经与 Docker 守护程序通信的工具都可以使用 Swarm 轻松地扩展到多个主机。 支持的工具包括但不限…...

从社交网络到元宇宙:Facebook的战略转型

随着科技的迅猛发展和数字化时代的深入&#xff0c;社交网络已不再局限于简单的信息交流和社交互动&#xff0c;而是逐步向更广阔、更深远的虚拟现实空间——元宇宙&#xff08;Metaverse&#xff09;转变。作为全球最大的社交网络平台之一&#xff0c;Facebook正在积极推动这一…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...

适应性Java用于现代 API:REST、GraphQL 和事件驱动

在快速发展的软件开发领域&#xff0c;REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名&#xff0c;不断适应这些现代范式的需求。随着不断发展的生态系统&#xff0c;Java 在现代 API 方…...

深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏

一、引言 在深度学习中&#xff0c;我们训练出的神经网络往往非常庞大&#xff08;比如像 ResNet、YOLOv8、Vision Transformer&#xff09;&#xff0c;虽然精度很高&#xff0c;但“太重”了&#xff0c;运行起来很慢&#xff0c;占用内存大&#xff0c;不适合部署到手机、摄…...

SQL Server 触发器调用存储过程实现发送 HTTP 请求

文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...

恶补电源:1.电桥

一、元器件的选择 搜索并选择电桥&#xff0c;再multisim中选择FWB&#xff0c;就有各种型号的电桥: 电桥是用来干嘛的呢&#xff1f; 它是一个由四个二极管搭成的“桥梁”形状的电路&#xff0c;用来把交流电&#xff08;AC&#xff09;变成直流电&#xff08;DC&#xff09;。…...