現代 C++ 對編譯期的計算，邏輯流程控制有了突破性的增強。上古時代很難做的事在現代都顯得更直覺化了。為了讓自己熟悉現代 C++ 的功能 (沒事找事幹)，所以就寫了一個編譯期算完八皇后所有解法的練習啦。所謂編譯期算完，其實也就是樣版元編程 (template meta-programming) 的各種組合，包含 variadic template, parameter pack 還有 constexpr 等等的組合接技。
如果同學們不確定我在說什麼，白話一句：
編譯這份 code 結束，所有八皇后的解就已經寫在編譯出來的執行檔了。
同學們可能會有疑問：
- 八皇后是什麼？
這是一關於西洋棋的問題，就是問說棋盤上擺八隻皇后能不能安然並存。詳情可以參考維基百科：https://zh.wikipedia.org/wiki/%E5%85%AB%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98 - 編譯期解八皇后可以幹嘛，沒屁用啊
對，不論是在軟體產業開發上，或自己開心寫個小玩具還真沒什麼用處。但小時候在學校也不是 DFS 解八皇后寫得很開心嗎 ^^。做編譯期算八皇后可以讓我們更熟悉 C++ 或是現代 C++ 的更多語法和規則，進而了解什麼做的到什麼做不到。
這篇不會帶同學們細步地看完所有步驟，也不會教怎麼解八皇后，也不是教同學樣版的基礎，網路上有很多別的教學可以看，只會提供大略的註解旁白讓大家知道，現代 C++ 在編譯期計算，也就是樣板元編程 (template meta-programming) 有著超乎想像的張力 XD。
先看結果
整份程式碼放在 gist 上：https://gist.github.com/TommyJSWu/9c2274c07e9810adf299a8399f09a97a。
為了證明編譯完，所有解就算完了，我們直接看看我們的 main() 還有編出來的 assembly 組語。
很簡單，就是宣告一個 std::array 叫 sols 把 solve_queen 算出來的八皇后結果存起來準備印出來。通過編譯組語的方式我們可以看到
g++ a.cpp -S; vim a.s
不得了啦！92 組解全部寫在組語裡面啦！15863724 的意思就是，第一隻皇后擺在第 1 欄，第二隻擺在第 5 欄，依此類推。
下面就把這份 code 用到的所有零件小拼圖們依次帶過功能。
雜魚組件們
編譯期數列 mylist
struct mylist 就是一個非型別的 variadic template，參數是不定個數的 int。帶著一個靜態變數 value 把樣版參數們轉為 std::array。這樣方便我們執行時期 (run-time) 把八皇后的結果印出來。
編譯期連接/串接數列
另外，為了在遞迴過程中，把嘗試放置不同位置的皇后得到的結果們串接起來，需要這個 struct mylist_cat 樣版串接多個 mylist 的樣版參數們。針對多個 mylist 的情況遞迴呼叫 mylist_cat 本身不斷串接，直到剩下兩個 mylist 要串接為止，這個情況我們特化樣版處理。
檢查盤面合法性
每次放一個皇后，我們只要簡單檢查三件事：
- 皇后的
y座標有沒有被佔領過，對應到struct conflict_c。 - 皇后的
x+y值有沒有被其它皇后佔過，對應到struct conflict_d1。 - 皇后的
x-y值有沒有被別的皇后佔領，對應到struct conflict_d2。
三件事的檢查都是通過位元運算遮罩起來做，並且用 C++17 的 std::bool_constant 來表示編譯期的 bool 常數。集中到靜態變數 conflict_v 檢查三者其一成立 (std::disjunction_v) 就是衝突，皇后駕崩了！最後有樣版 struct put_queen，放置皇后時更改這個位元遮罩。
遞迴尋找皇后解 compile-time backtracking
這就是解八皇后最核心的過程，相信大家有著大學資工系的回憶就很熟悉這其中原理了，只不過所有的遞迴和檢查盤面都改成使用樣版在編譯期就完成囉。
無效盤面
八皇后的其中一個停止遞迴條件，就是無效盤面沒有解啦！所以就返回一個空的 mylist 就好，無解！
遞迴/嘗試放棋子
遞迴主要由 struct solve_queen 進行，皇后擺到某一列 r 時，就對所有欄 (1, 2, … 8) 都試試看能不能擺皇后，也就是 struct try_put，並用 mylist_cat 把八個位置放置的結果 try_put_t 串接起來。
而 try_put_t 是個 C++11 的 alias template，為了 solve_queen 的遞迴寫起來清爽定義的。
而 struct try_put 就是試著擺擺看皇后並測試皇后能否即位。這部份我們用 C++17 的 std::conditional_t 去做型別上的 “if”。如果皇后擺放衝突了，被鬥倒了，我們就遞迴到上面說的無效盤面。不然就是進而遞迴到下一列 r+1 的擺放，並且檢查衝突的遮罩 mask 使用 put_queen 劃上一筆佔用的位置。我們的皇后擺法 solution 使用十進位的 int 來表示，所以擺放後需要 sol * 10 + c 來表示。
最後是遞迴完八個皇后發現八國鼎立沒有人互相打架，爽。需要一個遞迴終止條件把當前擺法回傳，也就是最後的特化 solve_queen<9, mask, sol>。
講完了
把上面的所有 code 片段拼起來你就能夠做到編譯完就算完八皇后囉。懶得自己拼湊的同學可以直接看 gist：https://gist.github.com/TommyJSWu/9c2274c07e9810adf299a8399f09a97a。
希望這篇粗略的介紹能讓大家稍微看到現代 C++11/C++14/C++17 在編譯期的計算和控制上能多麼巧妙地完成。
喔對了，這東西在 clang 10.0.0 在我的電腦上要編譯 6 到 7 秒…。所以絕對不是鼓勵大家編譯期解八皇后或是 DFS 等等的演算法問題，單純就是開個腦洞加上練習熟悉你手上的工具能力的範圍界限 ^^，大家掰掰！
