免费做橙光封面的网站,服装设计自学软件,龙华做棋牌网站建设多少钱,微信管理系统官网转载自 漫画#xff1a;什么是八皇后问题#xff1f;题目是什么意思呢#xff1f;国际象棋中的皇后#xff0c;可以横向、纵向、斜向移动。如何在一个8X8的棋盘上放置8个皇后#xff0c;使得任意两个皇后都不在同一条横线、竖线、斜线方向上#xff1f;让我们来举个栗子什么是八皇后问题题目是什么意思呢国际象棋中的皇后可以横向、纵向、斜向移动。如何在一个8X8的棋盘上放置8个皇后使得任意两个皇后都不在同一条横线、竖线、斜线方向上让我们来举个栗子下图的绿色格子是一个皇后在棋盘上的“封锁范围”其他皇后不得放置在这些格子下图的绿色格子是两个皇后在棋盘上的“封锁范围”其他皇后不得放置在这些格子那么如何遵循规则同时放置这8个皇后呢让我们来看看小灰的回答。———————————什么是八皇后问题八皇后问题是一个古老的问题于1848年由一位国际象棋棋手提出在8×8格的国际象棋上摆放八个皇后使其不能互相攻击即任意两个皇后都不能处于同一行、同一列或同一斜线上如何求解以高斯为代表的许多数学家先后研究过这个问题。后来当计算机问世通过计算机程序的运算可以轻松解出这个问题。如何解决八皇后问题所谓递归回溯本质上是一种枚举法。这种方法从棋盘的第一行开始尝试摆放第一个皇后摆放成功后递归一层再遵循规则在棋盘第二行来摆放第二个皇后。如果当前位置无法摆放则向右移动一格再次尝试如果摆放成功则继续递归一层摆放第三个皇后......如果某一层看遍了所有格子都无法成功摆放则回溯到上一个皇后让上一个皇后右移一格再进行递归。如果八个皇后都摆放完毕且符合规则那么就得到了其中一种正确的解法。说起来有些抽象我们来看一看递归回溯的详细过程。1.第一层递归尝试在第一行摆放第一个皇后2.第二层递归尝试在第二行摆放第二个皇后前两格被第一个皇后封锁只能落在第三格3.第三层递归尝试在第三行摆放第三个皇后前四格被第一第二个皇后封锁只能落在第五格4.第四层递归尝试在第四行摆放第四个皇后第一格被第二个皇后封锁只能落在第二格5.第五层递归尝试在第五行摆放第五个皇后前三格被前面的皇后封锁只能落在第四格6.由于所有格子都“绿了”第六行已经没办法摆放皇后于是进行回溯重新摆放第五个皇后到第八格。7.第六行仍然没有办法摆放皇后第五行也已经尝试遍了于是回溯到第四行重新摆放第四个皇后到第七格。8.继续摆放第五个皇后以此类推......八皇后问题的代码实现解决八皇后问题可以分为两个层面
1.找出第一种正确摆放方式也就是深度优先遍历。
2.找出全部的正确摆放方式也就是广度优先遍历。由于篇幅优先我们本篇只介绍如何找出第一种正确摆放方式。在研究代码实现的时候我们需要解决几个问题1.国际象棋的棋盘如何表示
很简单用一个长度是8的二维数组来表示即可。由于这里使用的是int数组int的初始值是0代表没有落子。当有皇后放置的时候对应的元素值改为1。在这里二维数组的第一个维度代表横坐标第二个维度代表纵坐标并且从0开始。比如chessBoard[3][4]代表的是棋盘第四行第五列格子的状态。2.如何判断皇后的落点是否合规
定义一个check方法传入新皇后的落点通过纵向和斜向是否存在其他皇后来判断是否合规。3.如何进行递归回溯
递归回溯是本算法的核心代码逻辑有些复杂4.如何输出结果
这个问题很简单直接遍历二维数组并输出就可以。5.如何把这些方法串起来
在main函数里分三步来调用
第一步初始化
第二步递归摆放皇后
第三步最后输出结果。其中Queen8是整个类的名字。最终输出如下10000000
00001000
00000001
00000100
00100000
00000010
01000000
00010000几点补充1.由于篇幅原因这一篇只讲了如何找出第一种正确的八皇后摆放。大家如果有兴趣可以对文中的代码稍作改动实现找出所有八皇后摆放的代码。2.本漫画纯属娱乐还请大家尽量珍惜当下的工作切勿模仿小灰的行为哦。
