技术标签: 算法
问题描述:国际象棋里,棋盘为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)
)这些几何特性使得我们能够有效地使用简单的算术运算来检测两个皇后是否处于对角线上的冲突位置。
如果觉得文章对您有帮助,请帮忙点赞或者收藏,如果在文章中发现什么错误或不准确的地方,欢迎与我交流。
文章浏览阅读744次。前言最近项目在对接美团外卖功能 实现外面小哥凭取货码取货对接完功能后 用户反馈 弹出的软键盘 很难输入 数字太小了大概是下面这种显示方式需求组长说 要不搞一个自定义软键盘吧 数字搞大点 方便外卖员输入数字我设置了输入EditText的输入格式为Number 还是不行那就开搞吧先来看下实现的效果图吧实现效果GIF实现代码自定义View 一个NineNumericKeyboardView/** * Author by Lyu * Date on 2021/5/26-19:55 _android studio九宫格软键盘设置
文章浏览阅读150次。code地址:https://github.com/dennybritz/nn-from-scratch文章地址:http://www.wildml.com/2015/09/implementing-a-neural-network-from-scratch/ Get the code: To follow along, all the code is also available as a..._nerual networks from stratch in python
文章浏览阅读1.6w次,点赞8次,收藏10次。问题:想让el-select自适应宽度,即 label宽度 + el-select宽度可以填满一行,想要实现这样的效果详细描述:项目中的代码如下,给 el-select 设置了 style=“width:100%” 没有作用,不论布局是变大变小,el-select 的宽度都不会有变化,就像下图所示我只有在el-select中设置固定的值如 style="width:100px"才有作用。下面是我的代码,不知道是不是我对width的设置方法有错<el-form :inline=“true” _el-form-item 宽度
文章浏览阅读498次。前言不管用什么语言编写的Web应用,它们都用一个共同点,具有交互性并且多数是数据库驱动。在网络中,数据库驱动的Web应用随处可见,由此而存在的SQL注入是影响企业运营且最具破坏性的漏洞之一,这里我想问,我们真的了解SQL注入吗?看完本篇文章希望能让你更加深刻的认识SQL注入。目录 第一节 注入攻击原理及自己编写注入点 1.1、什么是SQL? 1.2、什么是SQL注入? 1.3、SQL注入是怎么样产生的? 1.4、编写注入点 第二节 寻找及确认SQL注入 2.1、推理测试法 2.2、a_class=1 攻击
文章浏览阅读3.3k次。不知道为毛,Windows10突然乱码了。。。于是重新装了一下系统,然后打开一个基于CodeFirst连接mysql的项目文件。。。 然后Update-Database 我曹。。。。。。System.Runtime.Serialization.SerializationException: 未解析成员“MySql.Data.MySqlClient.MySqlException,MySql.Data_mysql.data, version=6.9.9.0
文章浏览阅读262次。转载:https://blog.csdn.net/ohmygirl/article/details/17849983上文( http://blog.csdn.net/ohmygirl/article/details/17846199 )中已经介绍了Fiddler的原理和软件界面。本文主要针对Fiddler的抓包处理。Fiddler抓取HTTP请求。抓包是Fiddler..._3)使用fiddler分析http请求
文章浏览阅读666次,点赞11次,收藏8次。Android studio的gradle版本下载太慢或者content time out超时的完美解决方法_androidstudio下载gradle超时
文章浏览阅读1.5w次,点赞14次,收藏64次。dom-to-image_dom-to-image
文章浏览阅读6.8k次,点赞2次,收藏19次。什么是知识库知识库(Knowledge base)是用于知识管理的一种特殊的数据库,以便于有关领域知识的采集、整理以及提取。 知识库中的知识源于领域专家或者从业者的经验教训,它是求解问题所需领域知识的集合,包括基本事实、规则和其它有关信息。构建企业知识库系统能将知识进行有效管理及合理利用,也能积累和保存信息及知识资产,加速内部信息及知识的流通,实现组织内部知识的共享。企业知识库系统的作用具体表现在:知识库系统为企业资料提供有效安全的管理,防止人员流动等原因造成的企业知识财产受损。 知识库系统使_什么是知识库
文章浏览阅读1.2w次,点赞5次,收藏3次。问题:java中List.forEach()无法实现continue和break功能。代码:package com.ziling.mianshi;import java.util.ArrayList;import java.util.List;/** * @Author: yipeng * @Date: 2021/7/21 11:34 */public class ForEachTest { public static void main(String[] args_java foreach continue
文章浏览阅读10w+次,点赞41次,收藏141次。 _rmse函数
文章浏览阅读370次。秋叶 PPT 双 12 大促年终盛典全场精品课享年度超值价买课赠书最高立省 801本文作者:小爽本文审核:玛奇鹅本文编辑:竺兰大家好,我是继续挖掘 Excel 各种技巧的小爽~在工作中,我们经常需要在 Excel 中填写一些固定选项的数据。对于「懂点 Excel」的小伙伴来说,一般会选择用【数据验证】的功能制作下拉列表。不过一旦数据选项过多,用下拉列表选择还是会显得比较麻烦,手还很累。..._isnumber(find(cell("contents")