d543: 挑戰極限 Part7：強大的N皇后

2021-07-08 18:41:41 +0800 CST Tags: 8-queen, bitmask, performance

出處：https://zerojudge.tw/ShowProblem?problemid=d543
提交：https://zerojudge.tw/Submissions?problemid=d543&account=allllllan123456

問題：給你許多個正整數 $N\in[1,15]$，問你每個正整數所對應到的棋盤邊長有多少種擺放 $N$ 皇后的方法。

解法：八皇后乃程式設計課經典的入門題型，目的是為了練習實作 DFS；然而，這題在判斷哪些位置還可以放棋子的時候其實還有個非常神秘且強大的加速技巧。。。。統一考慮本題的擺放方式為一個橫列 (row) 之中由右至左的每個直行 (column) 依序檢查之後再移往下一個橫列，所以最先擺放的位置為棋盤的最右上角，最後擺放的位置為棋盤的最左下角，那麼一個眾所周知的資料儲存方式便是用一個變數 col 的 bitmask 去記錄到目前為止有哪些 column 已經被放過了，LSB 代表最右邊的 column，MSB 代表最左邊的 column，這個變數只需要一個，但是其他記錄每條對角線有沒有放過的變數就要很多個嗎？其實也不然，我們可以觀察到每個 row 裡面固定就是 $N$ 個位置，因此在同一個 row 底下可能影響到的兩個方向的對角線條數也都剛好是 $N$ 條而已，而且由上一個 row 轉移到下一個 row 的過程中都是有一條可能被影響到的對角線從一端被移除，同時卻也有另一條可能被影響到的對角線從另外一端被加入，這不就是 sliding window 的概念嗎？所以，為了要在每個 row 都讓負責東北西南向的對角線 diag1 和負責西北東南向的對角線 diag2 的 LSB 都對齊 (align) 到 col 的 LSB，很容易知道轉移到下一個 row 的時候 diag1 要 left shift，而 diag2 要 right shift。另外還有一個極其重要的加速技巧就是，要找到下一個最右邊 (LSB) 的可放置位置其實不一定要一個 bit 一個 bit 檢查，可以用 LSB(ava) = ava & -ava 的位元運算技巧直接找出來，然後再用 ava ^= LSB(ava) 把 LSB(ava) 設為不可放置，如此一來就仍然能在 for loop 裡持續使用掉各種可能的位置而讓迴圈中止。

附註：
[1] https://medium.com/fcamels-notes/%E4%BD%BF%E7%94%A8%E4%BD%8D%E5%85%83%E8%A8%88%E7%AE%97%E5%8A%A0%E9%80%9F%E6%B1%82%E8%A7%A3-n-queen-d20442f34110

 1#include <bits/stdc++.h>
 2using namespace std;
 3
 4int n, counter;
 5
 6void dfs(unsigned col, unsigned diag1, unsigned diag2) {
 7	if (col == n) counter++;
 8	for (unsigned ava=n&~(col|diag1|diag2), now=ava&-ava; // now is the current position to be placed.
 9        ava; ava^=now, now=ava&-ava) // ava is short for available columns.
10        dfs(col|now, (diag1|now)<<1, (diag2|now)>>1);
11}
12
13int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
14	while (cin >> n)
15        counter=0, n=(1<<n)-1, dfs(0, 0, 0), cout << counter << '\n';
16    return 0;
17}