当前位置:主页   - 电脑 - 程序设计 - C/C++
N皇后问题摆法算法描述
来源:网络   作者:   更新时间:2012-08-21
收藏此页】    【字号    】    【打印】    【关闭

  本文示例源代码或素材下载

  题目说明:

  在一个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。

分享到:

其它资源

来源声明

  • 版权与免责声明
    1、本站所发布的文章仅供技术交流参考,本站不主张将其做为决策的依据,浏览者可自愿选择采信与否,本站不对因采信这些信息所产生的任何问题负责。
    2、本站部分文章来源于网络,其版权为原权利人所有。由于来源之故,有的文章未能获得作者姓名,署“未知”或“佚名”。对于这些文章,有知悉作者姓名的请告知本站,以便及时署名。如果作者要求删除,我们将予以删除。除此之外本站不再承担其它责任。
    3、本站部分文章来源于本站原创,本站拥有所有权利。
    4、如对本站发布的信息有异议,请联系我们,经本站确认后,将在三个工作日内做出修改或删除处理。
    请参阅权责声明

进入 esk365.com 首页