奇数网格(或棋盘)德杰尼斯问题解法

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

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

0 引 言

鉴于五后问题的由来，作者在文献[1]中将它称为德杰尼斯五后问题，并先后进行了德杰尼斯五后问题解法[2]和德杰尼斯五后问题泛化研究[3]．文献[3]是将文献[2]的论域8×8网格(或棋盘)推广到2p×2p网格(或棋盘)(p=1，2，…)上．

若对任意偶数e，称e×e网格(或棋盘)为偶数网格(或棋盘)，用数学语言可表为2p×2p网格(或棋盘)(p=1，2，…)；若对任意奇数o，称o×o网格(或棋盘)为奇数网格(或棋盘)，用数学语言可表为(2p+1)×(2p+1)网格(或棋盘)(p=1，2，…，p=0为平凡情形)．于是，文献[3]题目又可表述为偶数网格(或棋盘)德杰尼斯问题解法．虽然只有一字之差，但是两者解决问题的方法还是有所区别的．将本文与文献[3]合并起来，便得到一个新论题：对任意自然数n，n×n网格(或棋盘)德杰尼斯问题解法．可见，本文和文献[3]对这一论题的完成是不可或缺的．

1 求解前的准备

奇数网格(或棋盘)坐标表示如图1所示．

图1 (2p+1)×(2p+1)网格坐标图示Fig.1 Coordinate illustration of (2p+1)×(2p+1) grid

从图1可知，该图形是关于直线aa、bb、dd和gg对称的，它们相交于c，其坐标为(p+1/2，p+1/2)，以c为中心的格，称为中心格，表示为sp+1，p+1．可见，本文格仍沿用文献[2]或文献[3]的表示方式，即用格的右上角顶坐标来表示．为方便计，si，j简记为sij．

定义1S={sij|1≤i，j≤2p+1}，即用S表示(2p+1)×(2p+1)网格中的所有格集合．(文献[2]中是用C表示的)

定义2位于直线dd和bb上及其它们相交域(夹角≤90°)内的所有格，称为解首格集，表示为

Sf={sij|j≤i≤p+1，1≤j≤p+1}

与文献[1]、[2]中相同的定义，在此不再赘述．

又令Sfr={sij|sp-r+2p-r+2，sp-r+3p-r+2，…，sp+1p-r+2}为Sf中从中心点……