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

回溯法——(2)n皇后问题(C语言讲解)(LeetCode51 N皇后思想)(4皇后棋盘画图举例)(附代码)

目录

一、问题概括

二、算法分析

三、举例(4皇后棋盘)

 四、算法实现 

4.1运行结果:


51. N 皇后 - 力扣(LeetCode)

一、问题概括

        n皇后问题是19世纪著名数学家高斯于1850年提出的。

        问题是:在n×n的棋盘上摆放n个皇后,使其不能相互攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上。

二、算法分析

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

核心分析

        n后问题等价于在n×n格的棋盘上放置n个皇后,任何2个皇后不放在同一行同一列同一斜线上。 

         由以上问题与分析可知,棋盘每一行可以并且必须拜访1个皇后。

        1、那么n皇后问题的可能解用1个n元向量(x1,x2,......,xn)表示,即第i个皇后摆放在第i行第xi列的位置(1≤i≤n且1≤xi≤n)。

        2、由于两个皇后不能位于同一列,所以,n皇后问题的解的向量必须满足约束条件xi≠xj

        3、不在同一斜线上的约束条件|i-j|≠|xi-xj|。

三、举例(4皇后棋盘)

        下面将利用4皇后问题详细讲解。

       (Q代表皇后放置符号,×代表放置失败的符号)

        ①首先把皇后1摆放到所在第一行第一列

        ②皇后2本着不能与皇后1同行同列同斜线的原则 ,经过不懈努力尝试最终放置在了第二行第三列

        ③皇后3根据同样的原理(同行同列同斜线的原则)尝试了第三行的任何一列都冲突。

        ④因此进行回溯,将皇后2摆放到下一个位置, 即皇后2第二行第四列。

         ⑤皇后3再次本着同行同列同斜线的原则,摆放到第三行第二列。

        ⑥

                1、皇后4,摆放到第四行任何一列,都会违背同行同列同斜线的原则,进行回溯;

                2、发现皇后3除了摆放到第三行第二列不违背原则,其他列放置同样违背原则,因此我们继续回溯;

                3、但当我们此时回溯到皇后2时发现皇后2已经位于相应行最后一列了,所以我们只能继续回溯;

                4、回溯到皇后1,将皇后1摆放到第一行第二列。

        ⑦接下来,将皇后2摆放到第二行第四列,皇后3摆放到第三行第一列,皇后4摆放到第四行第三列的位置,便得到了4皇后问题的一个解。

 四、算法实现 

#include <stdio.h>
#include <stdlib.h>#define N 4  // 可以更改 N 的值来解决不同大小的皇后问题
int count = 0;void printBoard(int board[N][N]);// 函数来检查是否可以在 board[row][col] 放置皇后
int isSafe(int board[N][N], int row, int col) {int i, j;// 检查同一列for (i = 0; i < row; i++)if (board[i][col] == 1)return 0;// 检查左上对角线for (i = row, j = col; i >= 0 && j >= 0; i--, j--)if (board[i][j] == 1)return 0;// 检查右上对角线for (i = row, j = col; i >= 0 && j < N; i--, j++)if (board[i][j] == 1)return 0;return 1;
}// 函数来解决 N 皇后问题
void solveNQUtil(int board[N][N], int row, int& solutions) {// 如果所有皇后都放置完成if (row >= N) {solutions++;printBoard(board);return;}// 在当前行尝试放置皇后并递归地放置剩下的皇后for (int col = 0; col < N; col++) {// 检查放置皇后的位置是否安全if (isSafe(board, row, col)) {board[row][col] = 1;  // 放置皇后solveNQUtil(board, row + 1, solutions);  // 递归放置下一个皇后board[row][col] = 0;  // 回溯}}
}// 打印棋盘函数
void printBoard(int board[N][N]) {printf("Solution %d:\n", ++count);for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++)printf("%d ", board[i][j]);printf("\n");}printf("\n");
}// 用于解决 N 皇后问题的主函数
void solveNQ() {int board[N][N] = { 0 };  // 初始化棋盘int solutions = 0;solveNQUtil(board, 0, solutions);printf("Total number of solutions are %d\n", solutions);
}// 主函数
int main() {solveNQ();return 0;
}

4.1运行结果:

         这个代码尝试在棋盘的每一行放置皇后,并使用递归来检查每个位置是否安全。如果找到一个安全的放置位置,就会递归地尝试下一行。这个过程一直重复,直到所有皇后都被放置在棋盘上。每次成功放置所有皇后时,它都会增加解决方案的数量,并打印出当前棋盘作为一个新的解决方案。 


