37. 數獨解謎 part2 (Beats 97.52%)
=========================================================
難度: Hard
類型: Matrix
CPP程式下載: 37_2.cpp
=========================================================
第二篇文章仍然是數獨。這篇文章是一個很棒 recursive (遞迴) 使用函式的例子。
在 "37. 數獨解謎 part2" 中, 我們發現有的空格是有多種可能的值, 所以必須先試著填值, 然後看後續有沒有發現錯誤。在遞迴的呼叫函式的同時, 自然而然的前面試著填值的地方與他的位置, 都自然的被 stack 保留了起來。
=========================================================
前情題要:
數獨, 在 9*9 的格子內填上 1~9 的數字
1. 每一行的 9 個數字不能重複
2. 每一列的 9 個數字不能重複
3. 切成 9 個 3*3 的子矩陣內的 9 個數字不能重複
=========================================================
思考方式:
因為先做過
所以先把每一行 (共九行), 每一列 (共九列), 每個 3*3 子矩陣 (共九個), 總共 27 個, 裡面哪些數字已用過, 那些數字沒用過, 都記錄起來了。
接著要做遞迴, 為了方便寫遞迴的函式 fill_next(), 以及讓原本的 solveSudoku() 函式保持簡潔, 所以把檢查該位置是否是空格 '.', 以及每個位置都嘗試 1~9 的可能性, 這些都實作在遞迴的函式裡。
遞迴函式輸入參數有 location (y, x), 以及同時也為輸出參數的 board 矩陣。如果這個位置已經是題目給的固定值, 那就 fill_next(next_y, next_x), 這邊的 next_y, next_x 就是原本位置的右邊格子, 如果右邊已經到邊界, 就設為下一列的第一個格子。如果 fill_next() 回傳的值是 false, 代表後面遞迴嘗試各種可能性都失敗, 那麼就回傳 false, 回到上一層另外找尋可能的解。如果 fill_next() 回傳的值是 true, 代表現在的這個嘗試是對的方向, 就回報 true。
遞迴函式何時會回傳 false 呢? 除了遞迴呼叫時收到 false 的回傳之外, 還有就是嘗試了在目前的空格無論填 1~9 都不適合, 該行, 該列, 該 3*3 子矩陣都有發現重複的值。這代表前面的格子試著填的值不對, 回到前一個輪迴去試其他可能的值。
solveSudoku() 函式, 在處理完 27 個數字使用表之後, 只要呼叫 fill_next(board,0,0) 就可以開始讓該函式不停的自我遞迴呼叫, 直到找出正確解答。
到這裡看似完整, 實際上我們遺漏了一點。透過 debug 列印 location 位置, 以及 runtime error 發現, 有 illegal access, 代表我們訪問的矩陣超過了他的 9*9 大小。回想一下, 我們忘了煞車了, 當我們已經嘗試填完最後一個格子 (8,8), 就已經找到正解了, 下一個格子 (9,0) 是不需要再 fill_next() 了, 這時候回傳 true 就好。
註1: 每次試著填可能值到格子時, 記得更新該行, 該列, 該 3*3 子矩陣的數字出現紀錄。
註2: 每次發現 fill_next() 回傳是 false 時, 如果目前的格子原本是 '.' , 記得把目前 (y, x) 已經填的值改回 '.' , 並且 該行, 該列, 以及該 3*3子矩陣也要還原成未出現過該次填的值。
=========================================================
複雜度思考:
缺點:
1. 花了一些記憶體空間去存 每行, 每列, 每個矩陣中, 1~9 出現與否。共 27 * 9 個 sizeof(type)。
我這邊用 int, 實際上是可以改用一個 byte (char 或 unsigned char) 去存。
2. 填值時要更新相關的3個陣列, 發現 fill_next() 回傳為 false 時也要記得還原相關的3個陣列。
3. 遞迴呼叫必須邏輯清晰, 才不會出錯。
優點:
1. 儲存了27個數字出現與否的陣列。因此每次要在空格填值時, 不須重覆再計算, 能直接從 27 個陣列去判斷。
2. 遞迴呼叫, 簡化程式架構。
=========================================================
結果:
Runtime: 48 ms, Beats: 97.52%
Memory: 9 MB, Beats: 10.35%
