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

深入理解N皇后问题：从DFS到对角线优化

news 来源：原创 2025/6/18 12:19:46

N皇后问题是一个经典的算法问题，要求在N×N的棋盘上放置N个皇后，使得它们互不攻击。本文将全面解析该问题的解法，特别聚焦于DFS算法和对角线优化的数学原理。

问题描述

在N×N的国际象棋棋盘上放置N个皇后，要求：

任意两个皇后不在同一行
任意两个皇后不在同一列
任意两个皇后不在同一对角线

数据结构图解

1. 棋盘表示

char g[N][N];  // 棋盘矩阵
'.' 表示空位

'Q' 表示皇后

示例（n=4初始状态）：
. . . .
. . . .
. . . .
. . . .

2. 冲突检测数组

bool col[N];       // 列占用标记
bool dg[N*2];      // 正对角线占用标记
bool udg[N*2];     // 反对角线占用标记

对角线索引计算：

(0,0) (0,1) (0,2) (0,3)
(1,0) (1,1) (1,2) (1,3)
(2,0) (2,1) (2,2) (2,3)
(3,0) (3,1) (3,2) (3,3)

正对角线(dg)：u + i（行+列）

例如：(1,2)的正对角线索引=1+2=3

我们发现同一个对角线的上的坐标的x,y值相加是相等的，所以我们用dg[u+i]去标记

反对角线(udg)：n - u + i

例如：当n=4时，(1,2)的反对角线索引=4-1+2=5

反对角线，我们此时不能再次使用u+i了

但为了确保索引不重叠，我们使用n - u + i：

当u增加时，n - u减小

当i增加时，i增大

这样确保每条反对角线有唯一索引

实际计算示例（n=4）

坐标计算式索引值
(0,3) 4-0+3=7 7
(1,2) 4-1+2=5 5
(2,1) 4-2+1=3 3
(3,0) 4-3+0=1 1

坐标	计算式	索引值
(0,3)	4-0+3=7	7
(1,2)	4-1+2=5	5
(2,1)	4-2+1=3	3
(3,0)	4-3+0=1	1

算法执行流程图解

DFS递归过程

dfs(0)
├─ 尝试第0行第0列
│  ├─ 放置皇后
│  ├─ dfs(1)
│  │  ├─ 尝试第1行第2列
│  │  │  ├─ 放置皇后
│  │  │  ├─ dfs(2)
│  │  │  │  ├─ (冲突，回溯)
│  │  │  └─ 撤销皇后
│  │  └─ 尝试其他列...
│  └─ 撤销皇后
└─ 尝试第0行第1列├─ 放置皇后├─ dfs(1)│  ├─ 尝试第1行第3列│  │  ├─ 放置皇后│  │  ├─ dfs(2)│  │  │  ├─ 找到解│  │  │  └─ 输出棋盘│  │  └─ 撤销皇后│  └─ 尝试其他列...└─ 撤销皇后

示例解（n=4）

有效解之一：

. Q . .
. . . Q
Q . . .
. . Q .

对应的标记数组状态：

col: [1, 0, 1, 0] (第0、2列被占用)
dg: 索引1、3、4被占用
udg: 索引4、5、6被占用

完整代码

/*DFS			深度优先搜索*/
#include <stdio.h>
#include <stdbool.h>#define N 20int n;				//棋盘的大小(n*n)
char g[N][N];		//模拟棋盘,'.'表示空，'Q'表示皇后
//col表示列是否被占用，dg表示正对角线是否被占用，udg表示反对角线是否被占用
bool col[N], dg[N*2], udg[N*2];		void dfs(int u)	//u表示当前处理的行
{if (u == n)		//所有的行处理完毕,输出解,返回递归{for (int i = 0;i < n;i++)	//puts函数输出字符串,自动换行puts(g[i]);				//在二维数组g[][]中,单使用g[i]表示第i行的所有数据puts("");		//打印空格,隔开不同解return;}//尝试在当前行的每一列放置皇后for(int i = 0;i < n;i++)//检查列,正对角线,反对角线是否冲突if (!col[i] && !dg[u + i] && !udg[n - u + i]){g[u][i] = 'Q';		//防止皇后col[i] = dg[u + i] = udg[n - u + i] = true;		//标记占用dfs(u + 1);			//递归处理下一行col[i] = dg[u + i] = udg[n - u + i] = false;	//回溯,撤销原有的标记g[u][i] = '.';		//恢复棋盘}
}int main()
{scanf("%d", &n);//初始棋盘for (int i = 0;i < n;i++)for (int j = 0;j < n;j++)g[i][j] = '.';//从第0行开始DFSdfs(0);return 0;
}

