【譯】N 皇后問題 – 構造法原理與證明 時間複雜度O(1)

  • [原] E.J.Hoffman; J.C.Loessi; R.C.Moore
  • The Johns Hopkins University Applied Physics Laboratory
  • *[譯]* EXP 2017-12-29

注意

由於原文使用了「m皇后」進行描述，所以本文從現在開始也使用「m皇后」進行描述。
我這裡就不調整為大多數人習慣的「n皇后」了，避免某些數學公式參數混淆。

*【寫在前面】*

這是現在網上流傳的一套關於M皇后問題的構造法公式，但是這套公式是怎麼得來的，卻鮮有人知。而文本會詳細闡述這套公式的推導過程：

img

1. 前言

文本核心內容主要譯自 E.J.Hoffman、 J.C.Loessi 和 R.C.Moore 發表於 Mathematics Magazine 《數學雜誌》 上的學術論文 《Constructions for the Solution of the m Queens Problem》 。

該論文已被美國數學協會 Mathematical Association of America 公開，具體期數為 Vol.42, No.2 (Mar., 1969), pp. 66-72。

該文獻可從以下途徑購買：

該文獻的英文原文鏈接：

2. 問題背景

M皇后問題： 在M×M格的國際象棋上擺放M個皇后，使其不能互相攻擊，即任意兩個皇后都不能處於同一行、同一列或同一斜線上。

根據場景，又有三種衍生問題：

  • ① 共有多少種擺法（即有多少種可行解）
  • ② 求出所有可行解
  • ③ 求任意一個可行解

問題① 屬於 禁位排列 問題，目前是存在通項公式直接求解的。

問題② 屬於 搜索 問題，在網上也有多種解法，主流是 回溯法（另有衍生的位運算變種演算法），但不管如何優化，回溯法都有一個致命的問題：M值不能過大（一般M=30已是極限）。

問題③ 屬於 問題② 的子集，因此很多人的切入點依然是回溯法，也有啟發式演算法的解法：如遺傳演算法、還有劉汝佳在《演算法藝術與資訊學競賽》提出的啟發式修補演算法。啟發式演算法在M<10000左右都是可解的，但是因為啟發式演算法均存在隨機性，收斂速度視不同的收斂因子而變化（我看過某篇論文稱啟發式演算法在M=10000時的耗時等價於回溯法M=30的耗時）。

但早在1969年， 問題③ 的解就被 E.J.Hoffman、 J.C.Loessi 和 R.C.Moore 找到了潛在的數學規律，通過推導出數學公式，利用 構造法 使得該問題可在 O(1) 的時間複雜度得到解。

3. 譯者的話

① 原文寫得有點艱澀，有些中間步驟是跳過了。我就加上自己的理解做了意譯，並補上了跳過的步驟和圖示，但是核心的推導思路和步驟不會修改。

② 原文首先給出了3個構造式（其實就是m皇后問題的通解式），然後以此為結論展開了一系列的推導證明這3個構造式是正確的。但是這3個構造式真正是怎麼得來，原作者並沒有說，估計是原作者做了大量的演繹、從m皇后的特解找到了潛在規則所總結出來的通解。

4. 譯文：m皇后問題的構造解法

4.1. 數學模型定義

m皇后問題最初是由Gauss（高斯）提出的，該問題描述如下：

是否有可能在一個m×m的國際棋盤上放置m個皇后使得她們無法互相攻擊？（註：皇后是國際象棋中的一種棋子，她可以對橫、豎、斜三個方向的棋子發起攻擊）

這是一個有趣的問題，我們可以將其約束到一個 數學模型 進行描述：

把棋盤定義為一個m×m的方格矩陣，那麼對於任意方格可以使用有序對 (i, j) 以表示其行列坐標，其中 1 ≤ i ≤ m 表示該方格的行編號， 1 ≤ j ≤ m 表示該方格的列編號。

同時我們再為每個方格定義一組對角編號：

令自左上到右下方向為主對角線，對於主對角線上的方格 (i, j) ，顯然有：

　　m - j + i = MAJOR_CONSTANT —— 譯者註：這個公式對後續推導起到重要作用

其中 MAJOR_CONSTANT 稱之為主對角常數，顯然有 1 ≤ MAJOR_CONSTANT ≤ m ，將其定義為方格 (i, j) 的主對角編號。

進一步地，令自右上到左下方向為次對角線，對於次對角線上的方格 (i, j) ，顯然有：

