主題
題目連結：
題目大意：
輸入有多筆測試資料。每筆測資第一列給定一正整數 n （3 < n < 15，當 n = 0 時代表輸入結束），代表有一個 n × n 的棋盤。接著有 n 列輸入，每列給定 n 個字元，代表棋盤每一格的性質。字元只會是 '.' 或是 '*'，前者代表著空地、後者為障礙物。
現在我們需要在給定的棋盤上放 n 個皇后，使得皇后彼此之間不會互相攻擊，但是皇后不能放在有障礙物的格子上。試問有多少種這樣子的版面？輸出格式參見範例輸出。
範例輸入：
8
........
........
........
........
........
........
........
........
4
.*..
....
....
....
0
範例輸出：
Case 1: 92
Case 2: 1
解題思維：
雖然這題的作法更動一下（多判斷目前位置有沒有障礙物）便可以求出所求版面數量。
不過這次我們可以最佳化一下我們遞迴方式——我們可以將原本儲存每行、每條對角線有無皇后存在的「狀態」以 n 個位元儲存。而我們可以套用位元遮罩（Bit Mask）的概念得到每一列皇后的可行的位置。
每行的狀態位元比較容易理解，例如我們現在窮舉的是 5 × 5 的皇后，而我們在第 0 列第 0 行、第 1 列第 2 行各放了一個皇后，因此目前狀態可以寫為 10100 （雖然通常第「0」位於最右邊的位元，但是這邊是為了方便理解對應關係）。因此原本所有可能的位置 11111 考慮了每行有的皇后（00101）後，便得到了 11010 （因為根據行的資訊，你不能再放皇后在第一行和第三行）。
那對角線呢？我們先考慮主對角線（Main Diagonal，其為左上到右下之對角線），而這可以從以下範例看出（為了凸顯顏色，以下用「#」代替「.」）：
#####
#####
#####
#####
#####
一開始我們將一個皇后放在第 0 列第 0 行：
Q####
#####
#####
#####
#####
而我們記錄為 10000 （實際上還需要做其他的操作，等等會提到）。所以當我們遞迴到第 1 列時，我們可以看到我們不應該在以下紅色的位置放皇后：
Q####
#####
#####
#####
#####
而只考慮主對角線的話，其他皆為可以放。因此可行位置為 10111，而這是從主對角線遮罩 10000 往右移動一位元得到 01000 所產生的。假設此時我們放一個皇后在第 1 列第 2 行，則遮罩變成了 01100：
Q####
##Q##
#####
#####
#####
當我們遞迴到第 2 列時，可以看到紅色位置（第 1 列的紅色依舊保留著）以及藍色位置不應擺放皇后：
Q####
##Q##
#####
#####
#####
同樣，只考慮主對角線的話， 11001 為可行位置。而這是由上一列的主對角線遮罩 01100 往右移得到 00110 並產生而成。
所以我們可以看到主對角線的「資訊」往下一列傳遞時，會往右移動一位元（左邊新移動進來的位元補 0）。因為主對角線所代表著的是皇后可以攻擊從左上到右下之方向的位置。而每往下一列，我們便往右一行。
類似地，我們可以看到另一條對角線（反對角線，英文稱 Anti-Diagonal 或是 Counter Diagonal）有著相似的行為，不過是向左移動一位元（同樣，右邊新移動進來的位元補 0）。
假設我們在目前列有著行遮罩 C 、 主對角線 MD 、 反對角線 CD ，而原本可行的位置為 n 個 1 的位元數組 P（11……1）。根據以上結果，我們可以得到當前列的可行位置為
P & (~C) & (~MD) & (~CD)
其中「&」代表著位元間的 AND 運算，而「~」代表著要將位元資訊反轉。因為本來遮罩們「1」的位置代表著「不能」放皇后，所以反轉後「0」變「1」、「1」變「0」，所以「0」現在才是代表著「不能」放的位置。而全部的遮罩 AND 起來之後的資訊就是當前列可行的位置。
例如上面第 0 列第 0 行、第 1 列第 2 行放了皇后，因此到第 2 列時，C = 10100 、 MD = 00110 、 CD = 01000 ，因此我們可以將遮罩們反轉後與原本可放位置全部 AND 起來得到
11111
01011
11001
10111
-AND-
00001
因此我們本列只剩最右邊的位置可以放皇后。
而我們可以用另一個伎倆將一個位元數組的最低位（最右邊）的「1」擷取出來。假設可行位置為 P ，則我們只需要做
P & (-P)
便可以得到最右邊的「1」之位元。例如 P = 11010，而 -P 為 P 之二補數，其等價於 (~P) + 1。因此 -P 為 00110 （如果以平常的角度看待 P（將其視為 5 位元有號整數） ，其所代表十進位值為 -6 ，而 -P 之值為 6）。而
11010
00110
-AND-
00010
我們便將最低位 L 孤立了出來，然後我們將 P 的該位元之「1」變為 0 ，藉由 P ^ L 便可以得到消去該位元後的新 P 值。然後我們繼續此步驟便可以獲得下一個最低位的「1」，直到 P 變為 0 為止。然後每個 L 值即代表著本列一個可行的皇后擺放位置，因此我們就擺放看看並遞迴下去。
不過因為二進位是右邊的值比較小：2 ^ 0 、 2 ^ 1 、 …… 。而我們不想多做一個反轉的轉換，例如最右邊的位元代表著這一列最左邊的位置，從右邊數來第 i 個位元代表棋盤上從左邊數來第 n - i 個位置。而這樣的計算也會浪費時間，所以通常我們會直接將最右邊的位元對應著棋盤最左邊的位置，也就是反轉以上所有的位元對應關係。再強調一次，以上是為了方便辨識而將最右邊的位元對應於最右邊的位置。
最後，因為本題會有障礙物，所以每一列的原始可行位置不一定是連續的 n 個 1。我們在輸入時，可以對每列建立其可行位置，而有障礙物之位置其對應的位元在還沒有遮罩之前就已經設為「0」（代表不可放）。然後照常地套用以上作法即可得到所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
