# 2019q1 Homework3 (review)
contributed by < `LiunuXXX` >

## 預期目標

* 回顧 Linux 課程進行狀況
* 隨堂測驗回顧
* 誠實面對自己

## 作業要求

* 從 [第 1 週](https://hackmd.io/s/SyrZMGYr4), [第 2 週](https://hackmd.io/s/H1Pik8M8E), [第 3 週(上)](https://hackmd.io/s/S1weT4iLE), [第 3 週(下)](https://hackmd.io/s/SkrVSKiU4), [第 4 週(上)](https://hackmd.io/s/H1KLoTEv4), [第 4 週(下)](https://hackmd.io/s/BJKk1ANv4) 選出你感興趣的 3 個題組進行作答，並且回答附帶的「延伸問題」
* 比照 [課前測驗參考解答: Q1](https://hackmd.io/s/ByzoiggIb) 和 [對 Linked List 進行氣泡排序](https://hackmd.io/s/BklGm1MhZ) 的模式來撰寫共筆，需要詳細分析自己的想法、參閱的材料 (包含 C 語言規格書的章節)，以及==進行相關實驗==
* 若有不能理解的部分，請標註出來。善用 HackMD 的語法 `:::info` 和 `:::` 標註你的提問
:::info
像是這樣標註提問
:::

## 作業區
---
### 2019q1 第一週測驗題

### 測驗 `1`

西洋棋中的皇后可以直線前進，吃掉遇到的所有棋子，如果棋盤上有 8 個皇后，則這 8 個皇后如何相安無事地放置在棋盤上，1970 年與 1971 年， E.W.Dijkstra 與 N.Wirth 曾用這個問題來講解程式設計之技巧。

關於棋盤的問題，都可以用遞迴求解，然而如何減少遞迴的次數？在八個皇后的問題中，不必要所有的格子都檢查過，例如若某列檢查過，該該列的其它格子就 不用再檢查了，這個方法稱為分支修剪。


所以檢查時，先判斷是否在已放置皇后的可行進方向上，如果沒有再行放置下一個皇后，如此就可大大減少遞迴的次數，例如以下為修剪過後的遞迴檢 查行進路徑：

8 個皇后的話，會有 92 個解答，如果考慮棋盤的旋轉，則旋轉後扣去對稱的，會有 12 組基本解。 [ [source](https://openhome.cc/Gossip/AlgorithmGossip/EightQueen.htm) ]

透過 [bitwise 演算法](http://jgpettibone.github.io/bitwise-n-queens/) 改寫為以下 C 程式:

#include <stdio.h>
#include <stdlib.h>

static int sol_count = 0;
void recursive_solver(int row, int maj_con, int min_con, int col_con, int n)
{
    int queen_position;
    int conflicts = min_con | maj_con | col_con;
    int i = 0;

    min_con &= 65535;
    while (i < n) {
        queen_position = 1 << (A1 - i);
        if (!(queen_position & conflicts)) {
            if (row == n - 1)
                sol_count++;
            else
                recursive_solver(row + A2, (maj_con | queen_position) >> A3,
                                 (min_con | queen_position) << A4,
                                 col_con | queen_position, n);
        }
        i++;
    }
}
void solve_queens(int n)
{
    int minor_dconflict = 0, major_dconflict = 0, column_conflict = 0;
    recursive_solver(0, column_conflict, major_dconflict, minor_dconflict, n);
    printf("solutions = %d\n", sol_count);
}

其中 `solve_queens` 的參數 `n`，數值介於 `4` 到 `16`。
請補完程式碼。

==作答區==

A1 = ?
* `(a)` 16
* `(b)` 15
* `(c)` 14
* `(d)` 13
* `(e)` 12
* `(f)` 11
* `(g)` 10
* `(h)` 9
* `(i)` 8

A2 = ?
* `(a)` 7
* `(b)` 6
* `(c)` 5
* `(d)` 4
* `(e)` 3
* `(f)` 2
* `(g)` 1
* `(h)` 0

A3 = ?
* `(a)` 7
* `(b)` 6
* `(c)` 5
* `(d)` 4
* `(e)` 3
* `(f)` 2
* `(g)` 1
* `(h)` 0

A4 = ?
* `(a)` 7
* `(b)` 6
* `(c)` 5
* `(d)` 4
* `(e)` 3
* `(f)` 2
* `(g)` 1
* `(h)` 0

### Solution
#### A1
* 利用 conflicts 記錄會和皇后產生衝突的位置

int conflicts = min_con | maj_con | col_con;

* 隨著遞迴不斷增長，min_con 可能會超出棋盤邊界，而 solve_queens 的參數介於 4~16，棋盤應為 16x16，因此用 `0xffff`(65536) 去 mask。

接著看 while 迴圈:

    while (i < n) {
        queen_position = 1 << (A1 - i);
        if (!(queen_position & conflicts)) {
            if (row == n - 1)
                sol_count++;
            else
                recursive_solver(row + A2, (maj_con | queen_position) >> A3,
                                 (min_con | queen_position) << A4,
                                 col_con | queen_position, n);
        }
        i++;
    }

* 皇后的位置在 15~0 這 16 個位置，而 `queen_position` 又隨著 while 迴圈減少，因此最大位置應該是在 15，也就是 `1000 0000 0000 0000`

* 故得 A1 = 15

#### A2

recursive_solver(0, column_conflict, major_dconflict, minor_dconflict, n);

                recursive_solver(row + A2, (maj_con | queen_position) >> A3,
                                 (min_con | queen_position) << A4,
                                 col_con | queen_position, n);

由題目的遞迴參數可知，row 數由 0 逐漸增加，可知為從第
一 row 往下逐列呼叫。

* 故 A2 = 1

#### A3,A4

                recursive_solver(row + A2, (maj_con | queen_position) >> A3,
                                 (min_con | queen_position) << A4,
                                 col_con | que

* 假設 queen 在第一列的 15 位置 (`1000 0000 0000 0000`)，則遞迴呼叫下一 row 時，conflict 位置為 14 的位置 (`0100 0000 0000 0000`)，即右移一個 bit。
* 故 A3 = 1
* 類似 major conflict，但 min conflict 是左移
* 故 A4 = 1