时间复杂度分析

最坏情况：O(n!)（需要尝试所有可能的排列）
实际由于剪枝（冲突检测），运行效率高于纯暴力搜索

关键点总结

行处理顺序：逐行放置皇后，避免行冲突
冲突检测：
- 列冲突：col[i]
- 正对角线冲突：dg[u+i]
- 反对角线冲突：udg[n-u+i]
回溯机制：递归返回时撤销所有修改

这个算法通过DFS系统地探索所有可能的解空间，同时使用剪枝技术大幅提高效率。

深入理解N皇后问题：从DFS到对角线优化

N皇后问题是一个经典的算法问题，要求在NN的棋盘上放置N个皇后，使得它们互不攻击。本文将全面解析该问题的解法，特别聚焦于DFS算法和对角线优化的数学原理。问题描述在NN的国际象棋棋盘上放置N个皇后，要求： 任意两个…...

编程日记 2025/6/1 19:55:29

1软考系统架构设计师：第一章系统架构概述 - 超简记忆要点、知识体系全解、考点深度解析、真题训练附答案及解析

超简记忆要点一、考试大纲目标：架构设计能力（需求→架构）能力：技术/方法/行业科目：综合（选择）、案例（问答）、论文（论述） 二、架构核心定义…...

编程日记 2025/6/1 17:31:59

MuJoCo 关节角速度记录与可视化，监控机械臂运动状态

视频讲解： MuJoCo 关节角速度记录与可视化，监控机械臂运动状态代码仓库：GitHub - LitchiCheng/mujoco-learning 关节空间的轨迹优化，实际上是对于角速度起到加减速规划的控制，故一般来说具有该效果的速度变化会显得丝…...

编程日记 2025/6/3 17:20:22

如何打包python程序为可执行文件

将 Python 程序打包为可执行文件是一个常见需求，尤其是在希望将应用程序分享给不具备 Python 环境的用户时。以下是使用 PyInstaller 工具将 Python 程序打包为可执行文件的步骤。步骤 1：安装 PyInstaller 如果您还没有安装 PyInstaller，请…...

编程日记 2025/6/2 2:13:18

产销协同是什么？产销协同流程有哪些？

目录一、产销协同是什么 1.从市场需求的角度来看 2.企业内部运营的角度来看 3.从供应链的角度来看二、实现产销协同的八大步骤 1. 市场需求预测 2. 销售计划制定 3. 生产能力评估 4. 生产计划制定 5. 库存管理 6. 信息共享与沟通 7. 订单执行与跟踪 8. 绩效评估…...

编程日记 2025/5/30 6:29:24

SQL 查询进阶：WHERE 子句与连接查询详解

SQL（Structured Query Language）是管理关系型数据库的核心语言，熟练掌握其查询功能对于数据处理至关重要。本文将深入探讨 SQL 中的两个关键概念：WHERE 子句和连接查询。我们将详细讲解 WHERE 子句中的模糊查询、IS NULL、IS NOT …...

编程日记 2025/6/3 18:50:42

【计算机视觉】CV实战项目- DFace: 基于深度学习的高性能人脸识别

图：MTCNN的三阶段网络结构（P-Net、R-Net、O-Net） DFace深度解析：基于深度学习的高性能人脸识别深度解析DFace：基于PyTorch的实时人脸检测与识别系统技术背景与项目概述核心功能与特点实战部署指南环境准备硬件要求软…...

编程日记 2025/5/29 6:15:27

基于Docker、Kubernetes和Jenkins的百节点部署架构图及信息流描述

