西洋棋中的 八皇后問題

前言

最近剛好看到這題，以前沒學好的題目，重讀了一次，順手做個筆記幫助記憶，也分享給有需要或有興趣的讀者。內容枯燥，適合睡前閱讀。

我只略懂表面，歡迎高手路人留言指導，教學相長。

問題描述

八皇后問題還可以擴展到更大的棋盤和更多的皇后，稱之為 N皇后問題 (N-Queens Problem)，可用於測試和理解演算法的性能，Edsger Dijkstra 也曾用這問題來展示結構化編程 (structured programming) 的能力。

八皇后問題也曾出現在 1990 年代初期的著名電子遊戲《第七訪客》中。

舉例

為方便製圖與解說，下面以四皇后 (4x4棋盤，4個皇后) 為例。圖中四個皇后的位置，彼此不在攻擊範圍，所以算是其中一組解。

四皇后問題的其中一組解，4位皇后相安無事

而下圖中，有兩位皇后位於彼此的對角線上，處於攻擊位置，因此不是這題的解。

以紅色衰臉表示。

兩個紅后在對角線上，可互相攻擊，不能當作解

解的數量

四皇后有 2 組解，八皇后有 92 組解。

下表直接列出 N皇后問題中，不同的 N 分別有多少組解。可以注意到，若且唯若 N = 1 或 N ≥ 4，則 N皇后問題有解。即 N = 2 或 N = 3 時，此題無解。

The Number of Solutions for the N-Queens Problem

解題方法

暴力解

窮舉所有皇后的擺法，然後逐一檢查是否為解。

然而全部有 C N² 取 N 種不同的擺法，當 N = 4 已有 1820 種擺法，而當 N = 8 則暴增到 4,426,165,368 種擺法，如何有邏輯的窮舉，是這題的關鍵。其實也非常簡單，下面繼續以四皇后問題為例來說明。

*由於講行、列容易混淆，所以之後都用 row、col 取代：row 表示橫向 (左右)，col 表示縱向 (上下，即 column 之意)。

在大小為 4x4 的棋盤 ，擺放 4 個皇后

首先，直覺想法是：

• 第 1 個皇后，有 16 個位子可以選
• 第 2 個皇后，剩 15 個位子可以選
• 第 3 個皇后，剩 14 個位子可以選
• 第 4 個皇后，剩 13 個位子可以選

但其中有一堆重複的擺法，還有一堆不符合題目要求的擺法，這樣解題非常浪費算力。

稍作優化

1. 根據題目要求，任兩個皇后不能擺在同個 row 上，所以簡化為在每個 row 擺 1 個皇后：

• row 0 擺 1 個皇后，有 4 個位子可選 (column 0、1、2、3)
• row 1 擺 1 個皇后，有 4 個位子可選
• row 2 擺 1 個皇后，有 4 個位子可選
• row 3 擺 1 個皇后，有 4 個位子可選

如下圖， decision tree 大概長這樣。

row 0 有 4 個位子可選，不論選哪，row 1 也會有 4 個位子可選，依此類推

2. 根據題目要求，任兩個皇后也不能擺在同個 column 上，所以再簡化為在每個 row 擺 1 個皇后，且 column 不能重複：

• row 0 擺 1 個皇后，有 4 個位子可選
• row 1 擺 1 個皇后，剩 3 個位子可選
• row 2 擺 1 個皇后，剩 2 個位子可選
• row 3 擺 1 個皇后，剩 1 個位子可選

如圖，整個 decision tree 變小許多。

如紅叉所示，如果在 row 0 時選擇了 col 0 擺放皇后，row 1 就不能將皇后擺放在 col 0，依此類推

3. 根據題目要求，任兩個皇后除了不能擺在相同 row，或相同 column，或彼此對角線上。

擺了一個皇后後，她的 row、column、對角線上，不能再出現另位皇后

因此 decision tree 可以再縮小一些，很好理解，就不畫出來了。

總結

完整步驟：

1. 從 row 0 到 row 3，依序選擇 1 個 col 位子，擺放 1 個皇后
2. 選擇 col 時，從 col 0 開始檢查是否在其他皇后的 col 或對角線上。若無，則把皇后放下去。若有，則檢查下個位子， col 1，直到 col 3
3. 若 col 0~3 都不能擺，則回到前一個 row，按步驟 1、步驟 2 幫皇后換個位子。
4. 直到 row 0 到 row 3 都擺了皇后，即找到一組解
5. (optional) 若想找到其他解，就跳到步驟 3。持續到最後就能檢查完整個 decision tree

不好描述，建議搭配程式一起看。

可以把 decision tree 當作舊文 混亂的約會行程，竟是學妹給的智力測驗 裡的有向無環圖 (DAG)，概念就完全一樣了！

從 decision tree 的起點往下走，直到最深處，然後回到上一層，選擇另條路再走到最深處，邊走邊檢查 row 和 col 是否符題目要求。

程式實作

程式碼

使用 C++

n_queens.cpp

class NQueens {
 public:
  std::vector<std::vector<std::string>> FindSolutions(int n) {
    std::vector<std::vector<std::string>> ret;
    std::vector<int> temp(n);
    Backtrack(ret, temp, n, 0, 0);
    return ret;
  }

  void Backtrack(std::vector<std::vector<std::string>>& ret,
      std::vector<int> temp, int n, int row, int col) {
    if (row == n) Save(ret, temp);
    if (row == n || col == n) return;
    if (IsSafe(temp, row, col)) {
      temp[row] = col;
      Backtrack(ret, temp, n, row+1, 0);
    }
    Backtrack(ret, temp, n, row, col+1);
  }

  bool IsSafe(std::vector<int>& temp, int row, int col) {
    for (int i = 0; i < row; ++i) {
      if (temp[i] == col) return false;
      if (std::abs(temp[i]-col) == std::abs(i-row)) return false;
    }
    return true;
  }

  void Save(std::vector<std::vector<std::string>>& ret,
            std::vector<int>& temp) {
    auto n = temp.size();
    std::vector<std::string> ans(n, std::string(n, '-'));
    for (std::size_t i = 0; i < temp.size(); ++i) {
      ans[i][temp[i]] = 'Q';
    }
    ret.emplace_back(std::move(ans));
  }
};

int main(int argc, char *argv[]) {
  int n = std::atoi(argv[1]);
  int count = 1;
  auto solutions = NQueens{}.FindSolutions(n);

  // print solutions
  for (const auto& sol : solutions) {
    std::cout << "solution: " << count++ << std::endl;
    for (const auto& s : sol) {
      std::cout << s << std::endl;
    }
    std::cout << std::endl;
  }
  return EXIT_SUCCESS;
}

看不懂很正常，我直接從個人的題庫筆記 copy 過來，有些不相關的 code。

編譯

g++ n_queens.cpp -o n_queens

執行結果

四皇后

$ ./n_queen.out 4

solution: 1
-Q--
---Q
Q---
--Q-

solution: 2
--Q-
Q---
---Q
-Q--

八皇后，看起來 92 種解法都有找到，但沒驗證過。

$ ./n_queen.out 8

solution: 1
Q-------
----Q---
-------Q
-----Q--
--Q-----
------Q-
-Q------
---Q----

solution: 2
Q-------
-----Q--
-------Q
--Q-----
------Q-
---Q----
-Q------
----Q---

(略)

solution: 92
-------Q
---Q----
Q-------
--Q-----
-----Q--
-Q------
------Q-
----Q---

結語

小時不讀書，長大當社畜，真是悔不當初啊~