　　i + j - 1 = MINOR_CONSTANT —— 譯者註：這個公式對後續推導起到重要作用

其中 MINOR_CONSTANT 稱之為次對角常數，顯然有 1 ≤ MINOR_CONSTANT ≤ m ，將其定義為方格 (i, j) 的次對角編號。

m皇后問題的解模型【圖 1】 m皇后問題的解模型

至此，m皇后問題的解模型可以定義為如下：

放置m個皇后到一個m×m的方格矩陣，使得皇后們的所在的方格同時滿足下面所有條件：

  • ① 行編號唯一
  • ② 列編號唯一
  • ③ 主對角編號唯一
  • ④ 次對角編號唯一

這個模型足以解決所有m皇后問題（但僅適用於 m ≥ 4 的情況，因為 m = 2、3 時無解，m = 1 的解就不需要討論了） —— 譯者註：這個大前提條件會在最後進行論證

4.2. m皇后通解：三個構造式

由於通解公式相對複雜，為了便於說明，此處不從過程推導出結論，而是反其道而行之：先給出結論的通解公式（且不考慮公式是怎麼推演出來的），再證明之。

m皇后問題的解的共由3個構造式組成。

4.2.1. 【構造式A】

令 m = 2n，其中 n = 2, 3, 4, …

構造式A僅適用於m是偶數的情況，它由兩個子公式組成：

img

使用構造式A解決12皇后問題的解【圖 2】 使用構造式A解決12皇后問題的解

4.2.2. 【構造式B】

令 m = 2n，其中 n = 2, 3, 4, …

構造式B同樣僅適用於m是偶數的情況，它同樣由兩個子公式組成：

img

使用構造式B解決14皇后問題的解【圖 3】 使用構造式B解決14皇后問題的解

4.2.3. 【構造式C】

構造式C是構造式A或B的擴展推導式，僅適用於m+1是奇數的情況：

當已使用構造式A或B求得一個m×m的皇后問題的解時，若同時增加第 m+1 行和第 m+1 列，那麼第 m+1 個皇后應放置在坐標為 (m+1, m+1) 的方格。

構造式C解集圖示（在前面構造式B的示例解集基礎上增加一行一列）【圖 4】 構造式C解集圖示（在前面構造式B的示例解集基礎上增加一行一列）

4.3. 三個構造式的正確性證明

要證明構造式是成立的，只需要證明每個構造式導出的皇后位置均滿足：

  • ① 行編號唯一
  • ② 列編號唯一
  • ③ 主對角編號唯一
  • ④ 次對角編號唯一

4.3.1. 【構造式A】的證明

4.3.1.1. 【構造式A】

令 m = 2n，其中 n = 2, 3, 4, …（即m≥4且是偶數）：

img

構造式含義：若把棋盤在橫中軸線切開，很明顯解集是呈中心旋轉對稱的，其中上半部分對應PA-1的解集，下半部分對應PA-2的解集：

構造式A解集圖示【圖 5】 構造式A解集圖示

4.3.1.2. 【定理A】

定理A

對於m皇后問題，當 n != 3λ + 1 （其中 λ = 0, 1, 2, ... ）時，則必定可以使用【構造式A】求解。

4.3.1.3. 【定理A】的證明

① 行列編號的唯一性證明：

  • 根據 PA-1 導出的皇后位置為 (k, 2k) ，其中 1 ≤ k ≤ n
  • 根據 PA-2 導出的皇后位置為 (2n+1-l, 2n+1-2l) ，其中 1 ≤ l ≤ n
  • 明顯地，PA-1 的每個皇后放置在前n行的每個奇數列，PA-2 的每個皇后放置在後n行的每個偶數列，亦即每行每列均有且只有一個皇后，行列編號的唯一性得證。

② 主對角編號的唯一性證明：

img

　受 k、l 的取值範圍影響，顯然是不可能的，主對角編號的唯一性得證。

③ 次對角編號的唯一性證明：

img

　由此可知當 n != 3λ + 1（λ = 0, 1, 2, ...）時，次對角編號是唯一的。

　綜上①②③，定理A得證 。

4.3.2. 【構造式B】的證明

4.3.2.1. 【構造式B】

令 m = 2n，其中 n = 2, 3, 4, …（即 m ≥ 4 且是偶數）：

img

為了便於說明，對 PB-1 和 PB-2 的對m取mod運算做一下等價處理：

img