以下是基于Docker、Kubernetes和Jenkins的百节点部署架构图及信息流描述，使用文本和Mermaid语法表示：架构图（Mermaid语法） #mermaid-svg-WWCAqL1oWjvRywVJ {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-WWCAq…...

编程日记 2025/5/25 9:24:17

百度搜索AI开放计划：让应用连接精准流量的秘诀

引言在人工智能技术深刻改变各行各业的今天，每天都有许多AI应用诞生。然而无论是开发者还是用户依然会感到自己的应用鲜有人使用或是需求没有被充分满足。这种情况正说明了为什么我们需要SEO流量，而一个能够与AI应用直接相关的SEO平台更是呼之欲出。百度…...

编程日记 2025/6/4 7:33:05

Redis数据结构SDS,IntSet,Dict

1.字符串：SDS SDS的底层是C语言编写的构建的一种简单动态字符串简称SDS，是redis比较常见的数据结构。由于以下几种缺点，Redis并没有直接采用C语言的字符串。 1.获取长度需要计算 2.非二进制安全 ：中间不能有 \0，…...

编程日记 2025/6/3 3:21:45

leetcode201.数字范围按位与

找到公共前缀部分，然后后面的部分全0 class Solution {public int rangeBitwiseAnd(int left, int right) {int offset 0;while (left ! right) {offset;left left >> 1;right right >> 1;}return right << offset;} }...

编程日记 2025/5/26 19:57:26

云服务器 —— 公有 IP 与私有 IP

云服务器的公有 IP 和私有 IP 在网络架构中扮演不同的角色，具体用途和区别如下： 目录 1. 公有 IP（Public IP） 作用： 特点： 示例场景： 2. 私有 IP（Private IP） 作用…...

编程日记 2025/6/1 22:45:34

北斗导航｜ Transformer增强BiLSTM网络的GNSS伪距观测量误差探测

在GNSS（全球导航卫星系统）定位中，伪距观测量的误差直接影响定位精度。结合Transformer和LSTM的优势，可以设计一种混合模型以提升误差探测能力。以下是具体的技术实现方案： 1. 模型架构设计 1.1 输入特征设计原始GNSS观测数据：伪距观测值（C/A码、P码）、载波相位、多普…...

编程日记 2025/6/1 14:55:14

0803分页_加载更多-网络ajax请求2-react-仿低代码平台项目

文章目录 1 分页1.1 url与分页参数1.2 分页组件与url1.3 列表页引用分页组件 2 加载更多2.1 状态2.2 触发时机2.3 加载数据2.4优化结语 1 分页 1.1 url与分页参数查询问卷列表接口，添加分页参数： page：当前页码（第几页&#…...

编程日记 2025/6/2 11:26:02

React 与 Vue 的区别：你会选择哪个框架呢

🤍 前端开发工程师、技术日更博主、已过CET6 🍨 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 🕠 牛客高级专题作者、打造专栏《前端面试必备》、《2024面试高频手撕题》、《前端求职突破计划》 🍚 蓝桥云课签约作者、…...

编程日记 2025/5/12 1:40:12

Jmeter如何取JDBC request响应参数作为下一个接口的值？

1、功能参数说明 Variable Name：数据库连接池的名字，需要与JDBC Connection Configuration的Variable Name Bound Pool名字保持一致 Query：填写的sql语句未尾不要加“;” Parameter valus：参数值,对查询条件进行参数化 Paramete…...

编程日记 2025/5/29 1:35:27

【C++】14.容器适配器 | stack | queue | 仿函数 | priority_queue

1. 容器适配器什么是适配器适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。在C中，容器适配器（Container Adapters&…...

编程日记 2025/5/28 3:47:20

论文阅读：2025 arxiv Aligning to What? Limits to RLHF Based Alignment

Aligning to What? Limits to RLHF Based Alignment https://arxiv.org/pdf/2503.09025 https://www.doubao.com/chat/3871529075012866 速览这篇论文主要探讨了强化学习从人类反馈（RLHF）在对齐大型语言模型（LLMs）时的局限性…...

编程日记 2025/6/1 22:30:31

利用Arcgis自己绘制shp文件

