# Bitwise N-Queens
###### tags: `C LANGUAGE`

:::success
Bitwise Operator 一直是自己不太熟悉的一個部份，藉由閱讀`jgpettibone` 的 Bitwise N-Queens，並且將其內容做成筆記方便日後複習。
:::
[jgpettibone的文章](http://jgpettibone.github.io/bitwise-n-queens)

---
## N-Queens
N-Queens 這個問題早是由 8-Queens 問題延伸而來。在西洋棋的規則中 Queen 能夠吃掉在同 Column 跟同 Row 還有在其左右對角線的棋子。

而 8-Queees 問題就是在，8x8 的棋盤上有多少解是能夠讓8個皇后同時生存，而這個問題是 Backtracking 演算法的一個相當經典的應用。

#### BackingTracking (回溯法)
簡單介紹就是在無窮枚舉遞迴的過程中，在遞迴下去前檢查答案是否是自己要的，如果不是就不在往下跑，這樣就能減少所多無意義的運算，有點類似 Branch and Bound。

### Bitwise Implement
接下來就直接進入主題，看看 `jgpettibone` 是如何 Implement。

#### Board Position
取代利用陣列來表示 Queen 的位置，這邊利用二進位的1來表示目前的位置， 例如如果是一個4x4的棋盤，我們用1、2、4、8的二進位來表示位置，然後在用 Left shift `<<`來作 Queen 位置的操作。
:::info
0001 1 這代表 Queen 目前在最後一位。
0010 2
0100 4
1000 8

這樣的方法，可以利用 `AND` 來判斷 Queen 是否有在同 Column 的狀況。
:::

#### Conflicts 處理
因為我們是用二的倍數來操作所以不用擔心 Row 是否有 Conflict 的問題，要注意的是 Column 跟左右對角線。
:::success
0010 目前 Queen 要放的位置
0100 Queen 跟右下角衝突
0001 與下面對角線衝突
0010 與第一個 Column 衝突
:::
從上面的例子可以看到`0010`這個位置有兩種 Conflict 分別是與右下角衝突跟 Column 衝突，那要怎找到一個適合的位置？
:::success
0100
0001
1000
一一一
1101
:::
可以發現原本的 Queens 存在的位置做過 `OR` operator 之後，會得到1101，這個時候從簡單的4x4中可以觀察到在0010是唯一能夠放 Queen 的地方，如果我們將1101跟0010做 `AND` operator 之後。
:::success
1101
0010
一一一
0000
:::
可以得到0000，那就代表已存在的所有 Queens 做 `OR` 後得到的值再跟欲放入 Queen 的位置做 `AND` 如果得到的值都為0就代表此位置是可行。

#### 實際作法
Step One: 初始化三個變數分別代表左對角線、右對角線、Column 會遇到 Conflict 的位置。

Step Two: 將這三個變數做 OR operator 之後，就可以利用這個去對新的位置用 `AND` operator 判斷是否有 Conflict。

Step Three: 根據新進來的Row來變更那三個變數。

:::success
左對角線
0001 上一個左對角線參數
1000 現在進來的 Row
一一一
1001 作 OR operation
0100(1) 然後向右 shift 一個 bit
這樣就可以得到下一個 Row 進來是否有 Conflict 的判斷。
:::

:::info
右對角線
0100 上一個右對角線參數
1000 現在進來的 Row
一一一
1100 作 OR operation
(1)1000 然後向左 shift 一個 bit
這樣就可以得到下一個 Row 進來是否有 Conflict 的判斷。
:::

:::danger
Column
0010 上一個 Column 參數
1000 現在進來的 Row
一一一
1010 作 OR operation
這樣就可以得到下一個 Row 進來是否有 Conflict 的判斷。
:::

以上就是 Bitwise N-Queens 簡單的方法介紹，以下會附上 Implement 的 Code

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

//this struct record the conflict information
typedef struct quene_propety
{
    int minDiagnoalConflict;
    int maxDiagnoalConflictm;
    int ColConflict;
    int n_number;
} quene_pro;



void quene_count(int current_row ,quene_pro *quene, int *solution_count)
{
    //the current initial is zero
    //if the current row past the n_number mean find the one solution
    //solution_count plus one which mean the solution number  
    if (current_row == quene->n_number){
        (*solution_count)++;
        free(quene);
        return;
    }

    int conflicts = quene->maxDiagnoalConflictm | quene->minDiagnoalConflict  | quene->ColConflict;

    // first iteration is 1 and multiple 2 to the next bit 
    // if n = 4 , (1 << 4) = 10000 is 16 so the most left bit is 1000 = 8
    // the quene position = 1000 [0100 = 4 0010 = 2 0001 = 1] 
    for (int quene_position = 1; quene_position < (1 << quene->n_number); quene_position *= 2){
        if (!(conflicts & quene_position)){
           quene_pro *q_new = malloc(sizeof(quene_pro));
           q_new->maxDiagnoalConflictm = (quene->maxDiagnoalConflictm | quene_position) >> 1;
           q_new->minDiagnoalConflict  = (quene->minDiagnoalConflict  | quene_position) << 1;
           q_new->ColConflict = quene->ColConflict | quene_position;
           q_new->n_number = quene->n_number;
           quene_count(current_row + 1 ,q_new, solution_count);
        }       
    }
}

int quene_cross(int *number)
{
    int solution_count = 0;
    quene_pro p = {0, 0, 0,  *number};
    quene_count(0, &p, &solution_count);
    return solution_count;

}

int main()
{
    int n_number = 0;
    int counts = 0;
    scanf("%d", &n_number);
    counts = quene_cross(&n_number);
    printf("%d Solutions\n", counts);
    return 0;
}