电竞比分网-中国电竞赛事及体育赛事平台

分享

數(shù)獨解法理論探討

 北方的貓 2022-06-18 發(fā)布于云南

顛覆傳統(tǒng)思維,破解數(shù)獨密碼

新理念、新觀點、新角度,破解數(shù)獨新方法

這是以數(shù)獨規(guī)則為依據(jù),將集合論和拓撲學(xué)的理論為數(shù)學(xué)基礎(chǔ),采用深度優(yōu)先搜索算法,以新的視角、用新的思維,融合新的策略,以創(chuàng)新的手段開發(fā)出來的一種數(shù)獨新解法。

數(shù)獨進入中國以來,解題方法和解題技巧一直是國外經(jīng)驗一統(tǒng)天下。破解高難數(shù)獨的“高級技巧”更是被國內(nèi)數(shù)獨愛好者奉為“寶典“。

破解數(shù)獨果真就沒有別的方法了嗎?

首先,我們要從數(shù)獨的規(guī)則來研究:標(biāo)準(zhǔn)九宮數(shù)獨的每個小方格內(nèi)只能填上數(shù)字1至9,主要規(guī)則是:(1)每行、每列和每個小九宮都并且只包含數(shù)字1至9(2)每個單元格只包含一個元素(數(shù)字1—9),這個數(shù)字且與所在的行、列和宮都不重復(fù)。(3)標(biāo)準(zhǔn)數(shù)獨題只有唯一解。

高難度數(shù)獨是要通過“候選數(shù)法”才能快速順利解題的,“候選數(shù)法”就是在待填單元格中將可能填入的數(shù)字列示出來,以供尋找破解的線索。

使用“高級技巧”需要通過搜索與“高級技巧”相符合的題面(數(shù)字排列),再進行推算、回溯、刪除候選數(shù)或找出正確的答案。

那么候選數(shù)的性質(zhì)又是什么呢?我們不妨先看一道難度系數(shù)為8.0的數(shù)獨:

文章圖片1

我們將數(shù)獨作為一個集合,有81個單元格,九個元素(123456789)。他的子集分別是:行、列和小九宮,每個子集的元素也是九個,只是它們排列與組合有所不同。每個單元格只包含一個元素,這個元素在所處的行、列和宮都不重復(fù)。待填格的候選數(shù)也是一個集合,這個集合的元素≤9個。

我們用集合運算的方法將候選數(shù)填列出來。

數(shù)獨是以行、列、宮作為基本單元的,因為每個單元格元素的變動,與之發(fā)生直接關(guān)聯(lián)的是它所在的行、列和宮,這是數(shù)獨規(guī)則所決定的。如果把行、列和宮的待填數(shù)作為一個集合,我們以上圖的第五宮為例:

第四行待填數(shù)集合R4{1、2、3、5、6、7、8、9}

第五行待填數(shù)集合R5{、2、3、7、8、9}

第六行待填數(shù)集合R6{2、3、4、5、6、8、9}

第四列待填數(shù)集合C4{1、5、6、8}

第五列待填數(shù)集合C5{1、2、3、4、5、7、8}

第六列待填數(shù)集合C5{1、2、3、4、6、7、8}

五宮待填數(shù)集合B5{1、2、3、5、8、9}。見下圖;

文章圖片2

各待填格的候選數(shù)集合就是通過下列運算得到的

R4C5的候選數(shù)集合= R4∩C5∩B5{1、2、3、5、8}。

R4C6的候選數(shù)集合= R4∩C6∩B5{1、2、3、8、9}。

R5C4的候選數(shù)集合= R5∩C4∩B5{8}。

……。

可見,單元格的待填候選數(shù)就是該單元格所在行、列、宮待填數(shù)集合的交集。當(dāng)這個交集只有一個元素時,那么它就是該單元格的解。和我們通常用的余數(shù)法所計算出來的結(jié)果是一致的,見R5C4。