相关文章:

回溯法——(2)n皇后问题(C语言讲解)(LeetCode51 N皇后思想)(4皇后棋盘画图举例)(附代码)

目录 一、问题概括 二、算法分析 三、举例&#xff08;4皇后棋盘&#xff09; 四、算法实现 4.1运行结果&#xff1a; 51. N 皇后 - 力扣&#xff08;LeetCode&#xff09; 一、问题概括 n皇后问题是19世纪著名数学家高斯于1850年提出的。 问题是&#xff1a;在nn的棋盘上…...

数据库系统概论(第5版)复习笔记

笔记的Github仓库地址 &#x1f446;这是笔记的gihub仓库&#xff0c;内容是PDF格式。 因为图片和代码块太多&#xff0c;放到CSDN太麻烦了&#xff08;比较懒&#x1f923;&#xff09; 如果感觉对各位有帮助的话欢迎点一个⭐\^o^/...

数仓领域,Serving 是什么概念?

在数据仓库&#xff08;Data Warehouse&#xff09;和更广泛的数据工程领域中&#xff0c;“Serving”通常指的是将处理和优化后的数据提供给最终用户或应用程序的过程。这包括数据的查询、检索、展示等操作&#xff0c;使得数据能够在决策支持、报告、分析、或机器学习等应用中…...

Python筑基之旅-MySQL数据库(三)

目录 一、数据库操作 1、创建 1-1、用mysql-connector-python库 1-2、用PyMySQL库 1-3、用PeeWee库 1-4、用SQLAlchemy库 2、删除 2-1、用mysql-connector-python库 2-2、用PyMySQL库 2-3、用PeeWee库 2-4、用SQLAlchemy库 二、数据表操作 1、创建 1-1、用mysql-…...

(全面)Nginx格式化插件,Nginx生产工具,Nginx常用命令

目录 &#x1f3ab; 前言 &#x1f389; 开篇福利 &#x1f381; 开篇福利 x2 Double happiness # 介绍 # 地址 # 下载 &#x1f4bb; 命令及解析 # 整个文件系统中搜索名为nginx.conf的文件 # 编辑nginx.conf文件 # 重新加载配置文件 # 快速查找nginx.conf文件并使…...

软考 软件设计师 场景分析题 速成篇

文章目录 试题一&#xff1a;数据流图&#x1f496; 基本图形元素1. 外部实体2. 数据存储3. 加工4. 数据流 &#x1f4da; 例题&#xff08;1&#xff09;实体名称&#xff08;2&#xff09;数据存储名称&#xff08;3&#xff09;数据流① 父子图平衡② 加工有输入有输出④ 数…...

[学习笔记](Python3)防止SQL注入、XSS攻击和文件上传漏洞

学习笔记&#xff1a;防止SQL注入、XSS攻击和文件上传漏洞&#xff08;Python3&#xff09; 本笔记由生成式大模型GPT-4o自动整理。注意AI可能犯错。代码和理论由GPT-4o(2024-5-21)自行撰写未经人工复核。 参数化查询防SQL注入 参数化查询通过将SQL语句和数据分离来防止SQL注…...

西门子CPU与汇川伺服通信与控制

西门子CPU与汇川620F伺服通信与控制 一、西门子CPU与汇川620F伺服通信与控制1、器件准备2、伺服软件设置3、PLC添加汇川伺服描述文件4、PLC编程调试5、总结 二、西门子s7-1500限位信号接到伺服的方法1、通过默认报文获取限位信号2、添加自定义报文获取限位信号3、总结 三、西门…...

移动硬盘无法读取怎么修复?简单八步,轻松搞定!

移动硬盘在日常生活和工作中扮演着重要的角色&#xff0c;但有时我们可能会遇到移动硬盘无法读取的问题。这种情况可能导致数据无法访问&#xff0c;给用户带来一定的困扰。本文将介绍移动硬盘无法读取的可能原因以及针对这些问题的修复方法。 1. 检查硬件连接 当发现移动硬盘…...

c4d云渲染是工程文件会暴露吗?

在数字创意产业飞速发展的今天&#xff0c;C4D云渲染因其高效便捷而备受欢迎。然而&#xff0c;随着技术应用的深入&#xff0c;人们开始关注一个核心问题&#xff1a;在享受云渲染带来的便利的同时&#xff0c;C4D工程文件安全吗&#xff1f;是否会有暴露的风险&#xff1f;下…...

