[week1] 八皇后問題
===

關於這個經典的程式問題的歷史淵源，網路上已經有很多的紀錄，這邊就針對簡述問題並且提出比較精簡的解法

八皇后問題就是要在一個 8 * 8 的西洋棋盤上放置 8 個西洋棋皇后，並且各皇后間不存在可以吃掉別人的關係（西洋棋的皇后可以吃掉垂直下左右以及對角線上的棋子）

如果你去 google 相關的解法，像是 [Opencc 的 <八個皇后>](https://openhome.cc/Gossip/AlgorithmGossip/EightQueen.htm) ，基本上就是我們等下要實做的程式邏輯

常見的方法是透過遞迴的觀念，根據之前下的棋子位置找出下一行可以下的區域

// source from Opencc 的 <八個皇后>

int main(void) { 
    int column[N] = {0};        // 同行是否有皇后
    int slash[2 * N] = {0};     // 右上至左下是否有皇后 
    int backSlash[2 * N] = {0}; // 左上至右下是否有皇后 
    int queens[N] = {0}; 

    backTrack(column, slash, backSlash, queens, 0, print); 
    
    return 0; 
} 

由於預設就是從左向右（由於[大陸跟台灣對於 column / row 翻譯正好是相反的](http://lifehaskilledme.blogspot.com/2007/08/blog-post.html)，所以我接下來只用上下左右講）遞增一的方式掃描可以放置棋子，在左右順序固定連續加一的前提下，我們是不用去討論左右的位置的

事實上，在遞迴的解法裡，我們關心的只有 **「每次放棋子的時候，上至下那一格可以放？」** 跟 **「現在下完最後一個棋子了嗎？」**

但是網路上的多數解法都用到陣列去存值，事實上可以簡化到用 int 或甚至 short 大小就好了，透過 bit operation 可以輕鬆作到

### 遞迴程式邏輯

| V | | | | | | | |
| -- | -- | -- | -- | -- | -- | -- | -- |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |

以上圖為例，一開始我們先隨機在第一個上下行取一個位置

為了要表示目前下子的位置，我們用二進位記成 current_pos `0b10000000`，以最上方的格子作為 Most Significant Bit（MSB）

此時要下第二個棋子時，我們需要知道「什麼地方是可以下的」，透過我們剛剛下的第一個棋子，我們可以推出下一個上下行「什麼地方是不行的」

| V | X | | | | | | |
| -- | -- | -- | -- | -- | -- | -- | -- |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |

如上圖，因為我們目前只考慮第二個上下行

首先建立一個遮罩 horizon_conflict 用於判斷水平方向不能放的位置，這邊因為第一個左右列已經被佔領了，因此這個遮罩 horizon_conflict 現在就是 `0b10000000`

| V | X | | | | | | |
| -- | -- | -- | -- | -- | -- | -- | -- |
| | X | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |

隨後我們也需要判斷對角線方向不可以放的位置，因此我們建立另外兩個遮罩用來判斷不能下子的位置，一個是 slash_conflict 另外一個是 baskslash_conflict， slash 就是註解的那個 `/`，代表右上到左下的對角線， backslash 就是跳脫字元會用到的 `\`，代表右下到左上

slash_conflict 因為第一個位置正好沒有，因此可以記成 `0b00000000` ，這同時是 current_pos `0b10000000` **左移**一個位元形成的遮罩

backslash_conflict 則會是 `0b01000000`（第二個上下行位置因為對角線所以不能選），同時是 current_pos `0b10000000` **右移**一個位元形成的遮罩

根據這些限制，我們選一個跟這些 mask 不會起衝突的位置
就實做面來說，只需要 `if ( !( [要選的位置] & mask ) )` 就好了

| V | | | | | | | |
| -- | -- | -- | -- | -- | -- | -- | -- |
| | | | | | | | |
| | V | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |

現在把 current_pos 更新成 `0b00100000`，同時因為一三左右列都有人了，所以 horizon_conflict 也要加上新的 current_pos 形成 `0x10100000`

| V | | X | | | | | |
| -- | -- | -- | -- | -- | -- | -- | -- |
| | | X | | | | | |
| | V | X | | | | | |
| | | X | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |

此時 slash_conflict 也要隨著新棋子加入更新，更新的方法是把原本的 slash_conflict `0b00000000` 加上新的棋子位置 `0b00100000` 再跟過去一樣， **左移**一個位元形成新的遮罩 `0b01000000`

backslash_conflict 也類似 slash_conflict 的操作方法，原本的 backslash_conflict `0b01000000` 加上新棋子位置變成 `0b01100000`，最後再**右移**一個位元形成 `0b00110000`

以此類推，找到之後的點位置

### 非遞迴程式邏輯

非遞迴的概念其實與遞迴概念非常相像，都是要考慮到「上下直行哪邊可以下」跟「什麼時候找到全部解」這兩件事

不過非遞迴很機車的是需要額外考慮「怎麼回朔回上個狀態」，因為遞迴在函式呼叫結束後會自動根據 call stack 改變執行流程，像是遮罩這種變數因為每層遞迴會維護一個相對獨立不會被污染，但是在非遞迴的狀態下，我們必須手動維護這樣的變數狀態關係

相關實做在 [chenIshi/8queens](https://github.com/chenIshi/8queens)，與遞迴實做比較不同的是，因為遞迴每層會維護屬於自己的棋譜狀態，所以我們只要關心「哪邊不能下就好」

但是在非遞迴實做中，考慮到走到死路需要手動往前回復的情況，直接把「整份圖譜以類似二維陣列的方法紀錄」下來再去推論不能下的點會比較方便

不過實做上其實只有用到一維陣列（不過事實上 C 語言二維陣列也可以手動攤平成一維陣列就是），方法是「其中一維是利用上述 bitwise 的方法以二進位整數紀錄」

### 心得
由於一開始是以遞迴觀念去實做，轉到非遞迴的方式的時候一直在想有沒有辦法不要重複掃那麼多次，同時雖然大觀念都要朝找「哪邊不能下」前進，但是非遞迴的實做個人感覺更重視「棋譜狀態的回復」

目前還沒有做效能分析比較非遞迴與遞迴的差異，個人寫下來的感覺是非遞迴只是在手動實做遞迴部份底層工具幫你作的像是變數生命週期的管理，很繁瑣而且更新順序邏輯要很清楚

考慮到 recursion 需要額外的 function call 成本應該頗高（參考自 [Jserv’s Solution to FizzBuzz 實做分析](https://medium.com/@chen.ishi/jservs-solution-to-fizzbuzz-%E5%AF%A6%E5%81%9A%E5%88%86%E6%9E%90-2ee62a6ce82d) 得到的結論，條件判斷需要的 branch prediction 在現代處理器的效能影響大幅減輕到幾乎可以不用考慮的狀況，倒是函式呼叫像是 memset()，過於頻繁的函式呼叫會導致效能下降）

另外，根據 jserv 老師在[系統課程第一週的問題](/s/SyrZMGYr4#)中提到的「為什麼有效輸入只能在 4 ~ 16」，這部份跟使用到的 int 數值型態也有很大關係

儘管我後面程式主要是使用 `size_t` (`unsigned long`)的資料型態，但是這樣的資料處理還是有可能遇到某些極大數導致運算錯誤