如果某個單元格候選數(shù)集合中的一個元素,是所在宮或行或列的其它所有單元格候選數(shù)集合的絕對補集,那么這個元素也是該單元格的解。換種說法就是:一個單元格候選數(shù)集合中的一個元素,與所在宮或行或列的其它所有單元格候選數(shù)集合都沒有交集,那么這個元素也是該單元格的解。用排除法也會得出同樣的結(jié)果。見圖:

文章圖片3

看到這里,我們還明白一個道理,單元格里的候選數(shù)其實就是一個解的集合,如果沒有規(guī)則,就是一道多解題。

可見,破解數(shù)獨題,我們是用規(guī)則在識別答案:找出符合規(guī)則的答案。也用邏輯推理的方法取破解數(shù)獨,就是用一個又一個的判斷去識別答案。所謂“高級技巧”的缺陷是,著眼于一數(shù)、一鏈非此即彼,非真及假的推演,過多的且繁瑣判斷過程和只能適用固定數(shù)據(jù)結(jié)構(gòu)而掌握困難,運用于實踐更加困難,而且大多數(shù)時候只能刪除幾個候選數(shù),要想得到結(jié)果你可能需要幾次的推演。正因為如此,在實戰(zhàn)中得大多數(shù)情況下往往推不出一個確定的結(jié)果,忙了半天無果而終。九宮數(shù)獨約有6.67×10的21次方種組合,就是剔除重復(fù)(如數(shù)字交換、對稱等)后,也有54億多種。每個組合又可以設(shè)計出n道數(shù)獨題,即使高級技巧不斷被發(fā)現(xiàn),也無法適用千變?nèi)f化的數(shù)獨題。

從集合論的角度來看,數(shù)獨就是一個集合,雖有81個單元格,但只有九個元素(1、2、3、4、5、6、7、8、9)。如果我們把一個數(shù)獨題作為一個全集U,子集S則是:行、列和小九宮,每個子集的元素也是9個元素,只是它們排列與組合有所不同。

文章圖片4

我們把數(shù)獨的待填數(shù)看成一個集合,它的元素總是≤9個。每個單元格的待填候選數(shù)的個數(shù)卻遠遠大于集合的元素的個數(shù),這是因為每個待填單元格的候選數(shù)總是≥2,真正的答案隱藏其中,其它“候選數(shù)”組成了一個假候選數(shù)集合。

通過對“世界最難數(shù)獨”的逆項工程,得到以下候選數(shù)表。紅色數(shù)字是該單元格的解,仔細觀察就會發(fā)現(xiàn):四宮E3、D3和F2都存在數(shù)組{2、6}。在確認F3的解是9以后可繼續(xù)確認D3的解是4,再確認F2的解是8。

在解題過程中經(jīng)常會利用數(shù)對鎖定待填數(shù)和待填格來精簡候選數(shù)和確認解。當(dāng)一個單元只剩兩個待填格時,它們一定是一個雙值數(shù)對,雙值數(shù)對是最典型的數(shù)對,此外還有三值數(shù)對,四值數(shù)對。這些數(shù)對,對解題不利的方面是循環(huán)、結(jié)構(gòu)牢固,給解題帶來困惑。

既然數(shù)獨就是一個數(shù)的集合,每個待填的候選數(shù)是一個子集,這個子集中只有一個元素是符合數(shù)獨規(guī)則的元素,這是數(shù)獨題探求的結(jié)果。這也是分析數(shù)學(xué)—拓撲學(xué)研究的對象。

創(chuàng)新解法的核心就是要找出候選數(shù)集合中隱藏的數(shù)對,如果一個候選數(shù)集合有n個元素,我們就得找到n+1個同樣的選數(shù)集合,因為n個元素只能占用n個待填格。在刪除多出的那個候選數(shù)集合后要保證能得到有效解,否則毫無意義。這也是創(chuàng)新解法得獨特之處。所以,了解數(shù)對在解題中的意義很有必要。

