數獨 回溯法求解

數獨問題大家都很熟悉，很喜歡挑戰。但解決此問題極其需要耐心和邏輯，正因為此，解決完才會享受到那種成就感的樂趣。本文利用Python3 解決數獨問題，雖然過程不一樣，但結果還是會讓人感受一樣的樂趣。

問題描述

根據九宮格盤面上的已知數字，推理出所有剩餘空格的數字，並滿足每一行、每一列、每一個宮(3 * 3)內的數字均含1至9這9個數字。

解決思路

對每個空格尋找到其可能的數字，選擇有可能的數字個數最小的空格，為其添加數字，並記錄此狀態，以此類推，當無解時則返回上一個節點狀態，直到全部空格填充完畢。

Python3代碼

利用Pandas讀取存放數獨題目的Excel文件，利用Numpy進行運算。首先讀取數獨題目。

Excel文件中的數獨題目如下所示：

程序列印的結果為：

Pandas讀取數據時，若最後一行沒有數字，則不會讀取，因此需要判斷讀取的題目是否完整。

按照每行、每列、各宮內不能包含重複數字，但又需要包含全部數字的原則，為沒有數字的空格計算其可以填寫的數字。

針對題目中的每一個空格，得到其可以填寫的數字集合，並形成字典。

在所有的空格中，選擇一個jieti值最小的空格。

準備工作就緒，開始實現回溯法。用字典形式存儲題目填充完數字後的狀態。

本程序中實現狀態轉移時採用的尾遞歸方式，但是Python內部沒有對這種形式進行優化，並且最大遞歸層數大概是999，超過這個數程序會報錯，這種情況可通過裝飾器方法解決。本文採用的方法比較投機，就是在達到最大遞歸層數之前，記錄下當時狀態，退出遞歸，然後在重新進入遞歸，稱其為循環一次。

下面給出主要函數。

第一次循環

實現無數次循環直到解決的函數

最終結果的輸出程序

程序運行的結果：

GIF

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！