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

想必搞OI/ACM的朋友都应该知道八皇后问题，这是学习编程的必修课程之一：在国际象棋棋盘上最多可以放置多少个互不攻击的皇后（皇后可以攻击它所在的行、列、对角线方向上的棋子）？显然，能够放置的皇后数不超过8个，因为国际象棋的棋盘一共就8行8列。事实上，放置8个互不攻击的皇后是有可能的，并且方法不止一种。

上个月的IBM Ponder This考虑了一个八皇后问题的扩展：最多可以在国际象棋棋盘上放置多少个皇后，使得每一个皇后最多只能攻击到一个其它的皇后？

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

于是，我们有

m = (X₁+2X₂+ Y₁+2Y₂)/2

= (X₁+4X₂/3+2X₂/3 + Y₁+4Y₂/3+2Y₂/3)/2

≤ (X₁+4X₂/3+Y₁/3 + Y₁+4Y₂/3+X₁/3)/2

= 2(X₁+X₂+Y₁+Y₂)/3 ≤ 4n/3

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

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