我們在解題過程中所遇到的數(shù)對都是顯性數(shù)對,它的表現(xiàn)形式有兩種:一、n個待填格中只有數(shù)對中的數(shù)(數(shù)對中有n個數(shù)),別無其它候選數(shù)。待填格中只有數(shù)對中的全部或其中的幾個數(shù),可刪除的是所在宮或行或列其它待填格數(shù)對中的候選數(shù);二、只有n個待填格中有數(shù)對中的n個數(shù),可刪除的是所在待填格中其它候選數(shù)。

顯性數(shù)對通過肉眼觀察即能獲得,創(chuàng)新解法所要尋找的是隱性數(shù)對。隱形數(shù)對也有兩種表現(xiàn)形式:半隱性數(shù)對和全隱性數(shù)對。

既然我們運用分析數(shù)學(xué)—拓撲學(xué)作為破解數(shù)獨的理論,那么,我們就要尋找到一個適合的算法來求出答案。

我們知道,很多問題在無法根據(jù)某種確定的計算法則,同時也不能找出適用的數(shù)學(xué)模型來求解時,可以用搜索與回溯的技術(shù)求解。那么,深度優(yōu)先搜索(DFS)算法為我們提供了一個可用的工具,這種算法也是計算機常用的算法。專業(yè)的表述就是:搜索算法是利用計算機的高性能來有目的的窮舉一個問題的部分或所有的可能情況,從而求出問題的解的一種方法。

我們可以運用深度優(yōu)先搜索(DFS)算法尋求破解數(shù)獨。

深度優(yōu)先搜索(DFS)算法的特點就是利用計算機高性能計算速度和能同時多點發(fā)起搜索的優(yōu)勢,采用窮舉遍歷的方法找出答案??墒侨四X和手工在短時間內(nèi)是很難完成的。

如果我們能夠利用化整為零的方法縮小數(shù)據(jù)規(guī)模,科學(xué)的篩選出高效可靠的搜索發(fā)起點,正確定義解題空間,在搜索過程中再利用剪枝函數(shù)避免回溯減少無效搜索。那么,人腦和手工運用深度優(yōu)先搜索算法破解數(shù)獨還是有可能的。當(dāng)然,用計算機軟件來實現(xiàn)這個方案將會更快。

第一、如果以九宮數(shù)獨的小九宮、行和列作為研究對象,他們組合便只有362,880種。再以小九宮、行和列的待填格作為研究對象,數(shù)據(jù)的規(guī)模將會更小。

整個九宮數(shù)獨的81個單元格是相互聯(lián)系的,如果只是以小九宮、行和列為研究對象,把它們與整個九宮割裂開來,這樣得出的解豈不是令人擔(dān)心?大可不必,因為數(shù)獨題的每個待填單元格的元素(數(shù))是唯一的,早就確定的。我們看不到它,它只是隱藏在了其它候選數(shù)之中,它不會因我們的解題方法和解題線路而改變。根據(jù)數(shù)獨規(guī)則“(2)每個單元格只包含一個元素(數(shù)字1—9),這個數(shù)字且與所在的行、列和宮都不重復(fù)“的定義,它們只與所在的九宮、行列有關(guān)聯(lián),僅此而已。

第二、根據(jù)數(shù)獨的規(guī)則定義解題空間。每個單元格只有一個有效元素,且與所在的小九宮、行和列其它單元格的元素不重復(fù),這是數(shù)獨規(guī)則的要求。我們定義的有效解是:當(dāng)一個單元格只有一個元素不包含在該單元格的所出現(xiàn)的子集中,那么,這個元素就是該單元格的解。

為什么這樣說?每個單元格的元素是唯一的,而那有三個或更多的候選數(shù)待填格中,除了那個解外,其它的候選數(shù)正是一個假候選數(shù)的集合。我們只要根據(jù)一定的規(guī)則篩選出這些假候選數(shù)的集合,那么,這個單元格中孤獨的元素自然就是該單元格的解。

