技术标签: 算法
问题描述:国际象棋里,棋盘为8×8格。皇后每步可以沿直线、斜线走任意格。假设将8个皇后放到国际象棋盘上,使其两两之间无法相互攻击,共有几种摆法?
代码如下:
#include <stdio.h>
int Queenes[8]={
0},Counts=0;
int Check(int line,int list){
//遍历该行之前的所有行
int index;
for (index=0; index<line; index++) {
//挨个取出前面行中皇后所在位置的列坐标
int data=Queenes[index];
//如果在同一列,该位置不能放
if (list==data){
return 0;
}
//如果当前位置的斜上方有皇后,在一条斜线上,也不行
if ((index+data)==(line+list)){
return 0;
}
//如果当前位置的斜下方有皇后,在一条斜线上,也不行
if ((index-data)==(line-list)){
return 0;
}
}
//如果以上情况都不是,当前位置就可以放皇后
return 1;
}
//输出语句
void print()
{
int line;
for (line = 0; line < 8; line++)
{
int list;
for (list = 0; list < Queenes[line]; list++)
printf("0");
printf("#");
for (list = Queenes[line] + 1; list < 8; list++){
printf("0");
}
printf("\n");
}
printf("================\n");
}
void eight_queen(int line){
int list;
//在数组中为0~7列
for (list=0; list<8; list++) {
//对于固定的行列,检查是否和之前的皇后位置冲突
if (Check(line, list)) {
//不冲突,以行为下标的数组位置记录列数
Queenes[line]=list;
//如果最后一样也不冲突,证明为一个正确的摆法
if (line==7) {
//统计摆法的Counts加1
Counts++;
//输出这个摆法
print();
//每次成功,都要将数组重归为0
Queenes[line]=0;
return;
}
//继续判断下一样皇后的摆法,递归
eight_queen(line+1);
//不管成功失败,该位置都要重新归0,以便重复使用
Queenes[line]=0;
}
}
}
int main() {
//调用回溯函数,参数0表示从棋盘的第一行开始判断
eight_queen(0);
printf("摆放的方式有%d种",Counts);
return 0;
}
Queenes[]
来表示棋盘上皇后的位置,数组的下标代表行号,值代表列号。变量Counts
用于记录找到的正确摆放方式数量。Check
): 对于给定的行line
和列list
,判断当前位置是否可以放置皇后。通过遍历之前所有行的皇后位置,比较是否存在在同一列、同一斜线的情况,若存在则返回0(不可放),否则返回1(可放)。eight_queen
): 逐行尝试每一列的位置,对于当前行的每一列,使用Check
函数检查是否可以放置皇后,如果可以,则记录位置并递归地尝试放置下一行的皇后。如果到达最后一行且成功放置,增加解的计数并打印当前棋盘布局。无论成功与否,离开当前位置时需重置该位置,以便其它尝试使用。print
): 打印当前棋盘的一个解。使用‘#’表示皇后位置,‘0’代表空位。为了更具体地解释代码执行过程,我们将逐步走过前几个步骤的详细例子。注意,因为八皇后问题有92种解法,这里只展示找到第一个解的过程。假设我们开始时棋盘为空,目标是放置8个皇后到棋盘上,使得它们互不攻击。
plaintextCopy棋盘为空,Counts=0。
Queenes 数组初始化为 [0,0,0,0,0,0,0,0]。
我们从第一行(line=0)开始,尝试在第一列(list=0)放置皇后。
plaintextCopy检查位置 (0,0) 是否合法:通过 Check 函数检查,无冲突,故可以放置皇后。
更新 Queens 数组为 [0,...];实际上皇后已经放在第一行第一列,但由于数组下标和值都是从0开始计数,看起来像没有变化。
接着进入递归处理第二行。
现在,我们尝试在第二行放置皇后。根据算法,我们从第一列开始尝试每个位置直到找到一个合适的。
plaintextCopy第一次尝试位置 (1,0):失败,因为与第一行的皇后在同一列。
第二次尝试位置 (1,1):失败,因为与第一行的皇后在对角线上。
尝试位置 (1,2):成功,无冲突。
更新 Queens 数组为 [0,2,...]。
接着递归处理第三行。
接下来,尝试在第三行放置皇后。
plaintextCopy尝试位置 (2,0):失败,因为与第一行的皇后在同一列。
尝试位置 (2,1):失败,因为与第二行的皇后在对角线上。
尝试位置 (2,2):失败,因为与第一行的皇后在对角线上。
尝试位置 (2,3):成功,无冲突。
更新 Queens 数组为 [0,2,3,...]。
接着递归处理第四行。
按照上述过程继续尝试放置剩余的皇后。
这个过程中,我们会遇到需要回溯的情况,即当前行所有列都尝试过后仍然找不到合适的位置放置皇后。这时,算法会回到上一行,改变上一个皇后的位置,然后再次尝试。
最终,当递归函数成功放置了第八个皇后,并且没有冲突时,我们找到了第一个解,并且Counts
增加1,然后打印当前棋盘布局。
例如,其中一个可能的正确放置方式(不一定是第一种找到的)是Queenes
数组为 [0, 4, 7, 5, 2, 6, 1, 3]
,表示:
本例所述的步骤和对应的Queenes
数组值可能并不代表真实运行程序时的首次找到的解或者实际的执行顺序,因为全过程涉及大量尝试和回溯操作。
让我们以更细节化的方式通过一个具体数值的示例来演示如何逐步执行代码,特别关注Check
函数的执行。为了清晰起见,我们将从尝试放置第一个皇后开始,并展示前几步的详细过程。
Queenes
数组初始化为 [0, 0, 0, 0, 0, 0, 0, 0]
,表示棋盘上还没有皇后被放置。Counts
初始化为0
,表示还没有找到任何合法的摆放方式。line = 0
, list = 0
)。
Check(0, 0)
:由于这是第一个皇后,之前没有皇后被放置,所以无需检查冲突,直接返回1(表示可以放置)。Queenes
数组为 [0, ...,]
,实际上位置没变因为是从0开始计数的。尝试将第二个皇后放在第二行第一列(即line = 1
, list = 0
)。
执行
Check(1, 0)
Queenes[0] == 0
且list == 0
,说明在同一列,返回0(不可放置)。尝试第二行第二列(line = 1
, list = 1
)。
执行
Check(1, 1)
list == Queenes[0]
(列冲突),不成立。(index + Queenes[index]) == (line + list)
(主对角线冲突),即0 + 0 == 1 + 1
,条件不成立,不冲突,不成立。(index - Queenes[index]) == (line - list)
(主对角线冲突),即0 - 0 == 1 - 1
,条件成立,说明冲突,返回0。继续尝试,直至找到Check(1, 2)
返回1,意味着第二行第三列可以放置皇后。
Queenes
数组为 [0, 2, ...,]
。int Queenes[8]
: 用来存储每一行皇后的列位置。其设计使得我们能够快速访问和更新每一行皇后的放置位置,同时保证每行只有一个皇后。int Check(int line, int list)
: 核心验证函数,它接受正在尝试放置的皇后的行号line
和列号list
,并遍历所有已放置的皇后进行冲突检查。
int index
: 循环变量,用于遍历之前所有行中皇后的位置。int data=Queenes[index]
: 获取在已处理的index
行中皇后的列位置。用于与当前尝试位置进行比较,判断是否冲突。line + list
和line - list
),判断是否在同一列或对角线上。设计这种方式是因为在棋盘上,两点在同一对角线上当且仅当它们行列号的差或和相等。此设计利用了数组索引和值的映射关系简化了皇后位置的存储和冲突检查逻辑,使问题的空间复杂度降低。回溯算法通过逐行尝试每一列的策略,并在发现当前尝试路径不可能导致解时立即回溯,这样可以有效地遍历所有可能的摆放方式,而不必搜索整个解空间,提高了算法的效率。
假设在棋盘的第一行,我们不是选择第一列放置皇后,而是选择了第二列(即Queenes[0] = 1
)。此时Queenes
数组更新为[1, 0, 0, 0, 0, 0, 0, 0]
。
尝试在第二行第一列放置皇后 (即line = 1
, list = 0
)。
执行
Check(1, 0)
:
list != Queenes[0]
,无列冲突。(0 + 1) != (1 + 0)
,无主对角线冲突。(0 - 1) != (1 - 0)
,无副对角线冲突。所有检查通过,可以在该位置放置皇后。
更新Queenes
数组为[1, 0, ...,]
。
假设在接下来的尝试中,我们发现某一行无论放在哪个位置都会与之前的皇后产生冲突,例如:
Queenes
数组变成了[1, 0, X, X, X, ...,]
(X表示已经尝试过并放置了皇后但未详细展示)。list
值,Check(5, list)
都返回0
。此时,算法需要回溯:
Queenes
数组值重置为0。Queenes[3]
的值并重新进入尝试放置第五个皇后的流程。Check
函数判断的不同Check
函数负责核实在尝试的行line
和列list
上放置皇后是否会与之前放置的任何一个皇后冲突。它通过检查以下情况来确保放置的安全:
无论是在第一行中选择了第一列还是非第一列,Check
函数的这些判断标准保持不变。关键在于理解皇后的位置是如何通过行列索引的相对位置来确定冲突的:通过列的绝对位置判断列冲突,通过行列索引的和或差判断对角线冲突。
这个设计利用了棋盘格的几何特性来检测对角线冲突。在一个棋盘上,任意两个处于同一对角线上的点(无论是主对角线还是副对角线)都遵循特定的数学关系。我们通过行(index
或line
)和列(data
或list
)的加法和减法来描述这种关系。
当两个皇后在同一主对角线上时,它们满足的条件是行与列的差或和相等。为什么是这样的?
index - data
或 line - list
)保持不变。(index, data)
和(line, list)
的行号和列号的差相等,即index - data == line - list
,则它们位于同一主对角线上。不过这里有个小失误,在原问题中,检测主对角线的条件应该是行号和列号的和相等,即(index + data) == (line + list)
。副对角线的情况稍有不同,但也遵循一个简单的数学规律:
(index, data)
和(line, list)
的行号和列号的和相等,即index + data == line + list
,则它们位于同一副对角线上。而正确的检测副对角线冲突的条件实际上是行号和列号的差相等,即(index - data) == (line - list)
。总结来说:
(index + data) == (line + list)
)(index - data) == (line - list)
)这些几何特性使得我们能够有效地使用简单的算术运算来检测两个皇后是否处于对角线上的冲突位置。
如果觉得文章对您有帮助,请帮忙点赞或者收藏,如果在文章中发现什么错误或不准确的地方,欢迎与我交流。
文章浏览阅读2.5w次,点赞6次,收藏50次。官方解释是,docker 容器是机器上的沙盒进程,它与主机上的所有其他进程隔离。所以容器只是操作系统中被隔离开来的一个进程,所谓的容器化,其实也只是对操作系统进行欺骗的一种语法糖。_docker菜鸟教程
文章浏览阅读5.7k次,点赞3次,收藏14次。该如何避免的,今天小编给大家推荐两个下载Windows系统官方软件的资源网站,可以杜绝软件捆绑等行为。该站提供了丰富的Windows官方技术资源,比较重要的有MSDN技术资源文档库、官方工具和资源、应用程序、开发人员工具(Visual Studio 、SQLServer等等)、系统镜像、设计人员工具等。总的来说,这两个都是非常优秀的Windows系统镜像资源站,提供了丰富的Windows系统镜像资源,并且保证了资源的纯净和安全性,有需要的朋友可以去了解一下。这个非常实用的资源网站的创建者是国内的一个网友。_msdn我告诉你
文章浏览阅读1.2k次。vue2封装对话框el-dialog组件_
文章浏览阅读4.7k次,点赞5次,收藏6次。MFC 文本框换行 标签: it mfc 文本框1.将Multiline属性设置为True2.换行是使用"\r\n" (宽字符串为L"\r\n")3.如果需要编辑并且按Enter键换行,还要将 Want Return 设置为 True4.如果需要垂直滚动条的话将Vertical Scroll属性设置为True,需要水平滚动条的话将Horizontal Scroll属性设_c++ mfc同一框内输入二行怎么换行
文章浏览阅读832次。检查Linux是否是否开启所需端口,默认为6379,若未打开,将其开启:以root用户执行iptables -I INPUT -p tcp --dport 6379 -j ACCEPT如果还是未能解决,修改redis.conf,修改主机地址:bind 192.168.85.**;然后使用该配置文件,重新启动Redis服务./redis-server redis.conf..._redis-server doesn't support auth command or ismisconfigured. try
文章浏览阅读4.9k次。济大数电实验报告_数据选择器及其应用
文章浏览阅读236次。1研究内容消费在生产中占据十分重要的地位,是生产的最终目的和动力,是保持省内经济稳定快速发展的核心要素。预测河南省社会消费品零售总额,是进行宏观经济调控和消费体制改变创新的基础,是河南省内人民对美好的全面和谐社会的追求的要求,保持河南省经济稳定和可持续发展具有重要意义。本文建立灰色预测模型,利用MATLAB软件,预测出2019年~2023年河南省社会消费品零售总额预测值分别为21881...._灰色预测模型用什么软件
文章浏览阅读1.2k次。12.4-在Qt中使用Log4Qt输出Log文件,看这一篇就足够了一、为啥要使用第三方Log库,而不用平台自带的Log库二、Log4j系列库的功能介绍与基本概念三、Log4Qt库的基本介绍四、将Log4qt组装成为一个单独模块五、使用配置文件的方式配置Log4Qt六、使用代码的方式配置Log4Qt七、在Qt工程中引入Log4Qt库模块的方法八、获取示例中的源代码一、为啥要使用第三方Log库,而不用平台自带的Log库首先要说明的是,在平时开发和调试中开发平台自带的“打印输出”已经足够了。但_log4qt
文章浏览阅读786次。全局观思维模型,一个教我们由点到线,由线到面,再由面到体,不断的放大格局去思考问题的思维模型。_计算机中对于全局观的
文章浏览阅读330次。一、CountDownLatch介绍CountDownLatch采用减法计算;是一个同步辅助工具类和CyclicBarrier类功能类似,允许一个或多个线程等待,直到在其他线程中执行的一组操作完成。二、CountDownLatch俩种应用场景: 场景一:所有线程在等待开始信号(startSignal.await()),主流程发出开始信号通知,既执行startSignal.countDown()方法后;所有线程才开始执行;每个线程执行完发出做完信号,既执行do..._countdownluach于cyclicbarrier的用法
文章浏览阅读508次。Prometheus 算是一个全能型选手,原生支持容器监控,当然监控传统应用也不是吃干饭的,所以就是容器和非容器他都支持,所有的监控系统都具备这个流程,_-自动化监控系统prometheus&grafana实战
文章浏览阅读4.7k次。输入关键字,可以通过键盘的搜索按钮完成搜索功能。_react search