37. 數獨解謎 part1 (Time Limit Exceeded)
=========================================================
難度: Hard
類型: Matrix
CPP程式下載: 37_1.cpp
=========================================================
第一篇文章就挑數獨, 因為小孩的緣故, 有陪著玩速讀。這篇文章適合給剛學寫程式的人看。
大家都喜歡最佳解, 那為何我挑一個submission會超時的程式來寫在部落格?
因為這個解法最直覺, 才是我們平常在寫數獨題目時, 大腦的思考模式。
=========================================================
前情題要:
數獨, 在 9*9 的格子內填上 1~9 的數字
1. 每一行的 9 個數字不能重複
2. 每一列的 9 個數字不能重複
3. 切成 9 個 3*3 的子矩陣內的 9 個數字不能重複
=========================================================
思考方式:
因為先做過
所以先把每一行 (共九行), 每一列 (共九列), 每個 3*3 子矩陣 (共九個), 總共 27 個, 裡面哪些數字已用過, 那些數字沒用過, 都記錄起來了。
接著就是每個空白格 ( 9*9 矩陣中值為 '.' ) 去尋找, 是不是有某一個 (1~9) 的數, 且唯一, 剛好在該列, 該行, 該 3*3 子矩陣中, 都不存在。如果找到, 就確定的填進數獨的格子中。一直不斷的重複尋找, 慢慢的填進越多的數字, 直到所有的格子都填滿。
註: 每次找到唯一解的格子時, 記得更新該行, 該列, 該 3*3 子矩陣的數字出現紀錄。
=========================================================
複雜度思考:
缺點:
一開始很多格子可以選擇的數字很多, 並不是唯一選擇。隨著確定的數字變多, 很多之前不確定的格子, 也逐漸能夠確定下來。總共要跑 n 個迴圈的 9*9 次。
很明顯的, 有很多重複的運算, 絕對不會是最佳解, 也有心理準備很大機率提交之後Runtime會超時。
優點:
1. 跟平時寫數獨的思考模式一致, 容易理解, 至少能寫出對的答案。憑藉著現今電腦的運算速度, 仍能快速地找到答案。
2. 因為有先算過行, 列, 子矩陣的數字出現表, 這方法比每個空格都暴力的去嘗試 1~9 每個數字要快。
3. 每填進一個確定的空格, 都立刻更新該行, 該列, 該子矩陣的數字出現表, 後面需要算的數字越來越少, 速度逐漸變快。
=========================================================
結果:
如預期的出現了 Runtime 超時的結果。
進一步的除錯時, 發現並不是程式寫錯, 而是遇到了所有確定的空格都填完後, 剩下的空格都不是唯一解的狀況。( num_filled=47 就沒有繼續增加了。每一個 choice 的值不是唯一解, 也就是說, 非 1, 2, 4, 8, 16, 32, 64, 128, 256。)
那麼看來非要做 DFS (Deep First Search) 不可了!