1.选择自己想要创建的shp文件的位置我是直接创建在连接文件夹中 2.右键-新建-shp 3.设置名称、要素类型、空间参考 4、点击创建要素 5、右侧选择图层、创建面 6、开始绘制，双击任意位置结束绘制之后可以改一下shp文件的名字...

编程日记 2025/6/4 6:35:43

路由器重分发（OSPF+静态路由）

路由器重分发（OSPF静态路由） 静态路由充当不了翻译官 OSPF路由 OSPF路由需要宣告自己的ip， Router(config)#router ospf 1 Router(config-router)#network 10.10.10.0 0.0.0.255 area 0还要帮静态路由的也宣告一下 Router(config)#ip route…...

编程日记 2025/5/29 6:40:38

KTT入门

Kinetic tournament tree 简称 KTT 下文中全部简写。 KTT 用于解决类以下问题：已知 N N N 条一次函数，求解一段区间内函数最大值。支持修改操作可以修改 x i x_i xi 或者 b i b_i bi 的值。具体做法：我们考虑线段树来维护一个类似 Δ \Delta Δ 的东西，我们令当…...

编程日记 2025/5/29 17:23:31

WPF 上位机开发模板

WPF 上位机开发模板 WPF上位机开发模板，集成了基础操作菜单、海康视觉实时图像界面、串口通讯、网口通讯、主流PLC通讯、数据存储、图片存储、参数配置、权限管理、第三方webapi接口接入、数据追溯与查询等功能。一、项目结构 WpfSupervisor/ ├── Models/ …...

编程日记 2025/6/4 1:31:12

理想星环OS选择NuttX作为MCU侧OS的核心原因分析

文章目录引言一、POSIX兼容性：降低汽车软件迁移成本二、轻量级与模块化：适配MCU资源约束三、硬实时性能：保障车辆控制确定性四、多芯片适配：加速车企供应链灵活性五、安全与可靠性：构建纵深防御体系六、社区与生态&am…...

编程日记 2025/5/31 15:34:06

IP数据报发送和转发的过程

1. 发送端准备数据应用程序（比如浏览器）要发送数据，比如访问一个网站。应用层（HTTP） → 传输层（TCP/UDP） → 网络层（IP）。 IP层负责把数据包打包，加上必要…...

编程日记 2025/5/29 14:10:25

Pinia 详细解析：Vue3 的状态管理利器

一、Pinia 概述 Pinia 是 Vue 3 的官方推荐状态管理库，由 Vue 核心团队维护。它是对 Vuex 的改进和简化，提供了更简洁的 API 和更好的 TypeScript 支持。 Pinia 的核心优势更简单的 API：相比 Vuex 减少了概念和模板代码完美的 TypeScript…...

编程日记 2025/6/3 3:38:01

pytorch python常用指令

一、常用的conda指令创建新的python环境 conda create -n env_name python3.x 查看已有的python环境 conda env list 进入已有的python环境 conda activate env_name 退出当前的python环境 conda deactivate 二、常用的pip指令 pip install -r requirements.txt 根据…...

编程日记 2025/5/29 2:16:50

ubantu18.04（Hadoop3.1.3）之Spark安装和编程实践

说明：本文图片较多，耐心等待加载。（建议用电脑） 注意所有打开的文件都要记得保存。第一步：准备工作本文是在之前Hadoop搭建完集群环境后继续进行的，因此需要读者完成我之前教程的所有操作。以下所有操…...

编程日记 2025/5/29 17:13:53

Ubuntu下安装vsode+qt搭建开发框架(二)

Ubuntu下安装vsode+qt搭建开发框架(二) 上一节介绍了vsode下搭建qt环境，采用的项目构建方式是使用qt官方的qmake工具。然而从qt6之后，官方已经开始推荐使用cmake来构建项目；并且许多项目都是cmake直接构建的，用cmake来构建项目具有可以更方便的融合其他开源项目。一、vs…...

编程日记 2025/6/4 3:22:40

获取房源信息并完成可视化——网络爬虫实战1

房源信息爬虫与可视化分析程序个人程序全网一手，盗卖必究项目介绍本项目是一个基于Python的房源信息爬虫与可视化分析工具，可以爬取链家网的二手房源信息，并对数据进行清洗、分析和可视化展示。通过本工具，用户可以快速了解特…...

