# [2020q3 Homework (quiz9)](https://hackmd.io/@sysprog/2020-quiz9)
contributed by < `zhu849` >

## 測驗 `2`
依循 [leetcode 37. Sudoku Solver](https://leetcode.com/problems/sudoku-solver/) 解決數獨問題

### 範例解：

typedef struct {
    uint16_t row[9], col[9], box[9];
} masks_t;

const uint16_t ALL_NUMS = 0x1FF;

static inline int bi(int x, int y)
{
    return (y / 3) * 3 + (x / 3);
}

static bool solve(char **board, masks_t *m)
{
    for (int y = 0; y < 9; ++y) {
        for (int x = 0; x < 9; ++x) {
            if (board[y][x] != '.')
                continue;

            int b = bi(x, y);
            uint16_t posmoves = m->row[x] & m->col[y] & m->box[b];
            while (posmoves) {
                size_t n = __builtin_ctz(posmoves);
                uint16_t k = ~(1U << n);
                board[y][x] = '1' + n;
                m->row[x] &= k, m->col[y] &= k, m->box[b] &= k;
                if (solve(board, m))
                    return true;
                m->row[x] |= ~k, m->col[y] |= ~k, m->box[b] |= ~k;
                posmoves &= posmoves - 1;//Q1
            }
            board[y][x] = '.';
            return false;
        }
    }
    return true;
}

void solveSudoku(char **board, int boardSize, int *boardColSize)
{
    masks_t m;

    for (int i = 0; i < 9; ++i)
        m.row[i] = m.col[i] = m.box[i] = ALL_NUMS;
    for (int y = 0; y < 9; ++y) {
        for (int x = 0; x < 9; ++x) {
            if (board[y][x] != '.') {
                int n = board[y][x] - '1';
                uint16_t k = ~(1U << n);
                m.row[x] &= k, m.col[y] &= k, m.box[bi(x, y)] &= k;
            }
        }
    }

    for (int y = 0; y < 9; ++y) {
        for (int x = 0; x < 9; ++x) {
            if (board[y][x] != '.')
                continue;
            uint16_t mask = m.row[x] & m.col[y] & m.box[bi(x, y)];
            if ((mask & (mask - 1)) == 0) { //Q2
                size_t n = __builtin_ctz(mask);
                uint16_t k = ~(1U << n);
                board[y][x] = '1' + n;
                m.row[x] &= k, m.col[y] &= k, m.box[bi(x, y)] &= k;
            }
        }
    }

    solve(board, &m);
}

### 數獨舉例
#### 舉例
#### 解答

### 程式碼運作原理
* Line 2~4：定義一個 `masks_t` 的 type 便於紀錄整個數獨表格在三種不同角度觀察的狀態，總共有 9 個 row, col, box
* Line 6：定義一個 0x1FF 便於初始化 `masks_t` 內每格的值，剛好有 9 個 bits 為1，也因為這樣所以需要用 uint_16 才能容納
* Line 8~11：用於計算在 `masks_t` 中以 `box` 角度紀錄的 index，因為 `box` 在平面上是二維的，但是用一維陣列儲存
* Line 41~44：初始化 `m` 結構內的 `row`, `col`, `box` 陣列
* Line 45~53：將 board 上已填入的資訊更新到 `m` 中對應的 `row`, `col`, `box` 陣列
* Line 48~49：若 board 內數字是 (char)'5'，則 n 會為 (int)4， k 會是 0x1111111111101111
* Line 50：利用 K 的 and operation 將 `row`, `col`, `box` 對應的 bit 做更新
* Line 55~67：初步檢查 board 上的 `row`, `col`, `box` ，利用現階段已知條件填入能夠確定的格子(某格已經能知道是某數，不用透過遞迴猜測)
* Line 57~58：若格內是 digit 則略過
* Line 59：將 `row`, `col`, `box` 做 and operation 得到一個 mask ，這個 mask 可以知道哪些 digit 有可能是滿足三者條件的答案
* Line 60：利用 x 和 x-1 做 and operation 確認該值的二進位型態是否僅有一個 1's bit(只有這個情況會使條件為 true，是 bitwise operation 的特性)
* Line 61-64：計算該 bit 後有幾個 0 存在 n，利用 n 去製作一個 k mask，用 k mask 將 `row`, `col`, `box` 中對應的 bit 消除為 0
* Line 69：遞迴猜測可能的解
* Line 21： `posmoves` 計算意義同 Line 59 的 `mask`，目的是得知哪些 digit 有可能是滿足三者條件的答案
* Line 22~31：直到 `posmoves` 中所有可能的遞迴猜測完畢後，才會跳出迴圈
* Line 23-26：和 line 48-50 同理，先嘗試填入該格數字
* Line 27：利用填入數字遞迴確認是否能夠填完整張 board，若可以則回傳 true
* Line 29：若沒辦法順利填入則需要將狀態恢復成遞迴前的狀態，將 `row`, `col`, `box` 和 ~k 做 or operation 即可復原
* Line 30：這裡利用 x 和 x-1 做 and operation 去消除最右邊的 1
* Line 32：若該格的內容皆無法順利填入，則復原為 '.'
### 結果