演算法實踐數獨的基本解法

數獨（Sudoku）是一種運用紙、筆進行演算的邏輯遊戲。玩家需要根據9乘以9盤面上的已知數字，推理出所有剩餘空格的數字，並滿足每一行、每一列、每一個粗線宮內的數字均含1到9，不重複。 每一道合格的數獨謎題都有且僅有唯一答案，推理方法也以此為基礎，任何無解或多解的題目都是不合格的。

數獨的基本解法就是利用規則的摒棄法。每一行稱為數獨的行，每一列稱為數獨的列，每一個小九宮格稱為數獨的宮。數獨的基本規則就是每一行、每一列、每一宮中，1到9這9個數字都只出現一次。那些只能填一個數字的空白單元格，我們稱之為唯一數單元格。

解題的順序，就是從唯一數單元格開始，由於唯一數單元格只能填一個數，故先在這個單元格里填數。在這個單元格里填數，由於規則的定義，那麼這個單元格所在的行、所在的列、所在的宮的其他單元格就不能再填這個數了。這些單元格能填的數的可能性就少了。有可能會產生新的唯一數單元格。

在相當的一些的數獨題目中，從唯一數單元格開始填數，不停的在唯一數單元格填數就可以把數獨解出來。如果在解題的過程中，發現某些空白單元格沒有數字能填這樣的單元格稱之為無解單元格，那就說明：要麼這個數獨沒有解；要麼之前的解題過程有問題，需要返回檢查之前的解題過程檢視。

但是還有不少的數獨的題目，在解題的過程中，在還有空白單元格的情況下，卻找不到唯一數單元格，也就是意味著每個空白單元格中能填的數字至少有2個。而出現無唯一數單元格的這種狀況，我們可以找到其中一個可能數最少的空白單元格（這個沒有定論，可以是可能數最少的空白單元格；

也可以是第一個空白單元格；也可以是可能數最多的空白單元格，選哪個空白單元格對後面的解題是否有影響，沒有證明過，不好妄下定論。憑感覺選可能數最少的空白單元格是最好的選擇），由於能填的數字不止一個，先把當前的狀態儲存起來，再在能選的數字中選擇一個數字填寫（從小到大選擇），然後繼續求解下去。如果能解出最後的結果，說明當前的選擇是正確的；如果後面的求解過程有問題，說明當前的數字的選擇有問題，那麼再挑選另一個數填寫，繼續求解。

如果，所有的選擇都求不出最後的結果，還是說明：要麼這個數獨沒有解；要麼之前的解題過程有問題，需要返回檢查之前的解題過程檢視。如此反覆，直到求出最終的答案。會有種極端的情況（可能性不大）。那就是在當前的空白單元格的所有可能的數字都選擇了一遍，都沒有解。而之前又沒有出現無唯一數單元格的狀況。那就說明這個數獨根本就無解。