算法實踐數(shù)獨的基本解法

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

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

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

　　在相當?shù)囊恍┑臄?shù)獨題目中，從唯一數(shù)單元格開始填數(shù)，不停的在唯一數(shù)單元格填數(shù)就可以把數(shù)獨解出來。如果在解題的過程中，發(fā)現(xiàn)某些空白單元格沒有數(shù)字能填這樣的單元格稱之為無解單元格，那就說明：要么這個數(shù)獨沒有解；要么之前的解題過程有問題，需要返回檢查之前的解題過程查看。

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

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

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

聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com