從這個理論出發(fā),當(dāng)一個候選數(shù)集合在單元(行、列、宮)中的個數(shù)多于這個集合元素的個數(shù)時(集合的數(shù)量多于該集合的元素),才能進行刪除,而且在待填格中刪除該候選數(shù)集合后能得到有效解。

如果一個待填格中有兩個子集的并集且沒交集,這兩個子集符合刪除的數(shù)量要求時,也可作為確認有效解的刪除依據(jù)。

一個單元中,某個候選數(shù)出現(xiàn)在所有的待填格中,我們稱它為“公共候選數(shù)”。它將會與那些有三個及以上的其它候選數(shù)組成可確認有效解的候選數(shù)集合,而它將是那些子集的共同交集,確認解時要仔細分析。

文章圖片5

如圖1:候選數(shù)6在每個待填格中都有出現(xiàn),它就是公共候選數(shù)待填數(shù)1、2、9每個都出現(xiàn)3次,它們都能與6組成有效的可定義解的(三個)數(shù)組集合A{1、6}、B{6、9}、C{2、6},此時不能隨意刪除和任意確認其中的一個候選數(shù)是解(例:刪除A1中的{1、2}、{1、6}或{2、6},去定義另一個數(shù)是解)。定義沒有交集的待填格B1的解是4(4只出現(xiàn)兩次)。

下圖也是這種情況,候選數(shù)1在每個待填格中都有出現(xiàn),候選數(shù)3、7、8每個都出現(xiàn)3次及以上,它們都能與1組成有效的可定義解的(3-4個)數(shù)組集合A{1、3}、B{1、7}、C{1、8},此時不能隨意刪除一個去任意定義這幾個候選數(shù)的一個為解(例:刪除C2中的{1、3}、定義8是C2的解)。定義沒有交集的待填格A1的解是4(4只出現(xiàn)兩次)

文章圖片6

在解題過程中,公共候選數(shù)不僅能幫助我們確認只出現(xiàn)兩次的待填數(shù)的有效解,也能幫組我們在復(fù)雜的數(shù)據(jù)中確認有效解。如上例中的待填數(shù)4.

見圖1:一宮有7個待填數(shù),待填數(shù)5出現(xiàn)在每個單元格中;1和9出現(xiàn)三次;3和7出現(xiàn)四次,2出現(xiàn)5次。它們和5都能組成能確認有效解的集合。只有6出現(xiàn)兩次,它分別出現(xiàn)在A1和C1。C1中的{2、3、5}多于{2、2、3、5},確認C1的解是6。

文章圖片7

在四個待填格中不能同時定義兩個有效解。如果一個單元中只有兩個待填格,它們必定是一個數(shù)對。如果只有三個待填格,它們共有7種組合,分別是1.{ABC、ABC、ABC};2.{ABC、ABC、AB};3.{ABC、ABC、AC};4.{ABC、ABC、BC};5.{ABC、AB、AC};6.{ABC、AB、BC};7.{ABC、AC、BC}。如果根據(jù)規(guī)則,每個組合都是循環(huán),不能確認正確的解。在四個待填格中同時定義兩個解是有問題的。

文章圖片8

如上左圖:五宮有四個待填格,每個待填格都有數(shù)組{2、3}。有效搜索發(fā)起點是F5{2、3},按規(guī)則可刪除兩個{2、3},似乎可以得到兩個有效解D5是1、E6是9??墒?,這其中有一個解是在只有三個待填格的情況下確認的解,是不合乎邏輯的。如果我們確認任何一個解,剩下的三個待填格候選數(shù)組合是{23n、23n、23},無法確認解。最終正確答案是E6=9;D5=2。

第三、利用剪枝函數(shù)避免無效搜索。如一個數(shù)組有兩個元數(shù)(比如A、B),那么在另外一個單元格也應(yīng)有一個一樣的數(shù)組,不然一個單元格無法安放兩個元素。我們在確定子集的數(shù)組時,要保證它與其它子集∪時,至少要有一組∪中不存在∩。確定子集元素時要保證子集中的元素在上一層集合中它們是連接最緊密(最多)的。

