python挑戰骨灰級難度數獨

數獨是一種風靡全球的智力遊戲，數獨是源自18世紀瑞士的一種數學遊戲。是一種運用紙、筆進行演算的邏輯遊戲。玩家需要根據9×9盤面上的已知數字，推理出所有剩餘空格的數字，並滿足每一行、每一列、每一個粗線宮（3*3）內的數字均含1-9，不重複。

數獨盤面是個九宮，每一宮又分為九個小格。在這八十一格中給出一定的已知數字和解題條件，利用邏輯和推理，在其他的空格上填入1-9的數字。使1-9每個數字在每一行、每一列和每一宮中都只出現一次，所以又稱「九宮格」。標準數獨由9行，9列共81的小格子構成。分別在格子中填入1到9的數字，並滿足下面的條件。

• 每一行都用到1,2,3,4,5,6,7,8,9
• 每一列都用到1,2,3,4,5,6,7,8,9
• 每3×3的格子都用到1,2,3,4,5,6,7,8,9

現在我們訪問在線數獨網站（http://www.cn.sudokupuzzle.org/），選擇其中骨灰級難度的數獨，如下圖所示

接下來，我們就用python來解決這個數獨，其中使用的演算法是深度優先搜索。

深度優先搜索演算法（英語：Depth-First-Search，簡稱DFS）是一種用於遍歷或搜索樹或圖的演算法。沿著樹的深度遍歷樹的節點，儘可能深的搜索樹的分支。當節點v的所在邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重複以上過程，整個進程反覆進行直到所有節點都被訪問為止。屬於盲目搜索。深度優先搜索是圖論中的經典演算法，利用深度優先搜索演算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。

在程序中用time計時的起始時間是從第一行import time模塊之後就開始了，運行結果如下：

python挑戰骨灰級數獨

網站提供答案如下

python挑戰骨灰級數獨

查看答案發現求解正確，至此有沒有感覺到python的強大，骨灰級的數獨都不在話下，那麼入門級的更是小菜一碟啦，代碼獲取請看公眾號《python練手項目實戰》回復「數獨」，從此告別數獨難題，開啟數獨稱霸之路。

參考：

https://blog.csdn.net/littlethunder/article/details/9749509

https://www.cnblogs.com/LukeStepByStep/p/5694454.html

推薦閱讀：