编程日记 2025/6/1 10:49:22

css word

介绍 CSS word-spacing 属性，用于指定段字之间的空间，例如： p {word-spacing:30px; }word-spacing属性增加或减少字与字之间的空白。注意： 负值是允许的。浏览器支持表格中的数字表示支持该属性的第一个浏览器版本号。属…...

编程日记 2025/5/29 13:01:33

[mysql]约束(上)

约束道德约束,法律约束,这个约束在表里面是狭义的. 约束广义的,比如数值型你就不能录入’abc’.字符,定义了varchar(15)范围不能超过数量15. 我们这个章节要说的约束是狭义的,是具体的我们设定的约束, 为什么我们需要约束呢我们是为了数据的精确性和可靠性,我们了为了防…...

编程日记 2025/5/31 0:39:21

Eclipse 插件开发 2

Eclipse 插件开发 2 1 插件配置 1 插件配置 <?xml version"1.0" encoding"UTF-8"?> <?eclipse version"3.4"?> <plugin><extension point"org.eclipse.ui.commands"><category id"com.xu.learn.…...

编程日记 2025/5/29 17:11:47

用go从零构建写一个RPC（仿gRPC，tRPC）--- 版本1

希望借助手写这个go的中间件项目，能够理解go语言的特性以及用go写中间件的优势之处，同时也是为了更好的使用和优化公司用到的trpc，并且作者之前也使用过grpc并有一定的兴趣，所以打算从0构建一个rpc系统，对于生产环境已…...

编程日记 2025/6/1 22:58:00

树莓派（Raspberry Pi）入门建议

树莓派（Raspberry Pi）是一个低成本、信用卡大小的微型电脑，它的核心价值在于高度灵活的可编程性和丰富的硬件扩展能力。根据你的兴趣和需求，它可以用来做各种有趣且实用的项目，以下是常见的应用场景和实例：…...

编程日记 2025/6/4 15:34:59

SpringBoot物资管理系统 | JavaWeb项目设计与实现

概述基于JavaWeb技术实现了一套完整的物资管理解决方案。该系统适用于企业、学校、医院等机构，提供高效的物资入库、申报、公告管理等功能，帮助用户实现物资管理的数字化与智能化。主要内容 1. 管理员功能实现 5.1.1 物资管…...

编程日记 2025/6/3 7:56:05

《P1950 长方形》

题目描述小明今天突发奇想，想从一张用过的纸中剪出一个长方形。为了简化问题，小明做出如下规定： （1）这张纸的长宽分别为 n,m。小明将这张纸看成是由nm个格子组成，在剪的时候，只能沿着格子的…...

编程日记 2025/5/31 15:08:48

SpringCloud微服务架构

Spring Cloud是一个广泛使用的微服务框架，它基于Spring Boot构建，旨在帮助开发者构建复杂的分布式系统。Spring Cloud提供了多种工具和库，使得开发人员可以轻松地构建和部署微服务架构。以下是一些关键组件和概念，帮助你理解Sprin…...

编程日记 2025/5/27 12:31:27

网络管理知识点

1.传统网络管理：Web网管方式，CLI方式，基于SNMP集中管理 2.SNMP简单网络管理协议 SNMPV1实现方便，安全性弱 SNMPV2支持更多错误 SNMPV3认证加密，访问控制 3.SNMP，UDP传输效率较高，报文容易丢失…...

编程日记 2025/5/28 3:15:23

【Web应用服务器_Tomcat】二、Tomcat 核心配置与集群搭建

在企业级 Java Web 应用的部署场景中，Tomcat 作为主流的 Servlet 容器和 Web 服务器，其核心配置的优化以及集群搭建对于保障应用的高性能、高可用性至关重要。一、Tomcat 核心配置优化 1.1 server.xml 配置文件解析 Tomcat 的核心配置文件server…...

编程日记 2025/6/3 2:10:24

模板引擎语法-算术运算

模板引擎语法-算术运算文章目录模板引擎语法-算术运算[toc]1.加法运算2.减法运算3.乘法与除法运算4.四则运算5.整除运算在Django框架模板中，没有专门定义关于算术运算的语法。不过，通过一些标签和过滤器的配合使用，可以模拟实现类似“加减…...

