八皇后加强版:每个皇后最多攻击一个其它的皇后

    想必搞OI/ACM的朋友都应该知道八皇后问题,这是学习编程的必修课程之一:在国际象棋棋盘上最多可以放置多少个互不攻击的皇后(皇后可以攻击它所在的行、列、对角线方向上的棋子)?显然,能够放置的皇后数不超过8个,因为国际象棋的棋盘一共就8行8列。事实上,放置8个互不攻击的皇后是有可能的,并且方法不止一种。
    上个月的IBM Ponder This考虑了一个八皇后问题的扩展:最多可以在国际象棋棋盘上放置多少个皇后,使得每一个皇后最多只能攻击到一个其它的皇后?


 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
    首先我们证明,一个n行n列的棋盘上不能放置超过4n/3个皇后,使得每个皇后的攻击范围内最多只有一个其它的皇后。用Xi表示有多少个行放置了i个皇后,用Yi来表示有多少个列放置了i个皇后。由于同一行(或者同一列)不能放置3个或3个以上的皇后,即一行(或一列)的皇后个数只能是0个、1个或者2个。于是有X0+X1+X2=n, Y0+Y1+Y2=n。因此,我们有X1+X2≤n, Y1+Y2≤n。同时,在X2个放了2个皇后的行中共有2*X2个皇后,其中的每一个皇后都已经攻击了同行的另一个皇后,因此至少有2*X2列里恰好有一个皇后,即2*X2≤Y1。类似地,2*Y2≤X1。令m为棋盘上的皇后总数,则m=X1+2*X2=Y1+2*Y2
    于是,我们有

  m = (X1+2X2 + Y1+2Y2)/2
     = (X1+4X2/3+2X2/3 + Y1+4Y2/3+2Y2/3)/2
     ≤ (X1+4X2/3+Y1/3 + Y1+4Y2/3+X1/3)/2
     = 2(X1+X2 +Y1+Y2)/3 ≤ 4n/3

    当n=8时,上界m=10是可以达到的。

+---+---+---+---+---+---+---+---+
| * |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   | * | * |   |   |
+---+---+---+---+---+---+---+---+
|   | * |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   | * |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   | * |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   | * |   |
+---+---+---+---+---+---+---+---+
|   |   | * | * |   |   |   |   |
+---+---+---+---+---+---+---+---+
| * |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+

11 条评论

发表评论

2  +  4  =