




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、數獨技巧(Sudoku Strategies)數獨快速入門(上篇)數獨快速入門(中篇)數獨快速入門(下篇)數獨快速入門(上篇)范例一: 在左邊第一個九宮格里,哪格可以放數字, 先看到再第一列和第二列里已經有了數字, 所以很明顯了,除了棕色格子之外,上面兩列格子已經不能放了。 范例二: 換個進階范例來看看, 已知第一列和第二列不能放,但僅就第三列而言,的旁邊似乎都可以放的樣子, 但再看看被顏色標示的第三行, 看到第三行有之后,就知道棕色格子應該放。 范例三: 來個更進階點的,想想左上角第一個九宮格里,哪一格可以放, 再看 先看看前兩列,應該不能放, 看被顏色標示的第二行與第三行,又是不能放, 很
2、顯然的,就只有棕色格子能放。 范例四: 再看看這個重要范例,想想左上角第一個九宮格里,哪格可以放, 先看看被顏色標示的第二列, 再看看被顏色標示的第二行, 經過分析后可知要放在這棕色格子。 范例五: 換個輕松點的范例, 看看第一列,數字有哪些, 顯而易見的就是缺。 數獨快速入門(中篇)范例一: 看看這個比上篇難的,想想能放在哪里呢, 被顏色標示起來的第一列和第一行已經不能放了, 就左上角的九宮格而言,在紅色標示區域似乎是可以擺的, 但在這里而言,似乎無法決定放在兩格紅色區域的哪一格, 所以,可以先看看鄰近的九宮格,發現到棕色格子能放喔,這時候就不用懷疑馬上寫下。 范例二: 看看這個有技術性的,
3、想想能放在哪里, 看到黃色的第一列已經有,所以不能再放了, 就中央的九宮格而言,合理的推論,一定是在第二列中央紅色三格的其中之一了, 既然知道第二列的情況,再考慮黃色區域后, 那么可以先確定右方九宮格的必然放在這棕色格子。 范例三: 由上篇的概念再進階,考慮這上面三個九宮格,看看能否決定的位置, 黃色標示的第三行已先被排除, 就第一個九宮格而言,一定在紅色區域, 就黃色標示區域來看,已不能再放了, 這時可以馬上先決定右上九宮格里的棕色格子是能放的啦。 范例四: 看到這左上方九宮格的第一列,就可以馬上知道缺了哪兩個數字, 是不是已經看出紅色格子不是就是了, 但是又看到第二行有,所以很輕松知道左上
4、棕色格子一定是, 接下來就確定在紅色格子了。 范例五: 先看看這第一列, 左上方的九宮格里,第一列絕對有、, 再考慮到第一行黃色區域,看到有和, 這下就可確定絕對放在左上角的棕色格子。 數獨快速入門(下篇)范例一: 來看看這個高級進階例子,可以先把眼光放在第一列和第一行, 看到在黃色區域里都有和,所以此黃色區域已經不能再放和了, 這時可以考慮到左上九宮格里的紅色格子能放和, 再看到第一列和第三列的黃色區域,這黃色區域里已經不能放, 在左上九宮格里,能放的只有紅色與棕色格子,但紅色格子將會被和所占據,所以能確定棕色格子必然為。 范例二: 看看左上方九宮格里,能否由些微線索決定的位置, 首先,看到
5、第一列后先排除、,又因左上方九宮格里有、,再排除這三個數字,這下,在左上方九宮格的第一列,只剩下、可以填,然后,又看到第一行有和,所以,棕色格子必然不會是和,那么,就只剩下可以填入啦! · 直觀法(Direct Elimination Techniques) · 候選數法(Candidates Elimination Techniques) 直觀法(Direct Elimination Techniques)經常在報章雜志上看到的數獨謎題,一般就算再難都可以用直觀法來解決。它不需要象候選數法(Candidates Elimination Techniques)那樣在每個空白
6、的單元格中用鉛筆填上一大堆候選數。你只要有相對銳利的眼光和一定的邏輯分析能力,就可以準確地把空余的數字逐個填出來。實際上,直觀法就是對數獨游戲規則的充分利用。雖然它并不如候選數法(Candidates Elimination Techniques)那樣強大,但通常要想體會解決數獨謎題的樂趣,使用直觀法卻是不二之選。直觀法(Direct Elimination Techniques)具有以下的特點:輕松上手。 即便是數獨新手,在拿到謎題的一剎那,就可以用直觀法來解題了。 無需輔助。 在紙上解題時一般只需要一支鋼筆就可以。因為是通過推理和邏輯分析來確定哪個格填哪個數,或是哪個數填在哪個格里,所以基
7、本不需要猜測。容易掌握。 對于直觀法(Direct Elimination Techniques)中應用的各種算法,可以很快掌握并應用于實際中。 相對簡單。比起候選數法(Candidates Elimination Techniques),它的算法相對比較簡單,當然能解決的謎題的復雜度也相對要低。在直觀法(Direct Elimination Techniques)中,常用的算法包括:1.單元唯一法 ( Sole Position Technique ) 2.單元排除法 ( Basic Elimination Technique ) 3.區塊排除法 ( Block Elimination Te
8、chnique ) 4.唯一余數法 ( Sole Number Technique ) 5.組合排除法 ( Combination Elimination Technique) 6.矩形排除法 ( Rectangle Elimination Technique) 1.單元唯一法 ( Sole Position Technique ) 這應該算是直觀法中最簡單的方法了。基本上只需要看謎題,推理分析一概都用不上,這是因為要使用它所需滿足的條件十分明顯。同樣,也正是因為它簡單,所以只能處理很簡單的謎題,或是在處理較復雜謎題的后期才用得上。 我們先來看一個例子:在上圖中,觀察行B,可以看到除了B3外,
9、其他所有的單元格中都已有了數字,根據數獨游戲的規則,即每行,列或區塊中不能有重復的數字,則B3中能填入的數字只能是行B中所未出現過的,也就是數字3。所以可以毫不猶豫地在B3中填入3。這就是單元唯一法在行中的應用。這里的單元(Unit, or group),指的是行,列或區塊。所以有三種情況:當某行有8個單元格中已有數字,或 當某列有8個單元格中已有數字,或 當某區塊有8個單元格中已有數字。 無論是哪種情況,我們都可以很快地在該行,列或區塊剩余的空格中填入該單元還未出現過的數字。下面是單元唯一法在列中的應用: 在第7列中,只有F7未填入數字,且這一列中數字8還未出現過。所以F7 = 8。在區塊中
10、也是一樣:在起始于D7的區塊中,只有E7還未填入數字,且這個區塊中數字5還未出現過,所以可以馬上在E7中填入5。單元唯一法在解題初期應用的幾率并不高,而在解題后期,隨著越來越多的單元格填上了數字,使得應用這一方法的條件也逐漸得以滿足。 2.單元排除法 ( Basic Elimination Technique ) 單元排除法是直觀法中最常用的方法,也是在平常解決數獨謎題時使用最頻繁的方法。使用得當的話,甚至可以單獨處理中等難度的謎題。使用單元排除法的目的就是要在某一單元(即行,列或區塊)中找到能填入某一數字的唯一位置,換句話說,就是把單元中其他的空白位置都排除掉。它對應于候選數法中的隱式唯一法
11、。那么要如何排除其余的空格呢?當然還是不能忘了游戲規則,即行,列或區塊中不能有重復的數字。從另一個角度來理解,就是如果某行中已經有了某一數字,則該行中的其他位置不可能再出現這一數字。如果某列中已經有了某一數字,則該列中的其他位置不可能再出現這一數字。如果某區塊中已經有了某一數字,則該區塊中的其他位置不可能再出現這一數字。單純理解上面的規則還是不足以解題,但是在實踐中這些規則卻可以交叉使用。在實際解題過程中,應用最多也最方便的是對區塊的單元排除法,我們可以先看下面這個例子:對于起始于D1的區塊,其未填數字的空格有6個之多,如果不使用單元排除法,是很難為這一區塊填入任何數字的。這時我們就可以利用行
12、,列及區塊的相互關系,即一個單元格既在某一行上,也同時在某一列上以及某一區塊中的這種關系來解題。觀察數字9在謎題中的位置,可以看到它出現在B2,A4,C7,D8,I1和H9。而這些位置中,只有B2,D8和I1與起始于D1的區塊有關聯。因為I1=9,它所在的第1列上的其他單元格中不可能再出現9, 而區塊中的D1和F1正好也在第1列上,所以這兩個單元格填入9的可能性被排除。同理,因為B2=9,它所在的第2列中的其他單元格不可能再填入9,而區塊中的D2和E2也正好在第2列上,因此,這兩個單元格填入9的可能性也被排除掉了。再看行D,因為D8=9,所以該行上的D1,D2和D3也不可能再填入9,而這些單元
13、格正好也在起始于D1的區塊中。所以,這個區塊中能填入數字9的位置就只剩下了E3,這樣就通過排除法找到了答案,即E3=9。下面再看一個在行中使用單元排除法的例子:在謎題中觀察數字4和行H,在行H有5個空單元格無法確定數字,但是C3位置上的4使得其所在的第3列中的其他單元格上不能再出現4,所以H3不能填入4。I4上的4使得其所在的區塊中也不能再填入4,它幫助行H排除了兩個單元格H4和H6,而第8列上的E8中的數字4使得同樣位于這一列上的H8也排除了填入4的可能。這樣,行H中能填入4的位置就只剩下H9了。在列中也可以使用單元排除法:在第7列中,我們試圖確定能填入數字1的位置。在行B中,數字1已經出現
14、在B2上,所以B7不可能再填入數字1了。而位于D8的數字1也使得F7排除了填入數字1的可能,因為它們位于同一區塊中。這樣,第7列上就只有A7能填入數字1了。 通過上面的示例,可以看到,要對區塊使用單元排除法,需要觀察與該區塊相交的行和列。要對行使用單元排除法,需要觀察與該行相交的區塊和列。要對列使用單元排除法,需要觀察與該列相交的區塊和行。 在實際解題過程中,行,列和區塊之間的關系并不象上面這些圖中所示的那么明顯,所以需要一定的眼力和細心觀察。一般來說,先看哪個數字在謎題中出現得最多,就從哪個數字開始下手,找到還未填入這個數字的單元(行,列或區塊),利用已填入該數字的單元格與單元之間的關系,看
15、能不能排除一些不可能填入該數字的位置,直到剩下唯一的位置。如果害怕搞不清已經處理過哪些數字的話,可以從數字1開始,從左上角的區塊開始一直檢查到右下角的區塊,看能不能在這些區塊中應用單元排除法。然后測試數字2,以此類推。 單元排除法是應用得最多的直觀法,雖然在實踐中經常會因為粗心而漏掉很多使用這一方法的機會,但只要勤加練習,就可以運用自如。 3.區塊排除法 ( Block Elimination Technique ) 區塊排除法是直觀法中進階的技法。雖然它的應用范圍不如單元排除法那樣廣泛,但用它可能找到用單元排除法無法找到的解。有時在遇到困難無法繼續時,只要用一次區塊排除法,接下去解題就會勢如
16、破竹了。區塊排除法實際上是利用區塊與行或列之間的關系來實現的,這一點與單元排除法頗為相似。然而,它實際上是一種模糊排除法,也就是說,它并不象單元排除法那樣利用謎題中現有的確定數字對行,列或區塊進行排除,而是在不確定數字的具體位置的情況下進行排除的。這句話聽起來似乎不好理解,讓我們先從一個例子入手,看看區塊排除法是怎么應用的。對于上面這個謎題,用基本的單元排除法或是單元唯一法都無法再找到解。這時可以嘗試使用區塊排除法。 我們先從填入數字最多的區塊著手,也就是起始于G4的區塊,該區塊中只有H6和I5為空,且剩余數字1和2還未填入。這樣,我們可以想辦法確定這兩個數字的位置。觀察全局,可以看到D2=2
17、,根據單元排除法,它所在的第2列上不能再出現數字2,所以H2和I2將不能填入2,這使得起始于G1的區塊中數字2可能出現的位置僅剩下I1和I3,見下圖:雖然我們無法確定2在起始于G1的區塊中的確定位置,但幸運的是,能填入2的位置正好都在行I上,也就是說,無論2在I1還是在I3,行I的其他單元格中將不可能再出現數字2,所以可以毫不猶豫地排除在I5填入2的可能性,這樣,對于起始于G4的區塊而言,能填入數字2的位置就只剩下H6了。所以H6=2。接下來,當然毫無疑問,利用單元唯一法,在I5填入數字1。先小結一下上面的求解方法:解題時,實際上是在對目標區塊(主區塊)有影響的區塊(輔助區塊)中應用單元單元排
18、除法,使輔助區塊滿足某些條件并能參與對主區塊的數字排除。實際應用中,可能出現下面四種情況:當某數字在某個區塊中可填入的位置正好都在同一行上,因為該區塊中必須要有該數字,所以這一行中不在該區塊內的單元格上將不能再出現該數字。當某數字在某個區塊中可填入的位置正好都在同一列上,因為該區塊中必須要有該數字,所以這一列中不在該區塊內的單元格上將不能再出現該數字。當某數字在某行中可填入的位置正好都在同一區塊上,因為該行中必須要有該數字,所以該區塊中不在該行內的單元格上將不能再出現該數字。當某數字在某列中可填入的位置正好都在同一區塊上,因為該列中必須要有該數字,所以該區塊中不在該列內的單元格上將不能再出現該
19、數字。其中1,2兩種情況相對常見,也比較容易判斷。上面的示例就是第1種情況。下面我們會看到第2種情況的例子:雖然在起始于A7的區塊中,未填入數字的空單元格多達4個,但我們還是可以輕松地確定數字5的位置。這是因為在起始于G7的區塊中,我們欣喜地發現數字5可能出現的位置正好都在第8列上,這時5的確切位置已經不重要了,因為它已經滿足了上面介紹的第2種情況的條件,因此可以參與對起始于A7的區塊進行數字排除了。在它的影響下,A8和B8中填入數字5的可能性已經不存在,因為它們都在第8列上。這樣,在起始于A7的區塊中,數字5能填入的位置只剩下A9和C9了。這時,我們再利用單元排除法,通過A4位置上的數字5再
20、消除其所在行A上的A9,最終得到能填入5的唯一位置C9。下面看幾個比較少見的例子在行C上,數字3的位置可以通過下面的方法來確定:先看行B,利用單元排除法,通過H2和F3位置上的3進行列排除,得到行B中能填入3的位置為B4和B5。碰巧的是,這兩個單元格都在起始于A4的區塊中,這時已經滿足了上述情況3的條件。利用單元排除法的區塊排除,則行C上的C4和C5都不能再填入3;再加上F3的列排除的共同努力,最終確定數字3在行C上的唯一位置就是C1。第4種情況的例子如下:在這個示例中,只是使用單元排除法和單元唯一法到這一步就繼續不下去了。要想求得數字8在第6列的位置,就必須要借助區塊排除法。先看第4列,通過
21、位于C3和I8的數字8的行排除,使8在第4列可能填入的位置只剩下D4和F4,而這兩個單元格正好都在起始于D4的區塊中。因為第4列不能沒有數字8,而數字8如果填在區塊中的其他位置(如D6,E6或F6)時將迫使D4和F4上不能再填入8,這樣會導致第4列沒有數字8。因此,第6列中的D6,E6和F6能填入數字8的可能性被排除。這樣第6列中就只剩下B6能填入8了。實際解題過程中,還會碰到比較復雜的情況,看下面的謎題:你能確定數字3在起始于A1的區塊中的位置嗎?先看位于C5的數字3,它不僅排除了同一行中C1和C3中填入3的可能性,也同時排除了同一行中C8和C9填入3的可能性,這使得在起始于A7的區塊中,能
22、填入3的位置只剩下B8和B9,見下圖:利用區塊排除法,在起始于A7的區塊中,無論3在B8還是B9,行B中的其他位置都不能再填入3,所以B1,B2和B3都被排除。于是,在起始于A1的區塊中,能填入3的位置僅剩下A1和A2了。但至此我們還無法確定3的準確位置,這時我們還要借助于其他的輔助區塊來進一步排除。觀察起始于D1的區塊,利用D7位置上的3排除同一行的D1,以及用G3位置上的3排除同一列的E3和F3,使區塊中可能填入3的位置只余E2和F2,剛好這兩個位置都在第2列中,符合上面介紹的第2種情況,于是可以把A2也排除掉。最后,我們就可以很肯定地在A1中填入數字3了。這個例子同時使用了多個輔助區塊同
23、時參與排除。在實際使用中雖然這種情況并不常見,但卻也不少見。關鍵在于如何能正確識別并恰當應用區塊排除法。相信通過大量的練習并勤于分析思考,這種方法就可以運用自如,得心應手。下面是其他的一些例子,可以幫助更好地理解并掌握這種技法:4.唯一余數法 ( Sole Number Technique ) 唯一余數法是直觀法中較不常用的方法。雖然它很容易被理解,所以說明這個方法不需要很大篇輻,然而在實踐中,卻不易看出能夠使用這個方法的條件是否得以滿足,從而使這個方法的應用受到限制。與單元唯一法相比,唯一余數法是確定某個單元格能填什么數的方法,而單元唯一法是確定某個數能填在哪個單元格的方法。另外,應用單元唯
24、一法的條件十分簡單,幾乎一目了然。與候選數法相比,唯一余數法相當于顯式唯一法。雖然顯式唯一法是候選數法中最簡單且應用最容易的方法,但在 直觀法中卻正好相反。先看一個例子:對于單元格G9應該填入什么數字,就算你把前面介紹的所有直觀技法都用上,也不得而知。然而,我們通過觀察它所在的行,列和區塊,可以發現除了數字2以外,1到9中其他的數字都出現了,其中行G中包含了7,6,9,5,3和8,第9列中包含了數字5,8,7和1,起始于G7的單元格中包含了3,8,4,7,5和1。這樣,如果G9不填入數字2,就一定會違反游戲“行,列或區塊不能出現重復數字”的規則。所以G9中的數字一定是2總結一下,就是如果某一單
25、元格所在的行,列及區塊中共出現了8個不同的數字,那么該單元格可以確定地填入還未出現過的數字。怎么樣,很簡單吧,但在實踐中卻不那么容易識別。看下面的謎題: 你能看出來對哪個單元格應用唯一余數法嗎? 還有這個謎題:答案分別是E6=9和I7=9。 一般來說,只有在使用基本的排除方法都失效的情況下,才試著使用這個方法來解題。5.組合排除法 ( Combination Elimination Technique) 組合排除法和區塊排除法一樣,都是直觀法中進階的技法,但它的應用范圍要更小一點。一般情況下,基本沒有機會用到這種方法解題,所以要找到相應的例子也都很困難。當然,如果你希望優先以這個技法來解題的話
26、,還是能碰到很多能符合使用組合排除法條件的情況。組合排除法,顧名思義,要考慮到某種組合。這里的組合既包括區塊與區塊的組合,也包括單元格與單元格的組合,利用組合的關聯與排斥的關系而進行某種排除。它也是一種模糊排除法,同樣是在不確定數字的具體位置的情況下進行排除的。下面先看一個例子:對于上面這個謎題,你能確定數字6在起始于G4的區塊中的位置嗎?要想獲得正確的答案初看起來有些困難。因為雖然在G9和H3已經存在了兩個6,但是利用它們只能行排除區塊中的G4和H6兩個單元格,還是無法確定6到底是在I4還是在I5中。這時候,組合排除法就派上用場了。現在撇開起始于G4的區塊,先看它上面的兩個區塊,即起始于A4
27、和D4的區塊。這幾個區塊的共同特點是占有同樣的幾列,也就是第4列至第6列,因此它們之間的數字會相互直接影響。對于起始于A4的區塊,利用A1處已有的數字6進行行排除,可以得到這個區塊中可能填入6的位置只剩下兩個:B5和C6。 對于起始于D4的區塊,利用E7處已有的數字6進行行排除,可以得到這個區塊中可能填入6的位置也剩下兩個:F5和F6。 這時,我們仍無法確定6在這兩個區塊中的確切位置。但不妨對可能出現的情況作一下分析:假設在起始于A4的區塊中,B5=6,則同一區塊中的C6必不為6,而且B5還將列排除F5,這樣在起始于D4的區塊中,只有F6=6。假設在起始于A4的區塊中,C6=6,則同一區塊中的
28、B5必不為6,而且C6還將列排除F6,這樣在起始于D4的區塊中,只有F5=6。簡單地說,只有兩種可能:B5=6且F6=6,或者C6=6且F5=6。決不會再出現其他的情況。但無論是其中哪一種情況,第5列和第6列都會有確定的6出現在這兩個區塊中,也就是說,第5列和第6列的其他位置不可能再出現數字6。這樣,原本無法肯定的6在起始于G4區塊中的位置,一下子就變得明確了。利用起始于A4和D4的區塊對起始于G4的區塊進行列排除,可以把I5排除掉,這樣,就只剩下I4可以填入6了。小結一下,組合排除法的要滿足的條件如下:如果在橫向并行的兩個區塊中,某個數字可能填入的位置正好都分別占據相同的兩行,則這兩行可以被
29、用來對橫向并行的另一區塊做行排除。如果在縱向并行的兩個區塊中,某個數字可能填入的位置正好都分別占據相同的兩列,則這兩列可以被用來對縱向并行的另一區塊做列排除。 讓我們再看一個例子:要想確定數字1在起始于D4的單元格中的位置,我們將設法借助于其橫向上相鄰兩個區塊的幫助。利用I2的列排除,我們可以把起始于D1的區塊中的E2和F2排除掉,這樣,這個區塊中能填入1的位置剩下D1,D3和E1。 利用H7的列排除,可以把起始于D7的區塊中的E7和F7排除掉,再利用A9的列排除,可以把這個區塊中E9和F9排除掉,這樣,這個區塊中能填入1的位置只剩下D8和E8。雖然在起始于D1的區塊中,能填入1的位置多達3個
30、,但是它們正好只分布在行D和行E上,而且在起始于D7的區塊中能填入1的位置所占據的也是這兩行。最終1的位置只可能有三種情況:D1=1且E8=1;或者D3=1且E8=1;或者E1=1且D8=1。無論是哪種情況,行D和行E都會有確定的1出現在這兩個區塊中,也就是說,這兩行的其他位置不會再出現1。于是,借助于這兩個區塊的行排除,我們可以把起始于D4的區塊中的D4和D6排除掉,再利用G4位置的列排除,最終確定1的位置在F6。下面是其他一些使用組合排除法的例子:在實踐中,組合排除法的實際應用機會不如區塊排除法多。但是,掌握這一技法無疑可以大大提高求解謎題的靈活性,從而增加解題的樂趣。6.矩形排除法 (
31、Rectangle Elimination Technique) 矩形排除法雖然淺顯易懂,但一般在實際解題的時候應用得卻比較少。這是因為即使謎題中存在滿足使用這一方法的情況,也很難直接看出來。然而,相對組合排除法而言,在解題過程中倒是能有更多的機會用上矩形排除法。下面先看一個例子:對于這個謎題,如果不用矩形排除法是無法繼續下去的。我們將通過講解這種技法,從而找到數字8在起始于G1的區塊中的位置。乍看之下,好象一籌莫展。因為B2和E3上的8只能列排除左下角這個區塊中的G2, H2,G3和I3這4個單元格,這時仍剩下兩個單元格G1和H1無法確定。讓我們先來留意一下第6列,這一列中暫時沒有8,那么8
32、可能會填入哪幾個單元格中呢?首先,B2中的8行排除了B6,而E3和F4中的8又分別行排除了E6和F6。這樣,能填入8的位置就只剩下C6和I6了。見下圖:同樣,對于第9列,由于F4的行排除,F9不可能填8,所以這一列能填入8的位置也就只剩下C9和I9了。湊巧的是,這兩列中能填入8的位置都在同樣的兩行上,即行C和行I。這時就為我們應用矩形排除法創造了前提條件。如果第6列中C6=8,那么I6和C9一定不能是8。而第9列這時就只剩下I9能填入8了;又或者如果第6列中I6=8,那么C6和I9一定不能是8,而第9列就只剩下C9能填入8了。不可能再有第3種情況。所以,要么C6=8且I9=8,要么I6=8且C
33、9=8。但無論是哪種情況,不難發現,行C和行I都已填入了8,所以這兩行的其他位置不可能再填入8。我們正好可以利用這一點來進行排除。 觀察起始于G1的區塊,我們已經知道現在只剩下G1和I1兩個單元格無法確定了,通過上面的分析,利用矩形排除法排除位于行I上的I1,就可以確定數字8一定在G1上。總結一下,使用矩形排除法的條件如下: 如果一個數字在某兩行中能填入的位置正好在同樣的兩列中,則這兩列的其他的單元格中將不可能再出現這個數字;如果一個數字在某兩列中能填入的位置正好在同樣的兩行中,則這兩行的其他的單元格中將不可能再出現這個數字。讓我們再來看一個例子:做到這一步時,不用矩形排除法的話恐怕是走投無路
34、了。這次還是要在起始于G1的區塊中找到數字4的位置。但我們無法確定4究竟在G2還是G3呢? 先要找找看有沒有滿足矩形排除法條件的情況存在。觀察行B,在這一行中,由于C5的區塊排除,B4和B5都不能為4,再加上H8列排除了B8,這樣行B中能填入4的位置包括B1和B3。 再看行F,由于D6的列排除,使得F6不能填4,所以行F中能填入4的位置只有F1和F3。 幸運的是,行B和行F中能填入4的位置正好都位于同樣的兩列上,即第1列和第3列。根據上面矩形排除法的規則,第1列和第3列中不在行B和行F上的單元格中不能填入4,所以G3不能為4。這樣,起始于G1的區塊中就只有G2能填入4了。 下面是應用矩形排除法
35、的其他一些例子,希望可以幫助大家快速掌握這種方法: 矩形排除法可以說是直觀法中最困難的技法,因為當前的謎題即使滿足應用這一方法的條件,也實在太難發現了。一般情況下,盡量先使用其他相對簡單的直觀法。如果最后連矩形排除法都用上還是無法解題,你可能就需要嘗試候選數刪減法了。候選數法(Candidates Elimination Techniques)對于解決數獨謎題,最常使用的方法就是直觀法和候選數法。在謎題相對簡單時,直觀法可以取得相當好的效果。但是如果謎題比較復雜,直觀法的效果就十分有限,即使通過試探性填數也不一定能夠解題,而這時候選數法卻可以很好地發揮作用。在對數獨謎題求解的電腦程序的設計上,
36、候選數法也因為高效易實現而被廣泛應用。如果用候選數法來解題,必須首先準備一張如下圖所示的候選數柵格表: 初始化時,每個單元格中都包含了1至9所有的數字,它表示該單元格中在解題時還可以選擇填入的數字。很明顯,不在候選數中的數字是不能夠填入該單元格中的。如果某一單元格中已填入一個確定的數字,則根據數獨游戲的規則,即該單元格所在行,列及區塊中都不能再出現這個數字,則該數字應從這些單元格中的候選數字中去除。對于下面的這個謎題: 每填入一個數字時,都要將該單元格中的候選數全部刪除,同時掃描其所在行,列和區塊,看它們所覆蓋的單元格上的候選數中有無該數字: 如果有,就把該數字從候選數中刪除:同理,填入謎題中
37、其他的初始數字,并刪除這些數字各自所在行,列和區塊候選數中的該數字,可以得到下面的候選數柵格表: 注意,填入數字的順序與最終的候選數柵格表無關。這時,我們發現每個單元格中的候選數已經比最初少了許多,真是一個令人興奮的開始。隨后,我們將輔以各種候選數刪減技巧,進一步減少候選數的個數,當某單元格中只剩下唯一的候選數時,該單元格就得到了它的唯一解。細心的朋友已經發現,在上面的候選數柵格表中,單元格I1中已經剩下唯一候選數1,這時我們就可以通過顯式唯一法來解題了。 在候選數刪減法中,常用的算法包括:1.顯式唯一法 (Naked Single) 2.隱式唯一法 (Hidden Single) 3.區塊刪
38、減法 (Intersection Removal) 4.顯式數對法 (Naked Pair) 5.顯式三數集法 (Naked Triplet) 6.顯式四數集法 (Naked Quad) 7.隱式數對法 (Hidden Pair) 8.隱式三數集法 (Hidden Triplet) 9.隱式四數集法 (Hidden Quad) 10.矩形對角線法 (X-wing) 11.XY形態匹配法(XY-wing) 12.XYZ形態匹配法(XYZ-wing) 13.三鏈數刪減法 (Swordfish) 14.WXYZ形態匹配法(WXYZ-wing) 1. 顯式唯一法 (Naked Single) 這是候選
39、數刪減法中最簡單的一種方法,就是掃描候選數柵格表,如果哪個單元格中只剩下一個候選數,就可應用顯式唯一法,在該單元格中填入這個數字,并在相應行,列和區塊的候選數中刪除該數字。 在下面的圖中:單元格I1有唯一的候選數1,則毫無疑問地把數字1填入該單元格中,并掃描其所在行,列和區塊的候選數中有無數字1:如果有,則把1從這些單元格的候選數中刪除:顯式唯一法雖然簡單,但卻是最有效的候選數刪減法之一;尤其在謎題相對簡單時,有時單單使用顯式唯一法就可以解題。2. 隱式唯一法 (Hidden Single) 見文知義,隱式唯一法也是唯一候選數法的一種,但它肯定不如顯式唯一法那樣顯而易見。我們知道,如果某一個單
40、元格中只有一個候選數字,這時可以毫不猶豫地填入它;但是有沒有這種情況,即使某個單元格中有不止一個候選數字,我們也可以輕易地推斷出這個單元格的正確解答呢? 考慮下面的情況:在第7列中,單元格B7中雖然有多個候選數,但觀察整列后我們發現,只有這個單元格中有數字6。根據數獨游戲的規則,每一列中都必須要有從1到9的所有數字,而同時6卻只能出現在這個單元格中,所以很顯然B7=6。當然,別忘了把6從B7所在的行,列和區塊中刪除。同樣,在下圖中:觀察行B后我們發現,只有單元格B8中含有數字7。同理,B8是該行中唯一可以填入數字7的單元格,所以B8=7。另外,我們還要掃描相應行,列和區塊,刪除其中的候選數7。
41、當然,這種隱藏的唯一候選數也可能躲在區塊中,看下圖:對于起始于A1的區塊而言,數字8只出現在單元格A2的候選數中,所以A2=8。從相應行,列和區塊,刪除其中的候選數8。 隱式唯一法是顯式唯一法的有力補充,很多稍復雜的題都可以在這兩種方法的交替使用下得以解決。 3. 區塊刪減法 (Intersection Removal) 應用顯式唯一法和隱式唯一法只能解決簡單的謎題,遇到稍復雜的謎題,還是要靠其他的方法。區塊刪減法也是比較常用的方法,它的目的是盡量刪減候選數,而不一定要生成某一單元格的唯一解(當然,產生唯一解更好)。區塊刪減法是利用區塊中的候選數和行或列上的候選數之間的交互影響而實現的一種刪減
42、方法,它分為兩種情況:區塊對行或列的影響 觀察下圖:可以看到在起始于A7的區塊中,數字9只出現在A9和C9的候選數中,更巧的是,A9和C9正好都在同一列上,即第9列。這時就可以應用區塊刪減法了。具體地說,在起始于A7的區塊中,數字9只能填在A9或是C9中,又因為這兩個單元格都在第9列上,所以無論數字9填在哪個單元格中,第9列的其他單元格中都不能再填數字9,所以要把9從它們的候選數中刪除。在上圖中,位于第9列的單元格E9中的候選數9將被刪除。下圖說明的是區塊對行的影響:在起始于G1的區塊中,只有H2和H3可以填入數字3,而這兩個單元格正好都在行H中。同樣的道理,在這個區塊中無論數字3填入H2還是
43、H3,行H中的其他單元格中都不可能再填入3,所以在單元格H4,H6和H7的候選數中的3將被刪除。行或列對區塊的影響 與“區塊對行或列的影響”相近但卻不同,“行或列對區塊的影響”著重于先對行或列進行分析。觀察下圖:在第5列中,8只出現在D5和F5的候選數中;也就是說,第5列中的數字8只能填入這兩個單元格其中的一個。碰巧的是,這兩個單元格正好都位于起始于D4的區塊中,結果使得這一區塊中的數字8也不能填入區塊的其他單元格中,所以D4,E4,E6和F6的候選數中的8將被刪除。 同樣,下圖說明了行對區塊的影響: 在行E中,只有E5和E6能填入數字6,而這兩個單元格又剛好都在起始于D4的區塊中,所以該區塊
44、中的其他單元格內不能再填入數字6,即6將從單元格D5和F5的候選數中刪除。總結一下區塊刪減法的條件,就是在某一區塊中,當所有可能出現某個數字的單元格都位于同一行時,就可以把這個數字從該行的其他單元格的候選數中刪除。在某一區塊中,當所有可能出現某個數字的單元格都位于同一列時,就可以把這個數字從該列的其他單元格的候選數中刪除。 在某一行(列)中,當所有可能出現某個數字的單元格都位于同一區塊中時,就可以把這個數字從該區塊的其他單元格的候選數中刪除。雖然區塊刪減法應用比較廣泛,但是還是要先給大家潑盆冷水。因為在很多時候,即使滿足了區塊刪減的條件,也可能會發生沒有候選數可以刪減的情況,讓人空歡喜一場。其
45、實,這個問題對其他稍復雜的方法都是普遍存在的。4. 顯式數對法 (Naked Pair) 顯式數對法在很多謎題中都可以得到應用,它的條件比較容易滿足,而且顯而易見。先看下圖:在行E中,E2和E8中候選數只有兩個,且都是2和3,即構成一個2, 3的數對。這使得該行中其他單元格中不能再出現2或3。為什么呢,因為假設E2=2,則E8一定要填3;反之,假設E2=3,則E8則一定填2,不會再出現其他的情況。所以2和3必然不能成為該行中其他單元格的候選數。這樣,E3,E4和E5的候選數中都不能再有2和3。對于列也是這樣:在第3列中,數對6, 8只出現且都出現在A3和H3中,所以其他單元格里都不能再有這兩個
46、數字。這樣,C3的候選數中將刪除6和8,而F3的候選數中將刪除8。同樣,別忘了還有區塊: 觀察起始于G4的區塊,可以發現G5和I4中含有數對2, 4,這樣,該區塊中其他的單元格里都不能再有數字2和4,這次受影響的有4個單元格,分別是G4,H4,I5和I6。總結一下顯式數對的條件,也就是,在一個行,列或區塊中,如果有兩個單元格都包含且只包含相同的兩個候選數,則這兩個候選數字不能再出現在該行,列或區塊的其他單元格的候選數中。5. 顯式三數集法 (Naked Triplet) 顯式三數集法并不如顯式數對法那樣常見,但它們的原理卻很相似。顯式數對法要求同樣的2個數字都出現在某行,列或區塊的2個單元格中
47、,且這2個單元格的候選數不能包含其他的數字。同樣,顯式三數集法要求的是3個數字要出現在3個位于同一行,列或區塊的單元格中,且這3個單元格的候選數中不能包含其他數字。但不同的是,顯式三數集法不要求每個單元格中都要包含這3個數字。例如,對于數字集2,4,5,如果在某行,列或區塊中有3個單元格的候選數分別為下面幾種情況時,都可應用顯式三數集法,即3個單元格的候選數集可以分別為:2, 4, 5 2, 4, 5 2, 4, 5,或 2, 4 4, 5 2, 5,或 2, 4, 5 2, 5 4, 5,或 2, 4, 5 4, 5 2, 4, 5,或 . 也就是說,要形成顯式三數集,則必須要有3個在同一行
48、,列或區塊中的單元格,每個單元格中至少要有2個候選數,且它們的所有候選數字也正好都是一個三數集的子集。由于這個三數集中的3個數字正好可以分別填入這3個單元格中,所以該行,列或區塊中其他的單元格中不可能再填入這3個數字。但要注意的是,下面的這種情況不是顯式三數集:2, 4, 5 2, 4 2, 4其中2, 4和2, 4可應用顯式數對法,所以第一個候選數集2, 4, 5將只能剩下候選數,這時就可應用顯式唯一法了。看下圖:在行D中,D1,D7和D8中分別包含候選數集3, 5, 9,3, 5, 9和5, 9,根據上面的知識,可以判斷出這是一個顯式三數集,因此數字3,5和9不可能再出現在行內其他的單元格
49、中,所以D4和D6的候選數中的3,5和9將被刪除。下面是列中的顯式三數集的例子: 在第2列中,G2,H2和I2中分別包含候選數集2, 6,2, 5和2, 5, 6,所以數字2,5和6只能在這三個單元格中分別填入,而不可能填入到該列的其他單元格中,因此A2,B2和E2的候選數中的2,5和6將被刪除。 細心的朋友可能還發現,G2,H2和I2不僅都在第2列中,而且又恰好都在起始于G1的區塊中,對于數字5,已經符合區塊刪減法的條件,可惜的是,第2列中其他單元格的候選數中都沒有5可以刪減。 同樣,顯式三數集還有在區塊中的可能: 在起始于D7的區塊中,D8,D9和E9中分別包含了候選數集4, 9,4, 8
50、, 9和8, 9,這樣區塊中其他的單元格中不能再填入數字4,8和9,可以刪減的單元格是E7和E8。6. 顯式四數集法 (Naked Quad) 顯式四數集法比較少見,如果你已經對顯式三數集法比較了解,則對顯式四數集法也會很快掌握。先舉個例子,對于數字集1, 2, 4, 5,如果在某行,列或區塊中有4個單元格的候選數分別為下面幾種情況時,都可應用顯式四數集法,即4個單元格的候選數集可以分別為:1, 2, 4, 5 1, 2, 4, 5 1, 2, 4, 5 1, 2, 4, 5,或 1, 2, 4 1, 4, 5 2, 5 1, 2,或 1, 2, 4, 5 2, 5 2, 4, 5 1, 2,
51、 4, 5,或 2, 5 4, 5 1, 2, 5 1, 2, 4,或 1, 2, 5 1, 2, 4, 5 1, 2, 4, 5 2, 4,或 . 這樣的組合情況可以很多。也就是說,要形成顯式四數集,則必須要有4個在同一行,列或區塊中的單元格,每個單元格中至少要有2個候選數,且它們的所有候選數字也正好都是一個四數集的子集。由于這個四數集中的4個數字正好可以分別填入這4個單元格中,所以該行,列或區塊中其他的單元格中不可能再填入這4個數字。但要注意的是,下面的這種情況不是顯式四數集:1, 2, 4, 5 2, 4 2, 5 2, 4, 5其中2, 4 2, 5和2, 4, 5可應用顯式三數集法,
52、所以第一個候選數集1, 2, 4, 5將只能剩下候選數1,這時就可應用顯式唯一法了。看下圖:很明顯,在行D中,D1,D4,D6和D8中分別包含了候選數集3, 5, 6,2, 5, 6,2, 5, 6和3, 5, 6,即分別都是四數集2, 3, 5, 6的子集。這樣在行D中,數字2,3,5和6就只能填入這4個單元格中,所以D3和D7的候選數中將不能包含這幾個數字。下面是顯式四數集在列中的例子: 在第9列中,C9,D9,E9和G9中分別包含了候選數集1, 7, 8,1, 8,6, 7, 8和6, 7, 8,即分別都是四數集1, 6, 7, 8的子集。這樣數字1,6,7和8就不能填入該列中除這四個單
53、元格之外的單元格中,所以A9和B9的候選數中將不能出現這四個數字。同樣,顯式四數集也可以出現在區塊中:在起始于A7的區塊中,B9,C7,C8和C9中分別包含了候選數集6, 7,1, 6, 8,7, 8和1, 6, 7, 8,即它們分別都是四數集1, 6, 7, 8的子集。這樣,數字1,6,7和8就不能填入該區塊中除這四個單元格之外的單元格中,所以A7和A8的候選數中將不能出現這四個數字。 當然,掌握了顯式四數集法,我們同樣可以演繹出顯式五數集法,顯式六數集法等,但因為顯式四數集法出現的幾率已經較小,所以我們不指望推演出的更多方法能在解決數獨謎題上帶給我們有效的幫助。 7. 隱式數對法 (Hidden Pair) 對比顯式數對法,隱式數對法也需要在同一行,列或區塊中尋找兩個單元格,而這兩個單元格上都包含有一個數對(兩個數字),且這個數對不會出現在該行,列或區塊的其他單元格上。然而,應用隱式數對法卻要困難得多,因為它與顯式數對法不同的是,包含有數對的單元格的候選數中可能還包含有其他的數字。先看下圖:可以看到,在行A中,數對3, 6只出現在
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 湖南省耒陽市2025屆初三下學期第二次月考試題數學試題試卷含解析
- 遼寧省沈陽市一三四中學2025屆初三下學期周練試卷(四)生物試題含解析
- 山西省大同市左云縣東北小學校2024-2025學年數學四下期末學業水平測試試題含解析
- 吉林城市職業技術學院《Spss統計軟件》2023-2024學年第二學期期末試卷
- 山東政法學院《犯罪心理學專題》2023-2024學年第一學期期末試卷
- 皖北衛生職業學院《機械制圖Ⅰ》2023-2024學年第二學期期末試卷
- 上海市復旦附中2025屆高三補習班下學期第四次月考數學試題含解析
- 欽州幼兒師范高等專科學校《民族戲曲與說唱藝術》2023-2024學年第一學期期末試卷
- 山東省2025屆數學三下期末考試試題含解析
- 四川省棠湖中學2024-2025學年高三語文試題高考沖刺七含解析
- 人教版高中數學選擇性必修第三冊8-1-1變量的相關關系【課件】
- 《應用文寫作》高職全套教學課件
- LYT 2093-2013 防護林體系生態效益評價規程
- 綠城地產集團標準化運營手冊地產客服項目交付項目運營手冊之交付工作操作指引V1
- 風電項目風機吊裝專項施工方案
- GB 1499.1-2024鋼筋混凝土用鋼第1部分:熱軋光圓鋼筋
- 葉片維修工-B卷考試附有答案
- 2024年飯店轉讓合同簡單版(三篇)
- 小學一二年級必背古詩詞73首帶拼音
- 正壓式空氣呼吸器操作使用方法培訓課件
- 2024年信陽職業技術學院單招職業適應性測試題庫帶答案
評論
0/150
提交評論