编程日记 2025/6/1 3:34:54

MySQL 联合查询教程

MySQL 联合查询教程在 MySQL 中，联合查询用于从多个表中检索数据，常用于关联表中的信息。联合查询（JOIN）通过将两个或更多表根据一定条件连接起来，从而形成一个虚拟的结果集。MySQL 支持多种类型的联合查询&#xff…...

编程日记 2025/6/3 10:40:58

罗技Flow跨电脑控制

Windows 下载适用于 Windows 10 或更高版本的应用程序 macOS 下载适用于 macOS 12 或更高版本的应用程序 Flow 让您可以在两台电脑之间甚至 Windows 和 macOS 之间畅快办公。只需将支持 Flow 的鼠标的光标移动到屏幕边缘即可在电脑和操作系统之间切换。支持 Flow 的键盘会…...

编程日记 2025/6/1 15:42:21

Unity网络编程入门：掌握Netcode for GameObjects实现多人游戏基础(Day 39)

Langchain系列文章目录 01-玩转LangChain：从模型调用到Prompt模板与输出解析的完整指南 02-玩转 LangChain Memory 模块：四种记忆类型详解及应用场景全覆盖 03-全面掌握 LangChain：从核心链条构建到动态任务分配的实战指南 04-玩转 LangChai…...

编程日记 2025/6/4 10:53:36

LeetCode100题

LeetCode100 两数之和遍历数组，以哈希表存数与下标，边存边查，速找和为目标值的两数下标 class Solution {public int[] twoSum(int[] nums, int target) {int[] ansnew int[2];HashMap<Integer,Integer> mapnew HashMap<>();…...

编程日记 2025/6/1 10:28:08

鸿蒙代码@Builder

#代码如下： Entry Component struct CardExample {State title: string "欢迎使用鸿蒙";State content: string "这是一段自定义内容";build() {Column() {this.MyCard({ title: this.title, content: this.content })}.padding(20)}BuilderM…...

编程日记 2025/5/31 3:27:42

Gewechat启动启动报错

Centos7，测试连接时发现这个错误。 [rootxin ~]# curl -i -X POST http://127.0.0.1:2531/v2/api/tools/getTokenId curl: (56) Recv failure: Connection reset by peer 1、删除原容器，重新构建。 docker run -itd \--name gewe \--privileged \-v /ro…...

编程日记 2025/6/2 3:27:49

硅谷甄选41集-71集

第四十三集：完全按照视频敲代码的话会发现左侧顶部tabbar的display:flex失效了，是因为拆分开的子组件里面多了一个div,去掉就好了，vue3不需要再额外包裹元素。因为路径变化了，所以找不到图片的话在前面再加一个…。第四十五集&am…...

编程日记 2025/6/3 22:57:22

PyQt6实例_消息工具_使用与完整代码分享

目录使用每日消息全局查询更新数据库代码数据库表创建代码-数据库相关操作代码-界面与操作逻辑视频使用工具有三个面板：每日消息、全局查询、更新数据库 “每日消息”和“全局查询”，数据源：同花顺7x24小时快讯 “更新…...

编程日记 2025/5/30 13:54:33

docker配置mysql遇到的问题：网络连接超时、启动mysql失败、navicat无法远程连接mysql

目录 1.网络超时方式1. 网络连接问题方式2. Docker镜像源问题方式3.使用国内镜像源 2.启动mysql镜像失败 3.navicat无法远程连接mysql 1.网络超时安装MySQL时出现超时问题，可能由多种原因导致： 方式1. 网络连接问题原因：网络不稳定…...

编程日记 2025/6/1 10:49:23

【虚幻C++笔记】碰撞检测

目录碰撞检测参数详情示例用法碰撞检测显示名称中文名称CSphere Trace By Channel按通道进行球体追踪UKismetSystemLibrary::SphereTraceSingleSphere Trace By Profile按描述文件进行球体追踪UKismetSystemLibrary::SphereTraceSingleByProfileSphere Trace For Objects针…...

编程日记 2025/6/3 15:45:36