第四、確定集合研究的范圍也很重要,它可以避免我們在解題過程陷入混亂和迷茫。數(shù)獨不研究有0個元素的集合,因為數(shù)獨的每個單元格必須且只有一個元素,不存在空單元格。也不研究只有一個元素的集合,因為一個單元格只有1個元素,他就是這個單元格的解,再去研究毫無意義。

我們將數(shù)獨題的待填數(shù)定義為全集U,研究單元(小九宮、行和列)定義為子集S,每個單元的候選數(shù)以數(shù)組為子集A、B、C、……,子集A的子集是A1、A2、An……。數(shù)組子集的并集為T,T是S的子集。當(dāng)數(shù)組子集A、B、C的元素是n(n≥2)個時,它應(yīng)當(dāng)同時在≥n個單元中出現(xiàn)。這是數(shù)獨規(guī)則所要求的,如一個數(shù)組有兩個元數(shù)(比如A、B),那么在另外一個單元個也應(yīng)有一個一樣的數(shù)組,不然一個單元格無法安放兩個元素。

當(dāng)一個單元(宮、行和列)的某個候選數(shù)只出現(xiàn)兩次,這個候選數(shù)可以不用把它編入子集中。因為,我們定義:在一個單元中,如果一個子集僅出現(xiàn)兩次,不能作為確認解的依據(jù)。否則,很有可能讓我們在解題時進入死循環(huán)。

如果某個單元有多個候選數(shù)只出現(xiàn)兩次,而其他候選數(shù)數(shù)組又組成了與之?dāng)?shù)量相同的集合,那么,這些集合不能刪除,也不能作為確認解的依據(jù)。

第五、在對一個小九宮、行和列進行深度搜索(DFS)算法得出解之后,應(yīng)立即用排除法和余數(shù)法整理題面。一是可以驗證解的正確性,二是如果發(fā)現(xiàn)運用排除法和余數(shù)法即能順利解題,就可終止使用深度搜索(DFS)和回溯算法,畢竟用排除法和余數(shù)法解題要快速和容易很多,避免不必要的回溯。深度搜索(DFS)也可在多點(小九宮、行和列)同時發(fā)起。

第六、關(guān)于數(shù)對。創(chuàng)新解法的核心就是要找出非正解候選數(shù)的數(shù)對,如果一個非正解候選數(shù)集合有n個元素,我們就得找到n+1個同樣的非正解候選數(shù)集合,因為n個元素只能占用n個待填格。在刪除多出的1個非正解候選數(shù)集合后要保證能得到有效的解,否則毫無意義,這也是創(chuàng)新解法得獨特之處。所以,了解數(shù)對在解題中的意義很有必要。

我們在解題過程中所運用的大都是顯性數(shù)對和隱形數(shù)對。

顯性數(shù)對:n個待填格中只有數(shù)對中的數(shù)(數(shù)對中有n個數(shù)),別無其它候選數(shù)。待填格中只有數(shù)對中的全部或其中的幾個數(shù),可刪除的是所在宮或行或列其它待填格候選數(shù)中的數(shù)對數(shù)。如圖:數(shù)組{2、7}就是典型的顯性數(shù)對,本宮和相關(guān)列的其它待填格候選數(shù)中的2和7都要刪去。

文章圖片9

隱形數(shù)對:只有n個待填格中有數(shù)對中的n個數(shù),可刪除的是所在待填格中其它候選數(shù)。由于它們被其它候選數(shù)包裹著往往難以發(fā)現(xiàn)。如圖:

文章圖片10

圖中數(shù)組{1、2}就是典型的隱形數(shù)對,它們分別被其他候選數(shù){4、6、8}和{4、5、6}包裹著,不認真觀察不易發(fā)現(xiàn)。

