李 盘 林， 赵 铭 伟， 徐 喜 荣， 李 丽 双， 李 伯 章

( 1.大连理工大学 电子信息与电气工程学部, 辽宁 大连 116024；2.滑铁卢大学 计算机工程系， 加拿大 安大略 滑铁卢 )

德杰尼斯五后问题泛化研究

李 盘 林*1， 赵 铭 伟1， 徐 喜 荣1， 李 丽 双1， 李 伯 章2

( 1.大连理工大学 电子信息与电气工程学部, 辽宁 大连 116024；2.滑铁卢大学 计算机工程系， 加拿大 安大略 滑铁卢 )

在德杰尼斯五后问题求解方法基础上，给出了2p×2p棋盘坐标表示，定义了方环和马步格，并利用皇后控制数或剩余控制数、皇后最佳(极佳)位置或剩余最佳(极佳)位置，以及棋盘对称性，得到了德杰尼斯五后问题泛化求解定理和便于求解的简化定理．

德杰尼斯五后问题；皇后控制数或剩余控制数；皇后最佳(极佳)或剩余最佳(极佳)位置；方环；马步格

0 引 言

在德杰尼斯五后问题求解方法[1](下称五后问题)一文的结语中，指出对于2p×2p(p=1，2，…)棋盘上最少放置多少皇后，使它们在不同行、不同列和不同对角线上且能吃掉(或称管控)棋盘上其余任何棋子(下称五后问题泛化论题)这一问题的求解途径[2]，它可极大限度地克服以往人们用视察法求解[3]的盲目性．随着p的增大，收效更加明显．本文进一步详细地研究五后问题泛化论题．

1 求解前准备

(1)2p×2p棋盘坐标表示：完全类似于文献[1]中的描述，见图1．

(2)方环的定义：由格sp,p，sp+1,p，sp+1,p+1和sp,p+1组成p级方环；由格sp-1,p-1，sp,p-1，sp+1,p-1，sp+2,p-1，sp+2,p，sp+2,p+1，sp+2,p+2，sp+1,p+2，sp,p+2，sp-1,p+2，sp-1,p+1，sp-1,p组成p-1级方环…由格s1,1，s2,1，…，s2p,1，s2p,2，…，s2p,2p，…，s2,2p，s1,2p，…，s1,2组成1级方环(或称边界方环)．由各级方环中的格所组成的集合，记为Rk，1≤k≤p，如Rp={sp,p，sp+1,p，sp+1,p+1，sp,p+1}．从方环定义可知，方环是对于某些格在棋……