德杰尼斯五后问题求解方法
2016-06-01李盘林,赵铭伟,徐喜荣,李丽双,李伯章
李 盘 林, 赵 铭 伟, 徐 喜 荣, 李 丽 双, 李 伯 章
( 1.大连理工大学 电子信息与电气工程学部, 辽宁 大连 116024;2. 滑铁卢大学 计算机工程系, 加拿大 安大略 滑铁卢 )
德杰尼斯五后问题求解方法
李 盘 林*1,赵 铭 伟1,徐 喜 荣1,李 丽 双1,李 伯 章2
( 1.大连理工大学 电子信息与电气工程学部, 辽宁 大连116024;2. 滑铁卢大学 计算机工程系, 加拿大 安大略滑铁卢 )
摘要:给出了棋盘坐标表示,定义了皇后控制数或剩余控制数,以及皇后最佳(极佳)或剩余最佳(极佳)位置的概念.利用棋盘对称性,通过有效的计算,先求出了五后问题的3个基础解,进而得到了全部24个解及其图示,并首次给出了最少放置5个而不是4个皇后的证明,以及解的完备性证明.
关键词:五后问题;皇后控制数或剩余控制数;皇后最佳(极佳)或剩余最佳(极佳)位置
0引言
在信息领域,八后问题、五后问题,了解它们的不乏其人.前者由高斯解决[1],后者就不那么幸运了.都说五后问题但其内涵是不同的(http://cjc.iteye.com/blog/299173;http://wenku.baidu.com/view/c254e769a98271fe910ef965.html).1862年,德杰尼斯[2](De Jaenisch)研究在8×8棋盘上最少放置几个皇后,它们彼此互不攻击,又能控制其他任意棋子.他给出7个皇后的解,而正确解是5个.为了不忘德杰尼斯的先期工作,将下面论题:在8×8棋盘上最少放置5个皇后,能否使5个皇后各自安全且又能吃掉棋盘上其余任意棋子(皇后占用的五格不同行、或不同列、或不同一对角线,且又能与棋盘上其余格同行、或同列、或同一对角线)称为德杰尼斯五后问题[3].本文给出上述论题的一种解法.
1求解前的说明……p>
