=========================================================
前情題要:
數獨, 在 9*9 的格子內填上 1~9 的數字
1. 每一行的 9 個數字不能重複
2. 每一列的 9 個數字不能重複
3. 切成 9 個 3*3 的子矩陣內的 9 個數字不能重複
=========================================================
思考方式:
每一行, 譬如第 j 行, board[0~8][j]
每一列, 譬如第 i 列, board[i][0~8]
k=0~8 共九個 3*3 子矩陣, 表示為 x=((k%3)*3)~(k%3)*3+3, y=((k/3)*3)~((k/3)*3+3)
每行, 每列, 每個子矩陣, 1~9 數字都只能出現一次。
所以初始化 {1, 1, 1, 1, 1, 1, 1, 1, 1}, index 0~8 的值都是1, 代表 1~9 數字可出現的次數為 1。
譬如某一行出現了數字三, 然後這行剩下的位置都不能再出現3, 但其他數字都還能出現一次。就成了 {1, 1, 0, 1, 1, 1, 1, 1, 1}
檢查每行, 每列, 每個子矩陣, 如果同一數字出現兩次, 就回報 false, 如果檢查完全部都沒發現 false, 就回報 true。
=========================================================
複雜度思考:
九行, 九列, 九個子矩陣, 共27次檢查, 每次檢查9個位置。9*27 = 243。
總共也才算 243 次, 複雜度算低的, 就沒再思考如何簡化了。
=========================================================
結果:
Runtime: 0 ms, Beats: 100%
Memory: 21.54 MB, Beats: 92.04%