隱形數(shù)對還有多種非典型表現(xiàn)方式:

所謂非典型隱形數(shù)對:就是在一個單元中,有兩個及以上的待填數(shù)總是同時出現(xiàn)在相同的待填格中。見非典型隱形數(shù)對-1:這是所謂“世界最難數(shù)獨”第五宮開局全標(biāo)候選數(shù)圖,我們發(fā)現(xiàn),五宮的每個待填格中都有數(shù)組{2、8},按規(guī)則可以刪除三個{2、8}數(shù)組,但只有刪除C2的{2、8}可確認有效解是6。

文章圖片11

典型隱形數(shù)對-2,在實踐中也會經(jīng)常遇到,從圖可以看出,在該宮,待填數(shù)3和5都是同時出現(xiàn)在相同的待填格中,組成不可分割的數(shù)組{3、5}。

文章圖片12

這種形式在實戰(zhàn)解題中有什么意義呢?按照常規(guī)搜索法,該宮無法發(fā)起有效搜索,任一個三值格或四值格都不能找到3個或4個相同的數(shù)組,也就是不能發(fā)起有效搜索,也就無法得到有效解。如果發(fā)現(xiàn)了這個隱形數(shù)對,就可以從D3{1、6}、E3{6、7}、F2{8、9}、F3{2、7}發(fā)起有效搜索,從而可確認E2的有效解是9。

隱性數(shù)對也有兩種表現(xiàn)形式:半隱性數(shù)對和全隱性數(shù)對。創(chuàng)新解法解題時九是通過搜索半隱性數(shù)對來確認有效解。通常的做法是通過顯性數(shù)組來尋找(搜索)隱性數(shù)對(非正解候選數(shù)的集合),搜索到的非正解候選數(shù)集合的個數(shù)超過數(shù)對元素的數(shù)量時,對確認有效解才有實際意義。如果是一個雙值數(shù)對,需要找出三個或以上相同的數(shù)組,才能刪除多余的數(shù)組。

選擇搜索發(fā)起點的目的時尋找隱性數(shù)對的另一半,我們知道在一個單元中出現(xiàn)數(shù)對,這個單元其他待填格就不能再出現(xiàn)數(shù)對中的數(shù),解題實踐中幫組我們簡化題面的候選數(shù),又是也能直接得出有效解。

文章圖片13

如上圖:從A1{1、2、4、7}或B2{2、4、6、7}發(fā)起搜索,都不能得到4個相同數(shù)組,因為這個數(shù)組有四個元素,我們把它稱之為無效搜素。我們?nèi)绻麖腂1{2、4、7}發(fā)起搜索,發(fā)現(xiàn)共得到5個相同數(shù)組,因為這個數(shù)組只有三個元素,根據(jù)數(shù)對的定義,我們可以刪除兩個待填格中的數(shù)組{2、4、7}。但是,有三個待填格在刪除數(shù)組{2、4、7}后可得到解。A1和C3可得到的解是1,B2可得到的解是6。根據(jù)數(shù)獨規(guī)則,只能刪除兩個,取兩個解,顯然A1和C3的解是不符合數(shù)獨規(guī)則的,只得舍棄。沒有爭議的而能確認的有效解是B2,它的解是6。

全隱性數(shù)對就是無法通過搜索半隱性數(shù)對的方法得到,它只能通過因素分析法得到,在遇到數(shù)據(jù)結(jié)構(gòu)復(fù)雜,用搜索半隱性數(shù)對的方法無法獲得任何有效解的情況下而使用的一種方法。

在所有單元都無法發(fā)起有效搜索,或搜索不到有效的候選數(shù)集合,或無法確認有效解,這時需要運用因素分析法來獲得全隱性數(shù)對。

因素分析就是對一個單元所有待填格的候選數(shù)進行分析,找出隱性的有效候選數(shù)集合,這些候選數(shù)集合必須是明確的沒有交集的有效的并且能確認有效解的候選數(shù)集合。

