西洋棋中的 八皇后問題
前言
最近剛好看到這題，以前沒學好的題目，重讀了一次，順手做個筆記幫助記憶，也分享給有需要或有興趣的讀者。內容枯燥，適合睡前閱讀。
我只略懂表面，歡迎高手路人留言指導，教學相長。
問題描述
八皇后問題是一個經典的計算機科學問題，目標是：在 8 × 8 的西洋棋棋盤上放置 8 個皇后，且任兩個皇后都不能在同一行，或同一列，或同一對角線上。這意味著棋盤上任何兩個皇后都不能互相攻擊，彼此相安無事。這題一共有 92 種不同的解法。
八皇后問題還可以擴展到更大的棋盤和更多的皇后，稱之為 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 N2 取 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 個位子可以選
但其中有一堆重複的擺法，還有一堆不符合題目要求的擺法，這樣解題非常浪費算力。
稍作優化
- 根據題目要求，任兩個皇后不能擺在同個 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 個位子可選，依此類推
- 根據題目要求，任兩個皇后也不能擺在同個 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，依此類推
- 根據題目要求，任兩個皇后除了不能擺在相同 row，或相同 column，或彼此對角線上。
擺了一個皇后後，她的 row、column、對角線上，不能再出現另位皇后
因此 decision tree 可以再縮小一些，很好理解，就不畫出來了。
總結
完整步驟：
- 從 row 0 到 row 3，依序選擇 1 個 col 位子，擺放 1 個皇后
- 選擇 col 時，從 col 0 開始檢查是否在其他皇后的 col 或對角線上。若無，則把皇后放下去。若有，則檢查下個位子， col 1，直到 col 3
- 若 col 0~3 都不能擺，則回到前一個 row，按步驟 1、步驟 2 幫皇后換個位子。
- 直到 row 0 到 row 3 都擺了皇后，即找到一組解
- (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---
結語
小時不讀書，長大當社畜，真是悔不當初啊~