構造式含義：若把棋盤在橫中軸線切開，很明顯解集是呈中心旋轉對稱的，其中上半部分對應 PB-1 的解集，下半部分對應 PB-2 的解集。同時根據列編號 mod m 部分的取值（ ≥m 或 <m ），PB-1 與 PB-2 的解集又分別拆分成兩個分段函數子集：

構造式B解集圖示【圖 6】 構造式B解集圖示

4.3.2.2. 【定理B】

定理B

對於m皇后問題，當 n != 3λ （其中 λ = 1, 2, 3, ... ）時，則必定可以使用【構造式B】求解。

4.3.2.3. 【定理B】的證明

① 行列編號的唯一性證明：

img

　明顯地：

  • 當n是偶數時，PB-1 的每個皇后放置在前n行的每個偶數列，PA-2 的每個皇后放置在後n行的每個奇數列；
  • 當n是奇數時，PB-1 的每個皇后放置在前n行的每個奇數列，PA-2 的每個皇后放置在後n行的每個偶數列。
  • 亦即不論n的奇偶性如何，每行每列均有且只有一個皇后，行列編號的唯一性得證。

② 主對角編號的唯一性證明：

img

  • 化簡（1）得 k+l = 4n-2，但因為 MIN(k+l) = 2，此時 n = 1，與前提條件 m=2n≥4 ⇒ n≥2 矛盾，因此（1）不成立。
  • 化簡（4）得 k'+l' = 2n+4，與 MAX(k'+l') = 2n 矛盾，因此（4）不成立。
  • 化簡（5）得 k+k' = 2n 從取值範圍看顯然不成立。
  • 化簡（6）得 l'-l = 2n 從取值範圍看顯然不成立。
  • 化簡（2）得 k+l' = 4，化簡（3）得 k'+l = 4，
  • 由於 k 與 l 的取值範圍相同， k' 與 l' 的取值範圍相同，因此有：

img

　而 n = 3 不在定理B的前提條件 n != 3λ（λ = 1, 2, 3, ...）範圍內，可以直接排除。

　因此 n > 3（否則 k' 與 l' 不能存在），所以不存在 n = 2 或 n = 3 取值的可能性，亦即（2）（3）實際均不成立。

　綜上，（1）（2）（3）（4）（5）（6）均不成立，主對角編號的唯一性得證。

③ 次對角編號的唯一性證明：

