• linkedu视频
  • 平面设计
  • 电脑入门
  • 操作系统
  • 办公应用
  • 电脑硬件
  • 动画设计
  • 3D设计
  • 网页设计
  • CAD设计
  • 影音处理
  • 数据库
  • 程序设计
  • 认证考试
  • 信息管理
  • 信息安全
菜单
linkedu.com
  • 网页制作
  • 数据库
  • 程序设计
  • 操作系统
  • CMS教程
  • 游戏攻略
  • 脚本语言
  • 平面设计
  • 软件教程
  • 网络安全
  • 电脑知识
  • 服务器
  • 视频教程
  • JavaScript
  • ASP.NET
  • PHP
  • 正则表达式
  • AJAX
  • JSP
  • ASP
  • Flex
  • XML
  • 编程技巧
  • Android
  • swift
  • C#教程
  • vb
  • vb.net
  • C语言
  • Java
  • Delphi
  • 易语言
  • vc/mfc
  • 嵌入式开发
  • 游戏开发
  • ios
  • 编程问答
  • 汇编语言
  • 微信小程序
  • 数据结构
  • OpenGL
  • 架构设计
  • qt
  • 微信公众号
您的位置:首页 > 程序设计 >数据结构 > N皇后问题摆法算法描述

N皇后问题摆法算法描述

作者:匿名 字体:[增加 减小] 来源:互联网 时间:2017-06-28

匿名通过本文主要向大家介绍了八皇后问题递归算法,八皇后问题算法,八皇后问题算法思想,n皇后问题算法,八皇后算法等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
</div>

题目说明:

在一个N×N的国际象棋棋盘中摆N个皇后,使这N个皇后不能互相被对方吃掉。

题目要求:

(1)依次输出各种成功的放置方法。

(2)最好能画出棋盘的图形形式,并动态的演示试探过程。

(3)程序能方便的移植到其它规格的棋盘上。

例如:在一个4×4的棋盘可以摆放的棋位置{(0,1)(1,3)(2,0)(3,2)},{(0,2)(1,0)(2,3)(3,1)}两种。

题目分析:

一、试探过程分析:

N×N皇后问题的求解过程就是一个试探回逆的过程。如图-1

 

(图1-1)

1、首先查找第一行的可放位置,第一行全部可以放,那么我们就先将第一个皇后放在(0,0)点。

(图1-2)

2、再查找第二行,由于第一行的(0,0)已经放了皇后,故第二行的(1,0)和(1,1)都能放皇后了,可放的就是(1,2)和(1,3)点,在(1,2)放上皇后。

(图1-3)

3、再查找第三行,查找所以发现第三行没有可放的位置了,回逆到第二行讲皇后放到(1,3)再查找第3行。如果还不行,就回到第一行将第一行的皇后放人下一个可放的点,依次类推,查找N×N上的所以可放的位置,直到第一行所以位置被放完,输出结果。

4、根据上面的规律可以发现,对于一个皇后放在坐标(x,y),它的下一行位置为(x-1,y)(x,y)(x+1,y)的坐标都不能再放皇后。我们用一个数组来存放本行能放皇后的点。用循环来查找上面行对本行的影响,将收到影响的点置FAlSE。

5、计算公式为:
iPlaceOver[col - (column - i)] = false;
iPlaceOver[col] = false;
iPlaceOver[col + (column - i)] = false;

其中col是上面行皇后的位置,column是当前的第N行。

6、跌代过程:

for (i = 0 ; i < m_iCount ; i ++)
{  
  if (iPlaceOver[i]) //如果是可以放皇后的位置
  {
    m_piSaveQPlace[column] = i;//保存位置
    ComputQueenPlace(column + 1);//递归搜索下一行
  }
}
7、为了动态保存计算结果,程序使用了一个整形的数组指针存放每次结果中每行的位置。为了方便和清晰的显示,我使用了一个结构保存。

8、增加了一个位图保存函数,用来保存希望保存为位图的结果。

 2  下一页</div> </div> </div> </div> </div>
分享到:QQ空间新浪微博腾讯微博微信百度贴吧QQ好友复制网址打印

您可能想查找下面的文章:

  • N皇后问题摆法算法描述

相关文章

  • 2017-06-28模拟退火算法求解TSP问题
  • 2018-08-06有序链表转换二叉搜索树
  • 2017-06-28数据结构教程 第十三课 队列
  • 2017-06-28数据结构教程 第十一课 栈的应用
  • 2017-06-28数据结构教程
  • 2017-06-28数据结构教程 第三十九课 索引文件
  • 2017-06-28计算字符串的相似度
  • 2017-08-17UVa1584 环状序列 (Circular Sequence)
  • 2017-06-28数据结构教程 第二十六课 图的定义与术语
  • 2017-08-17做幻方

文章分类

  • JavaScript
  • ASP.NET
  • PHP
  • 正则表达式
  • AJAX
  • JSP
  • ASP
  • Flex
  • XML
  • 编程技巧
  • Android
  • swift
  • C#教程
  • vb
  • vb.net
  • C语言
  • Java
  • Delphi
  • 易语言
  • vc/mfc
  • 嵌入式开发
  • 游戏开发
  • ios
  • 编程问答
  • 汇编语言
  • 微信小程序
  • 数据结构
  • OpenGL
  • 架构设计
  • qt
  • 微信公众号

最近更新的内容

    • 迭代算法与递归算法的概念及区别
    • 链表的c语言实现(二)
    • 数据结构教程 第三十八课 文件概念、顺序文件
    • 数据结构教程 第六课 线性表的顺序表示和实现
    • 数据结构教程 第四十课 总复习
    • 数据结构教程 第二十六课 图的定义与术语
    • 数据结构教程 第三十一课 动态查找表
    • 验证哥德巴赫猜想
    • 数据结构教程 第三十三课 哈希表(二)
    • 面向对象编程(OOP)理解

关于我们 - 联系我们 - 免责声明 - 网站地图

©2020-2025 All Rights Reserved. linkedu.com 版权所有