文章圖片14

見上圖:A1{2、7、8、9};A2{5、6、7、8、9};B1{1、2、7、8、9};B2{1、6、7、8、9};C2{1、5、7、8、9}。與其他子集{1、2}和{5、6}沒有交集。并且能確認A1的有效解是2。

再看第二例,存在全隱性數(shù)對{4、5、6}和{2、3、8}。數(shù)對{4、5、6}共6個,(包含兩個子集{4、5});數(shù)對{2、3、8}共有5個(包含1個子集{2、8})。搜索過程中避開了發(fā)生交集的情況。因此得到兩個有效解1和9。

文章圖片15

這是有一個運用全隱性數(shù)對解題的例子,宮中只有一個提示數(shù),無論從哪個待填格都不能發(fā)起有效搜索,但是該宮有非典型隱形數(shù)對{5、9},這個數(shù)對不能幫我們直接確認有效解。在所有出現(xiàn)數(shù)對的待填格中還存在2個及以上的其它候選數(shù)。特別是有3個及以上候選數(shù)但又無法發(fā)起有效搜索時,就很難得到有效解,如果僅憑主觀臆斷對候選數(shù)進行組合劃分,出錯的概率會很大。這時我們可以利用非典型的隱形數(shù)對來搜索全隱形數(shù)對。這一例中,發(fā)現(xiàn)有四個{5、6、9}數(shù)組,還有一個子集{5、9}數(shù)組,繼續(xù)搜索過程中避開出現(xiàn)交集的情況,得到D1的有效解是2。

文章圖片16

顯性數(shù)對、隱形數(shù)對、非典型隱形數(shù)對、隱性數(shù)對的特點。

顯性數(shù)對和隱形數(shù)對是一組確定的數(shù)對,它們的存在可直接刪除與它們相關(guān)的其他待填格中的(數(shù)對)候選數(shù),起到精簡題面的作用,有時也能得到有效解。

文章圖片17

非典型隱形數(shù)對:可以確認一定存在一組數(shù)對,但是到底是由哪幾個單元格來組成數(shù)對并不確定。有時可以直接確認有效解,有時可幫助我們發(fā)起有效搜索找到有效解。

隱性數(shù)對不一定存在真正的數(shù)對,他只是幫助我們找出解的媒介。

第七、策略

一、搜索的策略

1、搜索單元以宮優(yōu)先。根據(jù)幾何學(xué)的定義,行和列屬于線是一維圖形,宮屬于面是二維圖形,宮的作用面要大于行和列,得到解的可能性大。

2、從候選數(shù)少的待填格優(yōu)先發(fā)起搜索。這是因為元素少更容易組成本解法意義上的有效集合,也更容易得到有效解。從實踐來看,在三值格中搜到有效解的概率很高。

3、元素多的集合優(yōu)先于元素少的集合。如:4元素集合→3元素集合→2元素集合……。例:從{A、B}發(fā)起搜索,搜索到了{A、B、C}數(shù)組集合且滿足定義有效候選數(shù)集合的條件(三個),這是{A、B}只能作為{A、B、C}的子集出現(xiàn),而不能利用{A、B}去確認{A、B、C}中的解。

4、在一個單元中(行、列、宮)的兩個待填格中同時搜索到相同解(兩個單元格得到同一個數(shù)字的解)的情況時:獨立子集優(yōu)先于并集;并集優(yōu)先于有交集的;出現(xiàn)次數(shù)多的優(yōu)先于出現(xiàn)次數(shù)少的。注意:有交集的待填格不可確認有效解。

5、開局搜索從提示數(shù)最多的行列宮開始。

二、規(guī)避風(fēng)險的策略

1、利用優(yōu)先搜索策略減少無效搜索。

2、優(yōu)先規(guī)避回溯風(fēng)險。在一個單元(行、列、宮)的兩個待填格中同時搜索到相同解(兩個單元格得到同一個數(shù)字的解)的情況,只要存在疑義,就果斷舍棄。

