【计算机算法设计与分析】n皇后问题(C++_回溯法)
文章目录
- 题目描述
- 测试样例
- 算法原理
- 算法实现
- 参考资料
题目描述
在nxn格的棋盘上放置彼此不受攻击的n格皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nxn格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。
当n=6时,一个如下的 6×6 的跳棋棋盘:
上面的布局可以用序列 2 4 6 1 3 5 来描述,第 i 个数字表示在第 i 行的相应位置有一个棋子。这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。并把它们以上面的序列方法输出,解按字典顺序排列。请输出前三个解。最后一行是解的总个数。
测试样例
输入:
6
输出:
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
算法原理
使用回溯法对解空间进行深度优先搜索遍历,同时要满足规则(任何两个皇后不放在同一行或同一列或同一斜线上),为节省时间我创建了四个数组:x[1000], y[1000], zr[1000], zl[1000],分别存储横轴、纵轴、左对角线、右对角线上是否已被占用的信息。其中,x[i]=j表示在第i行第j个位置放置一个皇后(方便输出结果);y[j]=1表示第j列已被占用;zr[i - j + n]=1表示这条从左上到右下的对角线已被占用(所有处于同一条左上到右下对角线上元素的横坐标减纵坐标都相同,为了让索引为正,所以加n);zl[i+j]=1表示这条从右上到左下的对角线已被占用(所有处于同一条右上到左下对角线上元素的横坐标加纵坐标都相同)。
算法实现
#include<bits/stdc++.h>
using namespace std;int n, num = 0;
int x[1000], y[1000], zr[1000], zl[1000];
void print()
{if (num < 3){for (int i = 1; i <= n; i++)cout << x[i] << " ";cout << endl;}num++;
}
void dfs(int i)
{if (i > n){print();return;}else{for (int j = 1; j <= n; j++){if ((!y[j]) && (!zr[i - j + n]) && (!zl[i + j])){x[i] = j;//i行第j个y[j] = 1;zr[i - j + n] = 1;zl[i + j] = 1;dfs(i + 1);//递归y[j] = 0;zr[i - j + n] = 0;zl[i + j] = 0;}}}
}
int main()
{cin >> n;dfs(1);cout << num;return 0;
}
参考资料
回溯法之n皇后问题总结_用回溯法求解n皇后问题的思路
相关文章:
【计算机算法设计与分析】n皇后问题(C++_回溯法)
文章目录 题目描述测试样例算法原理算法实现参考资料 题目描述 在nxn格的棋盘上放置彼此不受攻击的n格皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nxn格的棋盘上放置n个皇后,任何2个皇后不放在同…...
Calendar日历类型常见方法
Calendar日历类型常见方法: 概括:1.get( )方法2、set( ) 设置时间3、常用的add方法4、after()方法表示的时间是否在指定时间之后, before( ) 方法则之前, 返回判断结果4.1、compareTo比较器 概括: Calendar类是一个抽…...
Docker-Compose部署Redis(v7.2)主从模式
文章目录 一、前提准备1. redis配置文件2. 下载redis镜像3. 文件夹结构 二、docker-compose三、主从配置1.主节点配置文件2.从节点配置文件 四、运行五、测试 环境 docker desktop for windows 4.23.0redis 7.2 一、前提准备 1. redis配置文件 因为Redis 7.2 docker镜像里面…...
Spring国际化的应用及原理详解
1. 简介 Spring国际化(Spring Internationalization,简称i18n)是Spring框架提供的一种机制,用于支持多语言的应用程序。它使得开发者能够轻松地在应用程序中实现不同语言的支持,从而满足全球化的需求。通过Spring国际…...
Existing installation is up to date
这个报错是之前安装的docker没有删除干净 解决方法: 打开注册表编辑器 然后再搜索栏:HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Uninstall\Docker Desktop 回车 找到Docker Desktop文件夹后,右键删除 重新安装Docker…...
windows安装kafka以及kafka管理工具推荐
windows安装 1.下载地址 下载地址 下载最新版本的.tgz文件解压 2.修改配置 修改config目录下的zookeeper.properties中的dataDir属性 server.properties文件中的log.dir属性 3.启动zookeeper 进入到bin\windows\下的用cmd输入zookeeper-server-start.bat ..\..\config\zo…...
面向对象的三大特征之一多态
多态 概念 多态是同一个对象,在不同时刻表现出来不同的形态,称之为多态。 例如:水,我们把水理解成为一个对象,而水会有不同的形态,比如 液态水、冰块、水蒸气 多态的前提 有继承/实现关系(继承…...
vue3中标签form插件
想写一个系统,对八字进行标注,比如格局,有些八字就有很多格局,于是就想着使用el-tag但是,form表单中如何处理呢? 这个时候,就需要自己写一个,modelValue是表单的默认属性 <template><…...
企业数字化转型:1个核心、2种力量、3个关键点、4大转型、5大平台
引言 企业数字化转型源于当今数字化时代的巨大变革。随着科技的飞速发展和全球市场的日益竞争,企业们正面临着前所未有的挑战和机遇。这些挑战包括消费者行为的变化、新技术的涌现以及市场竞争的加剧。在这种环境下,传统的商业模式和运营方式已经不再适…...
Agilent安捷伦E4990A阻抗分析仪20Hz
Agilent安捷伦E4990A阻抗分析仪性能卓越,适用于元器件、半导体和材料测量。它具有宽广的频率范围,从20Hz到120MHz,能够适应各种不同的阻抗测量需求。在宽阻抗范围内,该仪器能够提供出色的0.045%(典型值)基本…...
性能优化-OpenMP概述(一)-宏观全面理解OpenMP
本文旨在从宏观角度来介绍OpenMP的原理、编程模型、以及在各个领域的应用、使用、希望读者能够从本文整体上了解OpenMP。 🎬个人简介:一个全栈工程师的升级之路! 📋个人专栏:高性能(HPC)开发基础…...
Prometheus实战篇:Prometheus监控nginx
准备环境 在此专栏的前几篇文章中已经准备了一台服务器作为我们进行环境的准备.大家也可以通过虚拟机创建俩台服务器,一台作为Prometheus的安装另外一台进行其他软件安装并且进行监控的服务器. 这里我就不赘述nginx的安装教程,相信大家都可以搜到,使用docker或者直接通过安装包…...
JVM加载class文件的原理机制
1、JVM 简介 JVM 是我们Javaer 的最基本功底了,刚开始学Java 的时候,一般都是从“Hello World ”开始的,然后会写个复杂点class ,然后再找一些开源框架,比如Spring ,Hibernate 等等,再然后就开发…...
如何使用CapSolver解决Web爬虫中遇到的CAPTCHA问题
Web爬取是一种强大的技术,用于从网站中提取数据,但经常会遇到一个常见障碍,即CAPTCHA。CAPTCHA是“Completely Automated Public Turing test to tell Computers and Humans Apart”的缩写,旨在防止自动机器人访问网站。然而&…...
杰发科技AC7801——IO模拟IIC注意事项
7801的参考手册没有说清楚 7840说明了用开漏 使用办法...
展台搭建与设计都有哪些思路
1、现代简约 设计理念强调简洁、线条清晰和空间布局,突出产品本身,使展台干净整洁,适合展示高科技、现代化的产品。 2、自然生态 利用植物、木材等自然元素,营造与自然和谐共处的氛围,适合健康、环保、生态产品。 3、品…...
解决mock单元测试中 无法获取实体类xxx对应的表名
错误描述:在执行单元测试时,执行到new Example时抛出异常,提示无法获取实体类xxx对应的表名 Example example new Example(ServeSubscribeRecord.class);Example.Criteria criteria example.createCriteria();criteria.andEqualTo("se…...
arm64虚拟化技术与kvm实现原理分享
文章目录 1 简介2 arm64 虚拟化相关硬件支持2.1 arm64 cpu 虚拟化基本原理及硬件支持2.2 系统寄存器捕获和虚拟寄存器支持2.3 VHE 特性支持2.4 内存虚拟化支持2.5 IO 虚拟化支持2.6 DMA 虚拟化支持2.7 中断虚拟化支持2.8 定时器虚拟化支持 3 arm64 kvm 初始化流程3.1 初始化总体…...
选择 省市区 组件数据 基于vue3 + elment-plus
h5 <el-cascader v-model"form.area" :props"{value: label,label: label }" :options"jsonData" change"handleChange" style"width: 100%;" /> script import jsonData from /utils/city.json; 选完省市区 数据是一…...
了解 nextTick
一. 什么是 nextTick 简单的说,nextTick 方法是在 Vue.js 中常见的一种异步更新 DOM 的机制。它的原理是利用 JavaScript 的事件循环机制以及浏览器的渲染流程来实现延迟执行 DOM 更新操作。 它的出现主要是为了解决 Vue 的异步更新导致的 DOM 更新后的操作问题。…...
C++精进之路(十六)string类和标准模板库
C提供了一组功能强大的库,这些库提供了很多常⻅编程问题的解决方案以及简化其他问题的工具。 string 类为将字符串作为对象来处理提供了一种方便的方法。string 类提供了自动内存管理功能以及众多处 理字符串的方法和函数。例如,这些方法和函数让您能够合…...
【23.12.29期--Redis缓存篇】谈一谈Redis的集群模式
谈一谈Redis的集群模式 ✔️ 谈一谈Redis的集群模式✔️主从模式✔️ 特点✔️Redis主从模式Demo ✔️哨兵模式✔️Redis哨兵模式Demo✔️特点 ✔️Cluster模式✔️Redis Cluster模式Demo✔️特点 ✔️ 谈一谈Redis的集群模式 Redis有三种主要的集群模式,用于在分布…...
【算法挨揍日记】day34——647. 回文子串、5. 最长回文子串
647. 回文子串 647. 回文子串 题目描述: 给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串&am…...
欧科云链研究院:奔赴2024,Web3与AI共振引爆数字时代潘多拉魔盒
出品|欧科云链研究院 2024年,Web3与AI两个数字科技的巅峰碰撞,欧科云链研究院探索AI与Web3的技术融合,与澎湃科技联合发布2024年展望,原标题为《2024年展望:Web3与AI共振引爆可信数字社会》,共…...
【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试之【数学】2023C-素数之积【欧弟算法】全网注释最详细分类最全的华为OD真题题解
文章目录 题目描述与示例题目描述输入描述输出描述示例输入输出说明 解题思路暴力解质数筛 代码PythonJavaC时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 题目描述与示例 题目描述 RSA加密算法在网络安全世界中无处不在,它利用了极大些数因数分解的闲难…...
uniapp路由
1、路由登记 uni-app页面路由为框架统一管理,开发者需要在pages.json里配置每个路由页面的路径及页面样式。 类似小程序在 app.json 中配置页面路由一样。 所以 uni-app 的路由用法与 Vue Router 不同,如仍希望采用 Vue Router 方式管理路由,…...
湖南大学-数据库系统-2023期末考试【原题】
前言 早上11:00考完的考试,下午回来打了三把LOL之后,凭着回忆把题目重现出来了。 在复习的时候刷了15,16,17,18,19,21六年的卷子,感觉题目都差不多,但是难度…...
【Java EE初阶九】多线程案例(线程池)
一、线程池的引入 引入池---->主要是为了提高效率; 最开始,进程可以解决并发编程的问题,但是代价有点大了,于是引入了 “轻量级进程” ---->线程 线程也能解决并发编程的问题,而且线程的开销比进程要小的多&…...
理解 Node.js 中的事件循环
你已经使用 Node.js 一段时间了,构建了一些应用程序,尝试了不同的模块,甚至对异步编程感到很舒适。但是有些事情一直在困扰着你——事件循环(Event Loop)。 如果你像我一样,花费了无数个小时阅读文档和观看…...
Mac 软件出现「意外退出」及「打不开」解决方法
Mac 软件出现「意外退出」及「打不开」解决方法 软件出现意外退出及软件损坏的情况,这是因为苹果删除了TNT的证书,所以大部分TNT破解的Mac软件会出现无法打开,提示意外退出。 终端需先安装Xcode或Apple命令行工具 如未装Xcode可以使用下列命…...
青岛做网站哪家专业/杭州排名优化软件
ajax在实际应用中是要选择同步还是异步 Ajax在网页中最大的一个优点是它可以访问服务器上的信息而不需要重新加载网页。这意味着要检索或是更新信息的某一小个部分的时候,只需要从服务器端传送那一部分需要的信息而不需要重新下载整个网页。Ajax可以通过两种方法访…...
wordpress 多站点模式 帐号是通用的么/软文广告100字
一、源码特点 SSM选房管理系统是一套完善的完整医院类型系统,结合SSM(SpringSpringMVCMyBatis)框架和bootstrap完成本系统,对理解JSP java编程开发语言有帮助系统采用SSM框架(MVC模式开发),系…...
什么是移动网站开发/做推广网络
前言 更换ip地址麻烦 所以做个脚本吧 操作界面 脚本内容 #!/bin/bash # ****************************************************** # 作用:根据主机目前IP地址更换为静态IP,或者手动输入IP地址用于跟换(手动更换要提供网卡名哦)。 # 时间:2…...
上市公司网站建设/百度seo优化教程
1. 线程优先级 现代操作系统中基本上使用时间分片的方式调度线程,通过设置线程优先级,使优先级高的线程获得时间片的次数多于优先级低的线程。 在java 线程中,通过一个整形变量prority来控制优先级,优先级的范围从1~10…...
WordPress调用html/网站优化流程
MySQL面试题-基础1、SQL中文全称结构化查询语言2、SQL语句分类(1)数据查询语言DQL包括select字段名from表名where条件(2)数据操纵语言DML包括Insertupdatedelete(3)数据定义语言DDL包括createalterdroptruncate(4)数据控制语言DCL包括grant(授权)DENY语句(拒绝授权)REVOKE语句(…...
信息推广网站点不开的那种怎么做/免费网站建设制作
站立会议信息:今天组内的成员报告了自己的进度,每个人都汇报了自己所完成的情况,例如系统的登录界面的整天模板、进入登录界面后用户选择的界面以及程序大体数据库的连接,每个人都在努力完成自己那一部分的工作。 站立会议照片: 任…...