img

  • 化簡（1）得 2n = 3(k+l-2)，因此 k+l-2 必為偶數，令 2λ = k+l-2（λ = 1, 2, 3, ...），則有 2n=3(2λ) ⇒ n=3λ，即當且僅當 n = 3λ 時（1）成立。
  • 化簡（2）得 4n = 3(k+l'-2)，因此 k+l'-2 必為二重偶數（即至少能被2整除兩次），令 4λ = k+l'-2（λ = 1, 2, 3, ...），則有 4n=3(4λ) ⇒ n=3λ，即當且僅當 n = 3λ 時（2）成立。
  • 化簡（3）得 4n = 3(k'+l-2)，因此 k'+l-2 必為二重偶數（即至少能被2整除兩次），令 4λ = k'+l-2（λ = 1, 2, 3, ...），則有 4n=3(4λ) ⇒ n=3λ，即當且僅當 n = 3λ 時（3）成立。
  • 化簡（4）得 2n = k'+l'-2，但從 k' 與 l' 的取值範圍可知 MAX(k'+l'-2) = n+n-2 = 2n-2，亦即 2n > k'+l'-2，因此（4）不成立。
  • 化簡（5）得 2n = 3(k'-k)，因此 k'-k 必為偶數，令 2λ = k'-k（λ = 1, 2, 3, ...），則有 2n=3(2λ) ⇒ n=3λ，即當且僅當 n = 3λ 時（5）成立。
  • 化簡（6）得 2n = 3(l'-l)，因此 l'-l 必為偶數，令 2λ = l'-l（λ = 1, 2, 3, ...），則有 2n=3(2λ) ⇒ n=3λ，即當且僅當 n = 3λ 時（6）成立。

　由此可知，當 n != 3λ（λ = 1, 2, 3, ...）時，（1）（2）（3）（4）（5）（6）均不成立，次對角編號的唯一性得證。

　綜上①②③，定理B得證 。

4.3.3. 【構造式C】的證明

4.3.3.1. 兩條【引理】

我們定義棋盤上由方格 (1, 1)、 (2, 2)、 (3, 3)、 …、 (m, m) 連線所得的對角線為標準對角線，亦即標準對角線的行列編號必有 i == j 。

構造式C解集圖示【圖 7】 構造式C解集圖示

在證明構造式C之前，首先需要證明兩條引理：

  • 【引理A】 使用構造式A得到的解，沒有任何皇后的坐標是在標準對角線上的。
  • 【引理B】 使用構造式B得到的解，沒有任何皇后的坐標是在標準對角線上的。

① 【引理A】的證明：

img

　k = 0 與取值範圍 k = 1, 2, 3, ..., n 矛盾，l = 0 與取值範圍 l = 1, 2, 3, ..., n 矛盾，因此假設不成立，【引理A】得證。

② 【引理B】的證明：

img

　由於 2n=m≥4 ⇒ n≥2，因此（1）（3）不成立，否則 k,l ≤ 0，與取值範圍矛盾。

　又由於（2）（4）的取值範圍 k,l ≤ n，（2）（4）明顯不成立。

　因此假設不成立，【引理B】得證。

4.3.3.2. 【定理C】

定理C

對於可使用【構造式A】或【構造式B】求解的m皇后問題，若同時增加第 m+1 行和第 m+1 列，使其延展為 m+1 皇后問題，那麼這個 m+1 皇后問題也是可解的，且第 m+1 個皇后應放置在坐標為 (m+1, m+1) 的方格。

4.3.3.3. 【定理C】的證明

① 行列編號的唯一性證明：

　由於【定理C】是從【定理A】或【定理B】上擴展的，且【定理A】與【定理B】的所有皇后的行列編號唯一性已得到證明，而【定理C】的第 m+1 行與第 m+1 列是新增的，那麼第 m+1 個皇后的行列編號也必定是唯一的，因此所有皇后的行列編號必定也是唯一的。

② 主對角編號的唯一性證明：

　由於第 m+1 個皇后的主對角線與標準對角線是重合的，而通過【引理A】與【引理B】可知在m×m範圍內的標準對角線上不存在任何皇后，換言之標準對角線上只有第 m+1 個皇后，所以主對角線編號是唯一的。

③ 次對角編號的唯一性證明：

　對於第 m+1 條次對角線，上面只有 (m+1, m+1) 一個方格，顯然次對角線編號是唯一的。

4.4. 大前提條件m≥4的證明

上述所有的證明，都是基於一開始給出的大前提條件：

  • 對於構造式A或B：令 m = 2n，其中 n = 2, 3, 4, …（即 m≥4 且 m是偶數）
  • 對於構造式C：在構造式A或B可解的基礎上令 m+1（即 m≥5 且 m是奇數）

亦即m皇后問題（ m≥4 且 m是偶數）可通過【構造式A】或【構造式B】求解，而 m+1 皇后問題（ m+1≥5 且 m是奇數）則可通過【構造式C】求解。

至於為什麼 m=1、 m=2 或 m=3 時並不適用於構造式A、B、C就是這裡要討論的。

首先當 m=1 時，雖然是有明確的唯一解，但並不存在 m=2n 的形式。而n作為三個構造式的重要變數，既然一開始就不存在n值，構造式A、B、C也就無從談起了。

　那麼需要證明的，就是為什麼 m=2 與 m=3 也不可取？

　證明：

img

　　不難發現，（2）中 m=2 是在 m<4 範圍內沒有被約束條件限制的特例。

　　但當 m=2 時 n=1，不妨把 n=1 代入 PB-1 與 PB-2，取值範圍均矛盾，無法計算列坐標編號。

　　因此對於【定理A】與【定理B】而言，m=2 都是不可解的，從而導致 m=3 也不可用【定理C】求解。

　證畢（事實上，通過畫圖可以明顯發現 m=2、 m=3 是無解的）。

5. 譯者後記：通解轉換式（編程用）

在原作者提出的三個構造式A、B、C中，均使用 (i, j) 的二維坐標形式標記每個皇后的位置，從數學角度上更易於表達作者的思想，但是不便於編程使用。

為此譯者在這裡補充針對構造式A、B、C的轉換公式，使用一維坐標形式標記每個皇后位置，以配合編程使用（其實這就是目前網上普遍流傳的m皇后問題構造式）。

　一維坐標的標記方式為：從第1行開始，依次寫出m個數字，分別代表每行的皇后列坐標。亦即行坐標為數序（索引/下標），列坐標為數值。

　如序列 [5, 3, 1, 6, 8, 2, 4, 7] 等價於 (1,5), (2,3), (3,1), (4,6), (5,8), (6,2), (7,4), (8,7)

5.1. 【構造式A】的轉換式

　約束條件：n != 3λ + 1（其中λ = 0, 1, 2, ...）

  • 即：m != 2(3λ+1) ⇒ (m mod 6) != 2（m為偶數）
  • 且：m-1 != 6λ+2 ⇒ (m mod 6) != 3（m為奇數，此時適用於構造式C）

　當m為偶數時：

  • 把行編號 1~n 代入 PA-1，可得到第 1~n 行的解序列： [2, 4, 6, 8, ..., m]
  • 把行編號 n+1~2n 代入 PA-2，可得到第 n+1~m 行的解序列： [1, 3, 5, 7, ..., m-1]
  • 合併兩個解序列，就是構造式A的通解轉換式（A1）：
    　　[2, 4, 6, 8, ..., m], [1, 3, 5, 7, ..., m-1] ………………………………………………………（A1）

　當m為奇數時：

  • 把行編號 1~m-1 代入（A1），可得到第 1~m-1 行的解序列： [2, 4, 6, 8, ..., m-1], [1, 3, 5, 7, ..., m-2]
  • 然後直接套用構造式C（增加第m行第m列），則可得到通解轉換式（A2）：
    　　[2, 4, 6, 8, ..., m-1], [1, 3, 5, 7, ..., m-2], [m] ………………………………………………（A2）

5.2. 【構造式B】的轉換式

　約束條件：不滿足構造式A約束條件的，都可使用構造式B求解。

  • 即：m mod 6 = 2 （m為偶數）
  • 或：m mod 6 = 3（m為奇數，此時適用於構造式C）

　當m為偶數時, n=m/2：

　　若n為偶數：

  • 把行編號 1~n 代入 PB-1，可得到第1~n 行的解序列（註：PB-1是分段函數）： [n, n+2, ..., m], [2, 4, 6, ..., n-2]
  • 把行編號 n+1~2n 代入 PB-2，可得到第 n+1~m 行的解序列（註：PB-2是分段函數）： [n+3, n+5, ..., m-1], [1, 3, 5, ..., n+1]
  • 合併兩個解序列，就是構造式B的通解轉換式（B1）：
    　　[n,n+2,...,m], [2,4,6,...,n-2], [n+3,n+5,...,m-1], [1,3,5,...,n+1] ………………………………………（B1）

　　若n為奇數：

  • 把行編號 1~n 代入 PB-1，可得到第 1~n 行的解序列（註：PB-1是分段函數）： [n, n+2, ..., m-1], [1, 3, 5, ..., n-2]
  • 把行編號 n+1~2n 代入 PB-2，可得到第 n+1~m 行的解序列（註：PB-2是分段函數）： [n+3, n+5, ..., m], [2, 4, 6, ..., n+1]
  • 合併兩個解序列，就是構造式B的通解轉換式（B2）：
    　　[n, n+2, ..., m-1], [1, 3, 5, ..., n-2], [n+3, n+5, ..., m], [2, 4, 6, ..., n+1] ………………………（B2）

　當m為奇數時, n=(m-1)/2：

　　若n為偶數：

  • 把行編號 1~m-1 代入（B1），可得到第 1~m-1 行的解序列： [n, n+2, ..., m-1], [2, 4, 6, ..., n-2], [n+3, n+5, ..., m-2], [1, 3, 5, ..., n+1]
  • 然後直接套用構造式C（增加第m行第m列），則可得到通解轉換式（B3）：
    　　[n, n+2, ..., m-1], [2, 4, 6, ..., n-2], [n+3, n+5, ..., m-2], [1, 3, 5, ..., n+1], [m] ………………（B3）

　　若n為奇數：

  • 把行編號 1~m-1 代入（B2），可得到第 1~m-1 行的解序列： [n, n+2, ..., m-2], [1, 3, 5, ..., n-2], [n+3, n+5, ..., m-1], [2, 4, 6, ..., n+1]
  • 把行編號1然後直接套用構造式C（增加第m行第m列），則可得到通解轉換式（B4）：
    　　[n, n+2, ..., m-2], [1, 3, 5, ..., n-2], [n+3, n+5, ..., m-1], [2, 4, 6, ..., n+1], [m] ………………（B4）

5.3. 小結：通解轉換式歸整

img

Tags:

VirMach 便宜 VPS

QNews

QNews