雨恩的生活日誌

 小孩小四時的數學題目,  想不開的老爸：到底是誰在念小學？  當時, 忍不住寫了程式來解問題, 想法是列出所有排列可能再一一比對符合條件者, 這個方法會因為列出所有可能排列的清單太多, 而造成CPU使用率相當的高! 也必須等待較長的時間才能得到解答。 研究了數獨的程式寫法後,  數獨(Su Doku)用電腦來解 , 發現用recursion的技法效率相當的不錯, 即使使用Python來寫也可以很快。 之前方法(test3.c)需要36秒才解出答案, 即使改為多緒寫法也要10秒。改用recursion方法來寫後, CPU使用量少到看不到, 答案也是立即閃現。即使用Python來寫, 也是馬上得到答案。這個Python程式放在github: math_junior.py (對應的C語言版本程式:  math_junior.c  , 其實C的執行速度還是快的多) 程式修改的想法如下: 因為和數獨的玩法很像, 都是方格裡填數字, 只是數獨的要求是橫列和直欄及3x3小方格裡的數字都不能重複; 而小四數學題目是橫列格子裡數字加總要等於指定的某個數值, 以及直欄格子裡的數字加總要等於指字的某個數值, 還有格子裡的數字要是1-16都不能重複。這不是很像嗎? 差別只是方格大小不同, 填入格子的數字要滿足的條件不同而已。 因此, solve()裡針對差異改了2個地方, 如下圖: 然後, 資料存放的陣列, 配合要求, 改了一下: 因應題目4x4的方格每橫列加總要等於該橫列指定的加總值, 所以直接把方格加大一些, 多出來的位置拿來放置指定的加總值 (如圖, 橫列的加總值以及直欄的加總值)。 最後, possible(y, x, n)裡要檢查同樣有3個條件, 1. 填入1-16不能重複, 這可以由#can't repeat之下的nested loops 來完成檢查工作。 然後橫列加總的條件有點挑戰! 一開始, 我用傳入的行列值(y, x)來判斷當到達行=3時, 再來檢查橫列加總是否符合條件, 卻總算出錯誤的答案, 而且跑很久! 後來才想到, 這支程式的solve()只找空格來嘗試可能答案, 而題目本身原本在四個角落就已經填了數值! 所以solve()會跳過這4固已填的格子; 這樣一來, 就不會檢查到加總條件是否符合。所以修改成先檢查...

 之前兒子在書局買了一小本的數獨, 無事時拿來玩玩。規則很簡單, 如下圖, 共有9x9的格子, 這個grid又均分成9個sub-grid, 每個sub-grid大小為3x3。每格只能填入1-9的數字, 而且每横列的數字不能重複, 同樣每直欄的數字也不能重複, 還有每個sub-grid內的數字也不能重複。如圖, 一開始都會先有填好的數字, 稱為clue, clue愈多愈好解! 我們玩了一下, 容易的可以在20分鐘左右解完。難的可能要40分鐘以上, 真是kill time的好方法!  但有一天, 小兒突發奇想, 出了一個題目給我解, 哇! 居然解不出來! 這下子是不是顯得我能力不足? (其實是題目出的不好!) 為了證明是題目出的有問題, 我必須找出所有可能的解, 以說明給的clue不足以解出唯一解! 當然聰明的方法是用電腦來解, 用手算是很花時間的。 其實可以google到很多人寫的程式, 第一個找到的程式是: a really simple sudoku solver in pure c 這個程式可以找出解, 但也只會找到一個解! 因為正常來說, 數獨出題的人會只出有唯一解的題目, 所以只找一個解的想法是合理的。但是碰到小朋友這種出題者, 就不會只有唯一解了! 因此, 我就想要自己改一下這支程式來找出所有解!  當然, 還是先google一下, 是不是已經有人已經先寫好了。結果先看到以下的問答: Sudoku multiple solutions C 就是有人寫了一個類似的程式, 然後問怎麼改成可以解多個解, PioneerAxon則回答, 1. solveSudoku()在return 1之前要把value重置回0, 2. 所有格子都填完就印出結果。雖然沒有直接幫忙把程式改完, 但這些提示對我很有助益! 然後, 他還給了一個連結, 指到一個sudoku-solver的程式專案。我也去看了這個專案, 試了一下程式, 它確實可以非常快地找到所有的解。不過, 這支程式的寫法稍為複雜了一些些。我還是以前面的那支程式來改寫, 首先要先看懂程式的邏輯是什麼, 簡單說是利用recursion來幫我們產生一個tree search, 將所有可能都走遍, 再排除所有不對的情況後, 自然會找到所有可能的解。以下影片, 應有助更深入的理解。 所以依Pionee...