技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 八皇后问题算什么,来看看无穷皇后问题吧

八皇后问题算什么,来看看无穷皇后问题吧

浏览:2448次  出处信息

     当 1848 年国际象棋玩家 Max Bezzel 提出八皇后问题(eight queens puzzle)时,他恐怕怎么也想不到,100 多年以后,这个问题竟然成为了编程学习中最重要的必修课之一。八皇后问题听上去非常简单:把八个皇后放在国际象棋棋盘上,使得这八个皇后互相之间不攻击(国际象棋棋盘是一个 8×8 的方阵,皇后则可以朝横竖斜八个方向中的任意一个方向走任意多步)。虽然这个问题一共有 92 个解,但要想徒手找出一个解来也并不容易。下图就是其中一个解:

    

     八皇后问题有很多变种,不过再怎么也不会比下面这个变种版本更帅:请你设计一种方案,在一个无穷大的棋盘的每一行每一列里都放置一个皇后,使得所有皇后互相之间都不攻击。具体地说,假设这个棋盘的左下角在原点处,从下到上有无穷多行,从左到右有无穷多列,你需要找出一个全体正整数的排列方式 a1, a2, a3, ... ,使得当你把第一个皇后放在第一行的第 a1 列,把第二个皇后放在第二行的第 a2 列,等等,那么任意两个皇后之间都不会互相攻击。

    

      

      

      

      

      

      

      

      

      

         下面给出一个非常简单巧妙的构造。首先,我们给出五皇后问题的一个解。并且非常重要的是,其中一个皇后占据了最左下角的那个格子。

    

     接下来,我们把五皇后的解扩展到 25 皇后,而依据则是五皇后本身的布局:

    

     这样一来,同一组里的五个皇后显然不会互相攻击,不同组的皇后之间显然也不会互相攻击,这便是一个满足要求的 25 皇后解了。注意到,在扩展之后,之前已经填好的部分并未改变。

     再接下来怎么办呢?没错,我们又把 25 皇后的解复制成五份,再次按照五皇后的布局来排列,从而扩展到 125 皇后!

    

     像这样不断地根据已填的部分,成倍地向外扩展,便能生成一个无穷皇后问题的解。

QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1