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

基于(N-1)×(N-1)棋盘的解的情况推出N×N棋盘的解的情况的N皇后问题

N皇后问题是一个比较经典的问题,其主要目标是在N×N的棋盘上,放置N个皇后,要求所有皇后之间不能互相攻击,即任意两个皇后不能处在同一行、同一列或同一对角线上。解决该问题可以采用递归的方式,基于(N-1)×棋盘的解的情况推出N×N棋盘的解的情况。

解决N皇后问题的关键在于如何放置皇后。可以用一个二维数组board表示棋盘,其中board[i][j]表示第i行第j列是否放置了皇后。对于每一行i,遍历该行的每一列j,判断该位置是否可以放置皇后。如果可以放置,将board[i][j]置为1,继续判断下一行。如果不能放置,继续遍历该行的下一列。如果遍历完该行的所有列都不能放置皇后,则返回上一行,重新遍历该行的下一列。

对于基于(N-1)×棋盘的解的情况推出N×N棋盘的解的情况,可以分为两个步骤:

1.复制(N-1)×棋盘的解到N×N棋盘 2.在N×N棋盘上填充第N个皇后

具体实现方式如下:

  1. 复制(N-1)×棋盘的解到N×N棋盘 对于(N-1)×棋盘的解,可以直接复制到N×N棋盘的前N-1行,第N行先不填充皇后,之后再填充。

  2. 在N×N棋盘上填充第N个皇后 对于第N行,遍历该行的每一列j,判断该位置是否可以放置皇后。如果可以放置,将board[N][j]置为1,继续填充下一行。如果不能放置,继续遍历该行的下一列。如果遍历完该行的所有列都不能放置皇后,则返回上一行,重新遍历该行的下一列。

最终得到的解就是N×N棋盘上所有皇后都不互相攻击的放置方案。

http://www.lryc.cn/news/207338.html

相关文章:

  • Vue mixin混入
  • 基于 FFmpeg 的跨平台视频播放器简明教程(十):在 Android 运行 FFmpeg
  • 正点原子嵌入式linux驱动开发——Linux LCD驱动
  • 2-Java进阶知识总结-6-多线程
  • openwrt下游设备在校园网(DLUT-LingShui)中使用ipv6网络
  • 10个基于.Net开发的Windows开源软件项目
  • Java多线程秘籍,掌握这5种方法,让你的代码优化升级
  • npm install报错 缺少python
  • 达梦:开启sql日志记录
  • C语言开发,指针进阶,字符串查找,包含,拼接
  • PyCharm中文使用详解
  • 一键同步,无处不在的书签体验:探索多电脑Chrome书签同步插件
  • 在Go项目中二次封装Kafka客户端功能
  • CVE-2021-44228 Apache log4j 远程命令执行漏洞
  • 前端跨域相关
  • HTML笔记-狂神
  • python自动化测试工具selenium
  • 输入/输出应用程序接口和设备驱动程序接口
  • Python---Socket 网络通信
  • 使用 jdbc 技术升级水果库存系统(优化版本)
  • 网络协议--广播和多播
  • python爬虫入门(三)正则表达式
  • fabric.js介绍
  • YOLOv5源码中的参数超详细解析(3)— 训练部分(train.py)| 模型训练调参
  • Linux高性能编程学习-TCP/IP协议族
  • 用爬虫代码爬取高音质音频示例
  • 深度学习与计算机视觉(一)
  • 【vector题解】杨辉三角 | 删除有序数组中的重复项 | 只出现一次的数字Ⅱ
  • 金字塔切分注意力模块PSA学习笔记 (附代码)
  • Jenkins自动化测试