C语言/数据结构——每日一题(有效的括号)

一.前言 如果想要使用C语言来解决这道题——有效的括号&#xff1a;https://leetcode.cn/problems/valid-parentheses/description/我们必须要借用上一篇我们所讲的内容——栈的实现&#xff1a;https://blog.csdn.net/yiqingaa/article/details/138923750?spm1001.2014.3001.…...

STM32使用旋转编码开关

一、旋转编码开关如何工作 编码器内部有一个开槽圆盘&#xff0c;连接到公共接地引脚 C。它还具有两个接触针 A 和 B&#xff0c;如下所示。 当您转动旋钮时&#xff0c;A 和 B 按照特定顺序与公共接地引脚 C 接触&#xff0c;具体顺序取决于转动旋钮的方向。 当它们与公共地接…...

OneMO同行 心级服务:中移物联OneMO模组助力客户终端寒冷环境下的稳定运行

中移物联OneMO模组以客户为中心&#xff0c;基于中国移动心级服务要求&#xff0c;开展“OneMO同行 心级服务 标定一流”高标服务主题活动&#xff0c;升级“服务内容““服务方式”和“服务意识”&#xff0c;为行业客户提供全新的服务体验。 近日&#xff0c;某车载监控设备…...

爬虫视图展示之 Power BI

实现方式 读取数据的实现 selenium 库 requests 库 存储媒介 MysqlElasticSearch 图表展示 GrafanaPower BI 是什么&#xff1f; Power BI 简单且快速&#xff0c;能够从 Excel 电子表格或本地数据库创建快速见解。 同时 Power BI 也可进行丰富的建模和实时分析&#xff…...

微软刚发布的Copilot+PC为什么让Intel和AMD尴尬?2024 AI PC元年——产业布局及前景展望

美国东部时间5月20日在微软位于华盛顿的新园区举行的发布会上&#xff0c;宣布将旗下AI助手Copilot全面融入Windows系统&#xff0c;能够在不调用云数据中心的情况下处理更多人工智能任务。 “将世界作为一个提示词就从Windows系统开始”。微软的新PC将是“CopilotPC”&#xf…...

抖音视频怎么去水印保存部分源码|短视频爬虫提取收集下载工具

抖音视频怎么去水印保存部分源码|短视频爬虫提取收集下载工具 抖音视频去水印保存部分源码&#xff1a; 通过使用Python中的requests、re和os等库&#xff0c;可以编写如下代码来实现抖音视频去水印保存的功能。 短视频爬虫提取手机下载工具的使用方法&#xff1a; 该工具主…...

类的组合、作用域与可见性、类的静态成员、单例模式、

类的组合 一个类内嵌其他类的对象作为成员的情况 has - a组合 初始化列表的另一用途&#xff1a;为了调用数据成员的带参构造函数 能够层层递进 class Line { public:Line(int x1 0, int y1 0, int x2 0, int y2 0);Line(const Line &other);~Line();Line(const Po…...

高速公路定向广播(声光一体) HT-600D

1、产品概述&#xff1a; HT-600D声光一体平面波IP定向广播是北京恒星科通创新性研发产品&#xff0c;采用公司自主研发的平面波传声技术&#xff0c;该产品具有高声压、强指向性、高清晰度等特点&#xff0c;采用定向声传声技术将声音聚集到正前方定向传输,周边声压级明显降低…...

2024离婚新规已生效,不用等30天冷静期,线上开庭

2024年离婚必知的12条法律知识&#xff1a; ✅分居多久都不会自动离婚&#xff0c;想离婚&#xff0c;必需通过协议或起诉程序离婚 ✅婚后的工资收入&#xff0c;继承的遗产(未指定只给一人&#xff09;都是夫妻共同财产 ✅没有领结婚证&#xff0c;或领证后没有共同生活&#…...

从零搭建python环境:深入解析虚拟环境与Python版本管理

新书上架~&#x1f447;全国包邮奥~ python实用小工具开发教程http://pythontoolsteach.com/3 欢迎关注我&#x1f446;&#xff0c;收藏下次不迷路┗|&#xff40;O′|┛ 嗷~~ 目录 一、引言&#xff1a;为何需要虚拟环境&#xff1f; 二、虚拟环境的创建与命名 1. 虚拟环境…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...