3、開局慎用殘局定義解的規(guī)則。

第七、因素分析法。

在所有單元都無法發(fā)起有效搜索,或搜索不到有效的候選數(shù)集合,或無法確認有效解,這時需要進行縱深分析。

因素分析就是對一個單元所有待填格的候選數(shù)進行分析,找出隱性的有效候選數(shù)集合,這些候選數(shù)集合必須是明確的沒有交集的有效得并且能確認有效解得候選數(shù)集合。

我們用下面這題難度系數(shù)為10.4的數(shù)獨題為例,全標(biāo)候選數(shù)見下圖:

文章圖片18

這道題用常規(guī)搜索法,一時很難發(fā)現(xiàn)有效解。下面運用因素分析法來解題,先從五宮入手:

首先在五宮發(fā)現(xiàn)了非典型隱形數(shù)對{1、4}用橙色標(biāo)記,它出現(xiàn)在每個待填格中。其他待填數(shù)3和7都出現(xiàn)五次、2出現(xiàn)三次,都用綠色標(biāo)記。5和9都只出現(xiàn)兩次不做標(biāo)記。先看D4的候選數(shù)5,除了數(shù)組{1、4}還有數(shù)組{3、7},數(shù)組{3、7}共有三個,可以刪除一個。E4也有候選數(shù)5,但七數(shù)組{2、3、7}只有兩個,不符合確認有效解的條件。再看待填數(shù)9,分別出現(xiàn)在D5{1、4、7、9}和F6{1、3、4、9},除了隱形數(shù)對{1、4}外,待填數(shù)3和7都出現(xiàn)在5個待填格中,所以不能確認哪個是有效解。

文章圖片19

這例中的數(shù)組{1、4}既是非典型隱形數(shù)對也是公共候選數(shù)。

再來看四宮,四宮也存在非典型隱形數(shù)對{2、8}。以數(shù)對{2、8}為起點,E2除了數(shù)對{2、8}外還有數(shù)組{4、5、6},共搜索到四個{4、5、6}數(shù)組,可組成一個有效的候選數(shù)集合,并能確認D2的解是9。但同時,又可以組成有效的{4、5、8}、{4、5、9}和{2、3、4}候選數(shù)集合。他們的交集是∩{4、5}。這種情況應(yīng)慎重行事。

文章圖片20

我們看三宮,從C8{4、6、9}發(fā)起搜索,引出數(shù)組{4、8}。數(shù)組{4、8}共有三個,根據(jù)數(shù)對理論,可以刪除一個,在刪除C9的{4、8}后可確認C9的有效解是3。我們見終盤圖:C9的解確實是9。但A7和A9的4、8并不是真正以數(shù)對形式存在的,C7的解是6,C9的解是8。

文章圖片21

見上圖:A1{2、7、8、9};A2{5、6、7、8、9};B1{1、2、7、8、9};B2{1、6、7、8、9};C2{1、5、7、8、9}??梢钥闯觯瑪?shù)組{8、9}是一組非典型隱形數(shù)對。{7、8、9}、{5、6}和{1、2}都屬于全隱形數(shù)對。這些數(shù)對的集合相互之間不存在交集。并且能確認A1的有效解是2。

最后,這些理論的經(jīng)過實戰(zhàn)的演練才發(fā)現(xiàn)它的瑕疵和新的規(guī)律,亦不斷完善走向成熟。以后將會以更多的實例來驗證這種創(chuàng)新解法格可行性和可靠性。歡迎數(shù)獨愛好者提供難題。

    本站是提供個人知識管理的網(wǎng)絡(luò)存儲空間,所有內(nèi)容均由用戶發(fā)布,不代表本站觀點。請注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息,謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,請點擊一鍵舉報。
    轉(zhuǎn)藏 分享 獻花(0

    0條評論

    發(fā)表

    請遵守用戶 評論公約

    類似文章 更多