數獨(Su Doku)用電腦來解
之前兒子在書局買了一小本的數獨, 無事時拿來玩玩。規則很簡單, 如下圖, 共有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一下, 是不是已經有人已經先寫好了。結果先看到以下的問答:
就是有人寫了一個類似的程式, 然後問怎麼改成可以解多個解, PioneerAxon則回答, 1. solveSudoku()在return 1之前要把value重置回0, 2. 所有格子都填完就印出結果。雖然沒有直接幫忙把程式改完, 但這些提示對我很有助益! 然後, 他還給了一個連結, 指到一個sudoku-solver的程式專案。我也去看了這個專案, 試了一下程式, 它確實可以非常快地找到所有的解。不過, 這支程式的寫法稍為複雜了一些些。我還是以前面的那支程式來改寫, 首先要先看懂程式的邏輯是什麼, 簡單說是利用recursion來幫我們產生一個tree search, 將所有可能都走遍, 再排除所有不對的情況後, 自然會找到所有可能的解。以下影片, 應有助更深入的理解。
所以依PioneerAxon的提示, 主要就是改2個地方, 改好的程式放在github:
------- modified sudoku solver for all possible solutions --------
然後我發現這支改寫後的程式解題非常的快, 以我家小朋友出的題目來說可以找到6個可能解, 根本用不到1秒, 程式一跑, 答案立刻出來。觀察CPU使用率, 根本看不出來有用到! 不是在自跨我程式改寫的多好, 而是這種recursion的寫法來解如此多種可能排列的問題, 看來效率是真的不錯!
因此, 原本都以C語言來寫程式的想法有點動搖, 就去找看看Python的寫法, 看到一篇文章:
Learning Recursive Algorithm with Sudoku Solver in Python
作者Ekapope Viriyakovithya介紹 University of Nottingham的Professor Thorsten Altenkirch的一支影片, 他很有條理的介紹了如何用Python (Jupyter notebook環境)來寫解Su Doku的程式, 程式使用同樣的recursion方法, 非常簡潔的寫完, 而且執行速度也是快的很! 而且也是可以解多個可能解, 寫法和之前那支C的寫法大同小異。小異之處, 正好用來思考, 為什麼可以如此寫, 也更加深入理解程式運作的方式。用來解小朋友給的題目, 如下圖, 可以看到解出6個可能解!
用我改寫的C程式, 以及別人寫的sudoku-solver專案(也是C程式), 還有Professor Thorsten Altenkirch寫的Python程式, 來解小朋友給的題目都是得到同樣的6個可能解。這應該可以說明我改寫的程式沒錯了吧! 小修改的這支Python程式也放在github:
但這個有2個可能解的題目, 它只給了一個答案!
留言