數獨難易度分級
不才的老葉!
被罵了,拖不住了,再不上貼,就反了。好吧!就來談談小周最近在研究的數獨難易度的客觀條件,提供筆者的個人淺見。
許多人會以數獨初盤上的提示格多寡來認定該數獨的難易度,原因很簡單,需要解出較多的解題格,相對需要花費較多的時間來解題。
這個概念基礎是對的,尤其是當尚未解題時看到初盤時的的基礎判斷。
例如一個數獨初盤的提示格為20個,另一個數獨盤的提示格為30個,若兩個數獨的解題順序及解題技巧相似(這裡假設都只需直接或隱性排除法即可完成),那兩者所花費的時間會不一樣。
提示格為20的數獨需解出61個空格,提示格為30的數獨需解出51個空格,若每一格的解題平均時間為2.5秒,那兩者解題所需時間差距就大約是25秒了。
許多人會認為解題所需時間不應納入謎題難易度條件中;但是經過觀察、比較及思考數獨謎題的難易度認定,回歸大數法則中,最後還是會以解題時間平均值作為難易度的參考值之一。
所以在筆者的觀念裡,解題所需花費的時間也需納入數獨難易度中。
但是光看提示格的多寡來訂定謎題的難易度,並非完全正確,因為有許多的因素會影響解題所需花費的時間。
哪些因素會影響解題所需時間,筆者歸納為下列五點:
一、首推解題技法。若不熟悉解題技法,或是用了更複雜的技法,所需使用的推理、分析與判斷要素就更多,當然時間花費就會增加。
二、作用格(作用中的確定數)相對於解答格的相對位置。牽涉到作用格相對於解答格的距離、數量與相距間的擾亂數(非作用中的確定數或空格)。
三、同時有解答的空格數目、數量與次數。也就是同一時間可供選擇有解答的空格數量愈多,找到解答格的機會愈大、速度愈快;若這樣的次數愈多,整體解答時間花費就愈少。
四、解答順序或流程。包含填入數字號碼順序,填入格順序或流暢度。
五、確定數與擾亂數的分佈狀態。確定數的分配情形影響解題時的判斷,如引導使用錯誤的解題技法或思考方向,以增加尋找的時間。
這裡僅以解題技法及應用做難易度說明,第二、三、四、五類不再分析。
1.以下是以解題技法難易度做順序,以每一小空格獲得解答的難易度分類(未考慮定數距解答格、關鍵格的距離,與擾亂數分配及數量) 。
2.以下是以不標記候選數解題模式來標記難易度分級(直觀法解題分級)。
3.以下是以獲得解答格經由比對、判斷、分析、推敲所需花費的時間做排序(純屬個人喜惡及主觀觀點,僅供參考)。
4.以下只用到筆者提倡的四類解題技法做分類(排除法、餘數法、井字型法、隱數法)。
圖例中,藍色小方格為解答格,數字皆為5。
1.宮餘一格解
2.一個定數宮直接排除解
3.行(列)餘一格解
4.同行(列)宮兩個定數宮排除解
5.兩個定數宮排除解
6.一個定數行(列)排除解
7.雙隱格+1個定數宮排除解
8.雙隱數在宮+宮餘一格解
這個小方格解看起來似乎很容易得解,但是許多人在作排除解時,因為思考方向仍在尋找排除解,所以容易忽略這個簡單的解答格。
另外,這個解答格須經由兩次的數數後(列數完換數宮)才能得解,容易粗心大意的算錯或填錯。
9.三隱數在宮+宮餘一格解
10.雙隱格(或雙隱數)行(列)排除解
11.三個定數宮排除解
12.四個定數宮排除解
13.雙隱格+兩個定數宮排除解
14.雙隱數在宮+行(列)餘一格解
行列在做數數時很容易出錯。
15.三隱數在宮+行(列)餘一格解
16.兩個定數行(列)排除解
17.兩組隱格(隱數)+一個定數宮排除解
18.隱格+三個定數宮排除解
19.兩組隱格+兩個定數宮排除解
20.全定數餘一數解
21.小井字排除解
圖例用了兩組小井字排
22.三個定數行(列)排除解
23.隱格餘一數解
24.大井字排除解
圖例用了一組大井字排及一組小井字排
25.雙隱格+2個定數行(列)排除解(或兩個雙隱格+1個定數)
26.四個定數行(列)排除解(含部分為隱格)
27.分開型雙隱數(餘二數組成)+餘一數解
以上基本類型有27種。
以下乃各種類型的交叉作用,最多為四種技法直接對解答格同時作用。
試著找這個圖例中的解答格在哪裡?用了哪幾種技法?
找到了嗎?
大井字 + 雙隱數(宮排除產生) + 分開型雙隱數(餘二數組成) + 餘一數解
可以發現上列的技法使用時,查找、比對、分析、判斷、推敲所需花費的時間不一樣。
因花費時間長短而感到難易度不同,但並非單單只用上述分類就可以正確的給予難易度分級,尚須將第二、三、四、五類影響條件納入。
如上述;有能力設計解題程式的人,就可以依照自己的分級與時間影響因素給予每一解題格難度係數,進而加總整個謎題的難度分數並分類。
若有機會再來探討數獨的解題格、解題流程、乃至謎題及難易度的標記研究。
唉!不才的老葉。
2007/03/14 補正
感謝同好小周指正,最後一個圖例有二個解答格、三種方法可以得解,並且繼續設計本謎題將會成為多重解謎題。
不才的老葉為了做技法併用圖例介紹,邊寫文章邊設計,並沒有仔細驗證解題格數量(應該說是沒有看出來),造成有2個解答格現象,於此說聲抱歉!
另一種解法<宮排除解>
2個數字3的大井字+1個確定數同時對 [宮6] 做排除,可得(69)=3排除解。
另一種解法<行排除解>
2個大井字+3個定數同時對 [行9] 做排除(6線排除),可得(69)=3排除解。
這個排除法無法成立。
雖然是合理的排除,但同時6條線排除將不會出現在合格的謎題。
作者:net538