標籤:

數獨解法

2009-04-06 12:27:34|分類:默認分類 |字型大小訂閱唯一解法前言數獨這個數字解謎遊戲,完全不必要用到算術!會用到的只是推理與邏輯。剛開始接觸數獨時,即使是只 須用到"唯一解"技巧的簡易級謎題,就已可讓我們焦頭爛額了,但是隨著我們深陷數獨的迷人世界之後,這 類簡易級的數獨謎題必定在短時間內難再使我們獲得征服的滿足。於是,當我們逐步深入、進階到更難的游 戲後,我們將會需要發展齦?多的解謎技巧。雖然最好的技巧便是我們自己發現的竅門,這樣我們很容易??能記住它們,運用自如,不需要別人來耳提面命。但是如果完全不去觀摩學習他人發展出來的技巧,而全靠 自己摸索,那將是一個非常堅苦的挑戰,也不是正確的學習之道!所以讓我們一齊來探討數獨的解謎方法吧!數獨的解謎技巧,剛開始發展時,以直觀式的唯一解及摒除法為主,對於初入門的玩家來說,這也是一般人 較容易理解、接受的方法,對於一般簡易級或中級的數獨謎題,如果能靈活運用此二法則,通常已遊刃有餘。唯一解詳說當數獨謎題中的某一個宮格因為所處的列、行或九宮格已出現過的數字已達 8 個,那麼這個宮格所能填入 的數字就剩下這個還沒出現過的數字了。

<圖 1> (9, 8)出現唯一解了<圖 1>是最明顯的唯一解出現時機,請看第 8 行,由 (1,8) ~(8,8) 都已填入數字了,只剩(9,8)還是 空白,此時(9,8)中應填入的數字,當然就是第 8 行中還沒出現過的數字了!請一個個數字核對一下, 哦!是數字 8 還沒出現過,所以(9,8) 中該填入的數字就是數字 8 了。

<圖 2> (8, 9)出現唯一解了<圖 2>是另一個明顯出現唯一解的情形,請看第 8 列,由 (8,1) ~(8,8) 都已填入數字了,只剩(8,9)還是 空白,此時(8, 9)中應填入的數字,當然就是第 8 列中還沒出現過的數字了!請一個個數字核對一下, 哦!是數字 9 還沒出現過,所以(8, 9) 中該填入的數字就是數字 9 了。

<圖 3> (7, 5)出現唯一解了<圖 3>是另一種明顯出現唯一解的情形,請看下中九宮格,在這個九宮格中除了(7, 5)還是空白外,其他宮格 都已填有數字了,所以(7, 5)中應填入的數字,當然就是下中九宮格中還沒出現過的數字了!請一個個數字核對一下, 哦!是數字 1 還沒出現過,所以(7, 5) 中該填入的數字就是數字 1 了。

<圖 4> 一般情形下的唯一解類似 <圖 1>~<圖 3>這種明顯出現唯一解的情形,在一般情形之下及解題初期是不太可能出現的! <圖 4>是一個最典型的簡易級數獨謎題,如果單純觀察某一個行、列或九宮格,沒有一處是已出現 8 個數字的, 難道如此就無解了嗎?非也!非也!在此圖中,出現唯一解的宮格其實有 3 處之多!你能找出來嗎?沒錯,在一般情形之下及解題初期,唯一解的尋找必須綜合所處的行、列及九宮格三者,同時過濾篩選出已出現 的數字才行!如果漏掉其一,可能就無法找出唯一解的出現位置了。現在且不忙著填入數字,先來找找看<圖 4>中 目前已出現的唯一解在哪兒吧:第一個唯一解位置在(2, 3):(2, 3) 所處的第 2 列中已出現的數字是:9、3、5、7。所處的第 3 行中 已出現的數字是:4、2、6、8。至於所處的上左九宮格中,已出現的數字是:2、9、4。所以綜合而言, 受其所處位置的行、列及九宮格影響,不得再使用並填入(2, 3) 的數字計有:2、3、4、5、6、7、8、9。 能用來填入的數字確實只剩數字 1 這個唯一的解了。第二個唯一解位置在(8, 7):(8, 7) 所處的第 8 列中已出現的數字是:1、2、8、6。所處的第 7 行中 已出現的數字是:3、9、5、4。至於所處的下右九宮格中,已出現的數字是:4、6、5。所以綜合而言, 受其所處位置的行、列及九宮格影響,不得再使用並填入(8, 7) 的數字計有:1、2、3、4、5、6、8、9。 能用來填入的數字確實只剩數字 7 這個唯一的解了。第三個唯一解位置在(5, 5):(5, 5) 所處的第 5 列中已出現的數字是:1、7。所處的第 5 行中 已出現的數字是:2、5。至於所處的中央九宮格中,已出現的數字是:3、6、8、9。所以綜合而言, 受其所處位置的行、列及九宮格影響,不得再使用並填入(5, 5) 的數字計有:1、2、3、5、6、7、8、9。 能用來填入的數字確實只剩數字 4 這個唯一的解了。以上所謂的三個唯一解位置,是以<圖 4>現況未填入任何數字之前而言,如果開始填入數字,出現唯一解的位置 可能將隨之增加。例:當(8, 7) 填入數字 7 之後,(7, 7)將出現唯一解 1;如果再將數字 1 填入(7, 7), 在(7, 8)又將出現唯一解 3;......如此不斷循環下去,就可以將整個謎題解出了。唯一候選數法概說依照候選數法概說一文中,候選數表的製作規則,我們可以知道:可以填入某一 個宮格的數字,一定會列於該宮格的候選數中;不在候選數中的數字,就不能填入該宮格中。所以如果在候選數表中發現某一個宮格的候選數僅有 1 個數字,那就是表示:不必再考慮了!這個宮格就是 只能填入這個數字啦!如果填入別的數字,就會違反數獨的填制規則的。利用「找出候選數表中,候選數僅有 1 個數字的宮格來,並填入該候選數」的方法就叫做唯一候選數法(Singles Candidature, sole Candidate)。唯一候選數法示例

<圖 1>數獨謎題的候選數表<圖 1> 是我們在候選數法概說一文中完成的候選數表,其中有好幾個宮格的候選數 都只有 1 個,所以可以利用唯一候選數法來進行填制。先還不要填入數字,我們先來找找看,有哪些宮格有 唯一候選數?在 (2, 7) 有唯一候選數 7。在 (5, 5) 有唯一候選數 5。在 (8, 3) 有唯一候選數 3。哇!同時出現了 3 個唯一候選數啊!那麼,先填入哪一個會不會影響填制結果呢?當然不會了, 只要你高興,喜歡先填哪一個都沒問題的。好,就在這 3 個宮格中填入他們的唯一候選數吧,填制結果如<圖 2>:

<圖 2>哇!又有唯一候選數出現了呢!沒錯,一般簡易級的數獨謎題,如果使用直觀式的 唯一解法及摒除法來解題,即使是數獨老手,也要花費相當的工夫才能完成; 但是如果採用唯一候選數法,從候選數表製作完成開始,唯一候選數將一個一個接連不斷的出現,輕輕鬆鬆的 就可以完成解題啦!<圖 3> 是 <圖 1> 的完成解。

<圖 3>完成解隱性三鏈數刪減法概說遇到了高級、困難級的數獨謎題,使得唯一候選數法和隱性唯一候選數法黔驢技窮的時候,就是各種刪減法上場的時機了。在各種的刪減法中,哪一個要先用 是隨個人之喜好的,並無限制。本頁介紹的例子當然可用其他刪減法完成解題,但還是要以隱性三鏈數刪減法優先??!

<圖 1>請看<圖 1>的第 2 列,數字 1、7、8 只出現在(2, 1)、(2, 7)和(2, 8)這三個宮格的候選數中;這時 隱性三鏈數刪減法的條件已成立了!這表示第 2 列的數字 1、7 和 8 將只能填到這三個宮格中,因為: 如果讓別的數字填入這三個宮格之中後,這三個相異的數字能填入的可能宮格就只剩下兩個,而那是 不可能的事!所以若這三個宮格的候選數中還有其他數字,全部是多餘無用的,它們已不可能再用來 填入這些宮格中了,所以可以毫不考慮的把它們刪減掉。於是(2, 7)和(2, 8)這兩個宮格候選數中的 6 都可被安全的刪減掉;其中(2, 7)的候選數少了數字 6,將使得(8, 7)出現行隱性唯一候選數 6 ,於是 可用隱性唯一候選數法來填入下一個解了。整理一下:當某 3 個數字僅出現在某列的某三個宮格候選數中時,就可以把這三個宮格的候選數刪減成該 3 個數字。 同理,當某 3 個數字僅出現在某行的某三個宮格候選數中時,就可以把這三個宮格的候選數刪減成該 3 個數字。 當然,當某 3 個數字僅出現在某個九宮格的某三個宮格候選數中時,就可以把這三個宮格的候選數刪減成該 3 個數字。利用「找出某 3 個數字僅出現在某行、某列或某一個九宮格的某三個宮格候選數中的情形,進而將這三個 宮格的候選數刪減成該 3 個數字」的方法就叫做隱性三鏈數刪減法(Hidden Triples)。本法其實為隱性數對刪除法的推廣,而且還可以繼續加以推廣:隱性四鏈數刪減法就是:「找出某 4 個數字僅出現在某行、某列或某一個九宮格的某四個宮格候選數中 的情形,進而將這四個宮格的候選數刪減成該 4 個數字」的方法。 隱性五鏈數刪減法就是:「找出某 5 個數字僅出現在某行、某列或某一個九宮格的某五個宮格候選數中 的情形,進而將這五個宮格的候選數刪減成該 5 個數字」的方法。 ......如果願意的話,你確實是可以這樣推廣的,只是,實用上是否有其應用的價值或空間呢?隱性三鏈數刪減法示例隱性三鏈數刪減法一共有 3 種狀況:第一種發生在行、第二種是發生在列、第三種則發生在九宮格。<圖 1> 就是 發生在列的例子了,其他的情況舉例如下:

<圖 2><圖 2> 是隱性三鏈數刪減發生在行的例子:圖中第 4 行的數字 2、4、9 只出現在 (4, 4)、(5, 4)及(6, 4) 這三個宮格的候選數中,所以可以將三個宮格候選數中 2、4、9 以外的數字安全的刪減掉,(4, 4)的候選數刪減成2、4; (5, 4)的候選數刪減成2、4、9;(6, 4)的候選數刪減成 9;出現了唯一候選數啦!

<圖 3><圖 3> 是隱性三鏈數刪減發生在九宮格的例子:圖中中央九宮格的數字 2、5、9 只出現在 (5, 4)、(5, 6)及(6, 4) 這三個宮格的候選數中,所以可以將三個宮格候選數中 2、5、9 以外的數字安全的刪減掉, (5, 4)的候選數刪減成2、5、9;(5, 6)的候選數刪減成2、5;(6, 4)的候選數刪減成 9;出現了唯一候選數啦!

<圖 4>像 <圖 1>~<圖 3> 這樣只經一次刪減就出現下一個解的情況當然不錯了,但有時可沒法這樣順心, <圖 4> 就是一個例子。下一個解將出現在(5, 6) 這個宮格,你能找出該填入什麼數字嗎?以目前所學到的方法,要解出下一個解,需要二個步驟:先看中左九宮格吧!由於只剩(5, 1)~(5, 3)這個區塊尚未填入數字,所以可用區塊刪減法將 第 5 列其他區塊候選數中的 1、3、4 全部刪減掉,但實際上僅能刪到(5, 4)及(5, 6)候選數的數字 4 而已。 接下來請觀察第 6 行! 由於數字 1、4、9 只出現在 (2, 6)、(8, 6)及(9, 6) 這三個宮格的候選數中 [因為(5, 6)的候選數在上一步驟中已被刪減為5、8 了 ], 所以可用隱性三鏈數刪減將三個宮格候選數中 1、4、9 以外的數字安全的刪減掉, (2, 6)的候選數刪減成1、4、9;(9, 6)的候選數沒變;(8, 6)的候選數則由 2、4、5、8、9 刪減成 4、9; 由於 5 被刪減掉了,使得(5, 6) 出現了行隱性唯一候選數5啦!隱性數對刪減法概說遇到了高級、困難級的數獨謎題,使得唯一候選數法和 隱性唯一候選數法黔驢技窮的時候,就是各種刪減法上場的時機了。在各種的刪減法中,哪一個要先用 是隨個人之喜好的,並無限制。本頁介紹的當然就要以隱性數對刪減法優先??!

<圖 1>請看<圖 1>的上右九宮格,數字 8、9 都只出現在(2, 8)和(2, 9)這兩個宮格的候選數中;這時隱性數對刪減法 的條件已成立了!這表示上右九宮格的數字 8 和 9 將只能填到這兩個宮格中,而且:如果數字 8 將填入(2, 8), 那麼(2, 9)就一定要填入數字 9;反之,如果數字 9 將填入(2, 8),那麼(2, 9)就一定要填入數字 8; 不論哪一個狀況出現,(2, 8)和(2, 9)這兩個宮格的候選數中若還有其他數字,全部是多餘無用的,因為這 兩個宮格若填入數字 8、9 以外的數字,那麼上右九宮格的數字 8 或 9 就將無處可填了。候選數的意義是 可能填入該宮格的數字,而這兩個數字以外的數字已不可能再用來填入本宮格中了,所以可以毫不考慮的把 它們刪減掉。當(2, 8)和(2, 9)這兩個宮格的候選數都安全的刪減成數字 8、9 之後,(2, 5)出現了列隱性 唯一候選數 2 ,於是可用隱性唯一候選數法來填入下一個解了。整理一下:當某個數對僅出現在某個九宮格的某兩個宮格候選數中時,就可以把這兩個宮格的候選數刪減成該數對。同理,當某個數對僅出現在某列的某兩個宮格候選數中時,就可以把這兩個宮格的候選數刪減成該數對。當然,當某個數對僅出現在某行的某兩個宮格候選數中時,就可以把這兩個宮格的候選數刪減成該數對。利用「找出某個數對僅出現在某行、某列或某一個九宮格的某兩個宮格候選數中的情形,進而將這兩個 宮格的候選數刪減成該數對」的方法就叫做隱性數對刪減法(Hidden Pairs)。當隱性數對刪減法完成後,通常還可引發數對刪減法;以<圖 1>為例,當(2, 8)和(2, 9)這兩個宮格的候選數 都安全的刪減成數字 8、9 之後,還可利用數對刪減法把 (2, 1)、(2, 2)、(2, 3) 這三個c格候選數中的數字 8 刪減掉。隱性數對刪減法示例隱性數對刪減法一共有 3 種狀況:第一種發生在行、第二種是發生在列、第三種則發生在九宮格。<圖 1> 就是 發生在九宮格的例子了,其他的情況舉例如下:

<圖 2><圖 2> 是隱性數對刪減發生在行的例子:圖中第 2 行的數對 4、6 只出現在 (3, 2)及(9, 2) 這兩個宮格 的候選數中,所以可以將(3, 2)及(9, 2)的候選數安全的刪減成數對 4、6;而經此一刪,(3, 3) 宮格出現 了列隱性唯一候選數 1 啦!

<圖 3><圖 3> 是隱性數對刪減發生在列的例子:圖中第 7 列的數對 4、7 只出現在 (7, 1)及(7, 8) 這兩個宮格 的候選數中,所以可以將(7, 1)及(7, 8)的候選數安全的刪減成數對 4、7;而經此一刪,(8, 1) 宮格出現 了行隱性唯一候選數 2 啦!三鏈列刪減法概說遇到了高級、困難級的數獨謎題,使得唯一候選數法和 隱性唯一候選數法黔驢技窮的時候,就是各種刪減法上場的時機了。在各種的刪減法中,哪一個要先用 是隨個人之喜好的,並無限制。本頁介紹的例子當然可用其他刪減法完成解題,且本刪減法成立的條件 和其他方法相比稍嫌繁雜,但為了介紹,在進行解題時還是要以三鏈列刪減法優先??!

<圖 1>請看<圖 1>第 1、4、6 列的數字 5 ,都只出現在第 1、5、8 行的宮格候選數中;這時 三鏈列刪減法的條件已成立了!這表示第 1 行、第 5 行及第 8 行的數字 5 將只能被填到第 1 、4、6 列了,因為:第 1 列的數字 5 只出現在(1, 1)及(1, 8),所以數字 5 只能填到這兩個宮格;先假設第 1 列的數字 5 將被填到(1, 1),第 1 行就不能再填數字 5 了,所以第 4 列 的數字 5 只好填到(4, 5),第 6 列的數字 5 只好填到(6, 8); 另外,假設第 1 列的數字 5 將被填到(1, 8),第 8 行就不能再填數字 5 了,所以第 6 列的數字 5 只好填到(6, 1)或(6, 5); 如果第 6 列的數字 5 填到(6, 1),第 4 列的數字 5 就要填到(4, 5); 如果第 6 列的數字 5 填到(6, 5),第 4 列的數字 5 就要填到(4, 1);不論哪一種情況發生,第 1、5、8 行的數字 5 一定要填在第 1、4、6 列的交點,別的宮格已不能再使用 數字 5 來填入了,所以若其他宮格的候選數中還有數字 5,全部是多餘無用的, 可以毫不考慮的把它們刪減掉。於是(5, 1)、(5, 5)、(9, 5)和(1, 8)、(2, 8)這五個宮格候選數中的 5 都可被安全的刪減掉;其中(9, 5)的候選數少了數字 5,將使得(9, 4)出現列隱性唯一候選數 5 ,於是 可用隱性唯一候選數法來填入下一個解了。整理一下:當某個數字在某三列僅出現在相同的三行時,就可以把這三行其他宮格候選數中的該數字刪減掉。 同理,當某個數字在某三行僅出現在相同的三列時,就可以把這三列其他宮格候選數中的該數字刪減掉。利用「找出某個數字在某三列僅出現在相同三行的情形,進而將該數字自這三行其他宮格候選數中刪減掉」; 或「找出某個數字在某三行僅出現在相同三列的情形,進而將該數字自這三列其他宮格候選數中刪減掉」的方法 就叫做三鏈列刪減法(Swordfish)。本刪減法其實是矩形頂點刪減法的推廣,如果你願意的話,還可以繼續推廣:四鏈列刪減法:利用「找出某個數字在某四列僅出現在相同四行的情形,進而將該數字自這四行其他宮格 候選數中刪減掉」;或「找出某個數字在某四行僅出現在相同四列的情形,進而將該數字自這四列其他 宮格候選數中刪減掉」的方法 五鏈列刪減法:利用「找出某個數字在某五列僅出現在相同五行的情形,進而將該數字自這五行其他宮格 候選數中刪減掉」;或「找出某個數字在某五行僅出現在相同五列的情形,進而將該數字自這五列其他 宮格候選數中刪減掉」的方法 六鏈列刪減法:...... 不過如果真的這樣做,實際應用時,能夠用上的機率大概不多就是了。遇到了高級、困難級的數獨謎題,使得唯一候選數法和 隱性唯一候選數法黔驢技窮的時候,雖然你可以優先使用三鏈列刪減法來尋找下一個解;但大部分的人在 使用刪減法的優先順序上,通常都會將三鏈列刪減法排在稍後一點,為什麼要如此安排,在實際使用一段時間之後, 相信你自能體會了,但這個方法又是不可或缺的,如果不會運用本刪減法,有很多高級的數獨謎題就將無解了。三鏈列刪減法示例三鏈列刪減法只有 2 種狀況:第一種的刪減發生在行、第二種的刪減發生在列。<圖 1> 就是 刪減發生在行的例子了,第二種的情況舉例如下:

<圖 2><圖 2> 是三鏈列刪減發生在列的例子:圖中第 3、5、8 行的數字 2 只出現在第 3、4、5 列, 所以可以將數字 2 自(4, 6)、(5, 6)的候選數中安全的刪減掉,其中(5, 6) 的候選數由 2、5 刪減成 5 時,出現唯一候選數啦!區塊刪減法概說遇到了高級、困難級的數獨謎題時,唯一候選數法和 隱性唯一候選數法仍有其黔驢技窮的時候;這時就是區塊刪減法上場的時機了,往後將要介紹的 數對刪減法(Naked Pairs)、隱性數對刪減法(Hidden Pairs)、三鏈數刪減法(Naked Triples)、 隱性三鏈數刪減法(Hidden Triples) 、矩形頂點刪減法(X-Wing)、三鏈列刪減法(Swordfish)都具有類似的特性:使用這 些技巧的目的僅在刪減候選數的數目,刪減之後,還是得使用唯一候選數法和隱性唯一候選數法來 找出下一個解並填入數字的。當使用唯一候選數法或隱性唯一候選數法找不出下一個解時,到底該先使用哪一個刪減法呢?隨您高興的用吧! 如果你比較擅長使用數對刪減法,那就先用數對刪減法吧!如果你認為區塊刪減法比較好用,那就先用數對刪減法吧! ......;介紹時總有先後的次序,但並不表示先介紹的就較好用或必須先用哦!只要能達到:「安全刪減掉候選數, 並找出下一個解」的目的,使用哪一種刪減法都是可以的。

<圖 1>請看<圖 1>,這時若使用唯一候選數法或隱性唯一候選數法是找不出下一個解來的!就先來試試區塊刪減法吧。 請觀察第 9 行:數字 1 在本行各宮格的候選數中,是不是僅出現在(1,9)~(3,9)的這一個區塊中?太好了,區塊刪減 的條件已有了;因為這表示第 9 行的數字 1 只能填在(1,9)~(3,9)的這一個區塊中,而不論填在本區塊 的哪一個宮格中,上右九宮格的其他宮格將因本九宮格已出現數字 1,而不得再填入 1,否則就違反數獨填制的規則 啦!所以(1, 7)~(3, 7)及(1, 8)~(3, 8)這兩個區塊的宮格,如果其候選數中包含有數字 1,就可以毫不考慮的 把它刪除掉,因為候選數的意義是可能填入該宮格的數字,而這個數字已不可能再用來填入該宮格中了。啊!太好啦! (1, 7)的候選數中包含有數字 1,所以可以把 (1, 7) 的候選數由 1、6 刪減成 6,於是可用唯一候選數法來填入 下一個解了。當區塊刪減法的條件成立時,可別高興得太早,因為很有可能找不到可刪減的數字,例如:在<圖 1>的第 1 行中, 數字 2 在本行的各宮格候選數中,僅出現在(4, 1)~(6, 1)這一個區塊中,而不論數字 2 將來會被填到本區塊 的哪一個宮格中,將使得數字 2 不得再填入(4, 2)~(6, 2)及(4, 3)~(6, 3)這兩個區塊中;但請找找看! 這兩個區塊各宮格的候選數中全部沒有數字 2,所以是白忙了一場,條件是成立了,但候選數並未因此而得到刪減。整理一下,並為了簡化敘述起見,下面所述的「區塊候選數」表示:該區塊的各個宮格候選數的總和。例如(1, 3)~(3, 3) 的區塊候選數就是(1, 3)的候選數 4、6、7 及(2, 3)的候選數 3、4、6 及(3, 3)的候選數 3、7 的總和: 3、4、6、7 啦!:當某一個數字只出現在某行的某一個區塊候選數中時,就可以把該數字自包含該區塊的九宮格之其他 區塊候選數中刪減掉。 同理,當某一個數字只出現在某列的某一個區塊候選數中時,就可以把該數字自包含該區塊的九宮格之其他 區塊候選數中刪減掉。 同理,當某一個數字只出現在某個九宮格的某一個區塊候選數中時,就可以把該數字自包含該區塊的行或列之其他 區塊候選數中刪減掉。利用「找出某一行、某一列或某一個九宮格各個區塊候選數中只出現一次的數字來,並將該數字自包含該區塊的另一個 行、列或九宮格的其他區塊候選數中刪減掉」的方法就叫做區塊刪減法 (Locked Candidates, Single Sector Candidates)。區塊刪減法示例區塊刪減法一共有 4 種狀況:第一種是發生在行而去刪減九宮格、第二種是發生在列而去刪減九宮格、 第三種是發生在九宮格而去刪減行、第四種是發生在九宮格而去刪減列。<圖 1> 就是發生在行而去刪減九宮格的例子了,其他的情況舉例如下:

<圖 2><圖 2> 是發生在列而去刪減九宮格的例子:因為第 3 列的數字 6 只出現在 (3, 1)~(3, 3) 這一個區塊, 所以可以將上左九宮格的另兩個區塊 (1, 1)~(1, 3)、(2, 1)~(2, 3) 候選數中的數字 6 安全的刪減掉; 於是(1, 1)的候選數 2、6 將被刪減成 2,出現了唯一候選數啦!

<圖 3><圖 3> 是發生在九宮格而去刪減列的例子:因為上右九宮格的數字 5 只出現在 (3, 7)~(3, 9) 這一個區塊, 所以可以將第 3 列的另兩個區塊 (3, 1)~(3, 3)、(3, 4)~(3, 6) 候選數中的數字 5 安全的刪減掉; 於是(3, 3)的候選數 5、9 將被刪減成 9,出現了唯一候選數啦!

<圖 4><圖 4> 是發生在九宮格而去刪減行的例子:因為中央九宮格的數字 1 只出現在 (4, 5)~(6, 5) 這一個區塊, 所以可以將第 5 行的另兩個區塊 (1, 5)~(3, 5)、(7, 5)~(9, 5) 候選數中的數字 1 安全的刪減掉; 於是(8, 5)的候選數 1、3、7、8 將被刪減成 3、7、8;同理,中央九宮格的數字 7、8 都只出現在 (4, 5)~(6, 6) 這一個區塊,所以可以將第 5 行的另兩個區塊 (1, 5)~(3, 5)、(7, 5)~(9, 5) 候選數中 的數字 7、8 都安全的刪減掉;於是(8, 5)的候選數 3、7、8 將再度被刪減成 3;出現了唯一候選數啦!像<圖 1>~<圖 3>這樣,只做一次區塊刪減就找到下一個解的情況固然是不錯,但有時並沒有那麼順心, 像<圖 4>就需要刪減三次才得到下一個解,不過那還算好的了,因為三次的刪減都恰好發生在同一個區塊中, 請看下面發生在不同區塊的情形吧!

<圖 5><圖 5> 中的(4, 3)將可利用區塊刪減法得出下一個解,你能夠不看下面的解答,自己找出來嗎?試試!也許你已經找出答案了,恭喜!也許你還找不出答案,那也沒關係,人有失手,馬有失蹄,總有腦袋被漿糊 糊住而一時失誤的時候,請看答案吧:因為第 8 列的數字 2 只出現在 (8, 1)~(8, 3) 這一個區塊, 所以可以將下左九宮格的另兩個區塊 (7, 1)~(7, 3)、(9, 1)~(9, 3) 候選數中的數字 2 安全的刪減掉; 刪減之後的結果如<圖 6>。

<圖 6>接下來,因為第 3 行的數字 2 只出現在 (4, 3)~(6, 3) 這一個區塊,所以可以將中左九宮格的另兩個區塊 (4, 1)~(6, 1)、(4, 2)~(6, 2) 候選數中的數字 2 安全的刪減掉;刪減之後的結果如<圖 7>。

<圖 7>哈!哈!看出來了嗎?(4, 3)已出現了列隱性唯一候選數2啦!關鍵數刪減法概說遇到了高級、困難級的數獨謎題,使得唯一候選數法和隱性唯一候選數法黔驢技窮的時候,就是各種刪減法上場的時機了。在各種的刪減法中,哪一個要先用是隨個人之喜好的,並無限制。本頁介紹的例子雖然可能可以使用其他刪減法完成解題,但在大部份的情況下是無可取代的,不過本刪減法成立的條件和其他方法相比稍嫌繁雜,所以一般在使用時,均將其優先順序 放在後面,只在不得已時才用之!

<圖 1>請看<圖 1>,此時使用以往所提及的:數對刪減法、區塊刪減法、隱性數對刪減法、三鏈數刪減法、 隱性三鏈數刪減法、矩形頂點刪減法、三鏈列刪減法...等各式刪減法都已找不到下一個解了,這才是 關鍵數刪減法(Colors, Colouring)最好的上場時機。某一個數字在某一行、某一列或者某一個九宮格的各宮格候選數中恰出現兩次時,我們說在 這一行、這一列或者這一個九宮格中有了一個關鍵數。由於使用本刪減法的時機是在數獨填制的中後期, 所以擁有同一個關鍵數的行列或九宮格通常不止一處,而且環環相扣,使得候選數中包含該關鍵數的宮格 形成涇渭分明的兩大陣營;<圖 2> 和 <圖 1>是完全相同的數獨殘局,但只顯示候選數 4 的情形:

<圖 2>在 <圖 2> 中,第一列的數字 4 僅出現在 (1, 1) 及 (1, 5),是本列的關鍵數,此時,若數字 4 應填入 (1, 1),則 (1, 5) 就不能再填入數字 4;反之,若數字 4 應填入 (1, 5),則 (1, 1) 就不能再填入數字 4 了; 雖然我們還不知道哪一個宮格應填入數字 4,但卻可以利用關鍵數的這一個特性,將待填的部分宮格區分成兩組, 只要其中的一組宮格應填入數字 4 ,另一組宮格就不可能再填入數字 4 。<圖 2> 中底色為粉紅及淺藍的兩組宮格, 就具有這樣的性質。接下來,我們就可以根據這兩組宮格的分布情形,做一些確切的判定:當在底色為淺藍的宮格中填入數字 4 時,並無任何不妥! 若在底色為粉紅的宮格中填入數字 4 時,則第 7 列或第 7 行都將出現兩個數字 4,這是違反填制規則的。所以所有底色為粉紅的宮格都不可能填入數字 4,這些宮格候選數中的數字 4,全部都可以刪減掉!回到 <圖 1>,我們可發現,進行刪減之後,下一個解的尋找根本就不成任何問題了。大部分情況下,利用行列及九宮格的關鍵數將相關宮格區分為兩組後,並不一定可找出上述的矛盾狀況, 而確切的據以判定某一組宮格可進行候選數的刪減,例如<圖 3>就是一個例子:由第 9 列的關鍵數 6 所引發區分的兩組宮格,不論將數字 6 填到粉紅或淺藍為底色的宮格中,都是不會產生矛盾的。

<圖 3>不過<圖 3>卻展示了關鍵數刪減法的另一種刪減狀況;請看第 1 列中的 (1, 5) 及 (1, 8),它們有什麼 特殊之處呢?尤怪居然要用淺綠的底色來標示!哈!哈!相信你已看出來了,在這兩個宮格的同一行上,都有兩個不同底色的宮格存在,這代表:不論最後 數字 6 應填到哪一組底色的宮格中,因為本行的數字 6 已被填入了,所以這兩個宮格都不可能再填入數字 6 了,因此這兩個宮格的候選數 6 都可被安全的刪減掉!為了更清楚的說明這類的刪減,假設有某個數獨殘局的數候選數 1 分布如<圖 4> :

<圖 4>利用<圖 4>第 1 列中的關鍵數 1,可將部分宮格區分為兩組獨立的宮格,分別以粉紅及淺藍為底色來標示; 只要其中的一組宮格被填入數字 1,另一組宮格就不可能再填入數字 1。雖然在本圖中的任一組宮格中填入 數字 1 都不會產生矛盾,但是仍可以利用這些宮格的分布,對其他宮格進行刪減。先看 (3, 7)、(3, 8)、(3, 9),因為上右九宮格中己擁有粉紅及淺藍為底色的宮格各一個,表示不論 數字 1 應填到哪一組底色的宮格中,因為本九宮格中的數字 1 已被填入了,所以其他宮格都不能再 使用數字 1 了,因此這三個宮格的候選數 1 都可被安全的刪減掉! 再看 (4, 9),因為同行的(2, 9)有一個粉紅底色的宮格,同列的(4, 4)又有一個淺藍底色的宮格,所以 不論數字 1 應填到哪一組底色的宮格中,因為同一個行、列中的數字 1 已被填入了,所以本宮格就不能 再使用數字 1 了;這個宮格的候選數 1 可安全的刪減掉! 最後來看看 (4, 1)、(5, 1),因為同行中己擁有粉紅及淺藍為底色的宮格各一個,所以這兩個宮格的 候選數 1 都可安全的刪減掉!利用「以關鍵數的關係找出矛盾的組合,或者找出確切可進行刪減的宮格,進而將該數字自宮格候選數中刪減掉」 的方法就叫做關鍵數刪減法(Colors, Colouring)。由於在說明本法的分組狀況時, 以顏色來區分是最清楚明了的,所以外國人就以 「colors 顏色」為名,也是十分傳神的。矩形頂點刪減法概說遇到了高級、困難級的數獨謎題,使得唯一候選數法和 隱性唯一候選數法黔驢技窮的時候,就是各種刪減法上場的時機了。在各種的刪減法中,哪一個要先用 是隨個人之喜好的,並無限制。本頁介紹的例子當然可用其他刪減法完成解題,且本刪減法成立的條件 和其他方法相比稍嫌繁雜,但為了介紹,在進行解題時還是要以矩形頂點刪減法優先??!

<圖 1>請看<圖 1>的第 1 列及第 9 列,數字 8 都只出現在第 5、8 行的宮格候選數中;這時 矩形頂點刪減法的條件已成立了!這表示第 5 行及第 8 行的數字 8 將只能被填到第 1 列及 第 9 列了,因為:第 1 列的數字 8 只出現在(1, 5)及(1, 8),所以數字 8 只能填到這兩個宮格; 同樣的,第 9 列的數字 8 只出現在(9, 5)及(9, 8),所以數字 8 也只能填到這兩個宮格; 先假設第 1 列的數字 8 將被填到(1, 5),第 5 行就不能再填數字 8 了,所以第 9 列的數字 8 只好 填到(9, 8);另外,假設第 1 列的數字 8 將被填到(1, 8),第 8 行就不能再填數字 8 了,所以第 9 列的數字 8 只好填到(9, 5);不論哪一種情況發生,第 5 行及第 8 行的數字 8 都已被填入,別的 宮格已不能再使用數字 8 來填入了,所以若其他宮格的候選數中還有數字 8,全部是多餘無用的, 可以毫不考慮的把它們刪減掉。於是(3, 5)、(6, 5)和(3, 8)、(7, 8)這四個宮格候選數中的 8 都可被安全的刪減掉;其中(6, 5)的候選數少了數字 8,將使得(6, 6)出現列隱性唯一候選數 8 ,於是 可用隱性唯一候選數法來填入下一個解了。整理一下:當某個數字在某兩列僅出現在相同的兩行時,就可以把這兩行其他宮格候選數中的該數字刪減掉。 同理,當某個數字在某兩行僅出現在相同的兩列時,就可以把這兩列其他宮格候選數中的該數字刪減掉。利用「找出某個數字在某兩列僅出現在相同兩行的情形,進而將該數字自這兩行其他宮格候選數中刪減掉」; 或「找出某個數字在某兩行僅出現在相同兩列的情形,進而將該數字自這兩列其他宮格候選數中刪減掉」的方法 就叫做矩形頂點刪減法(X-Wing)。因為本刪減法的條件成立時,關鍵的數字 8 所處的宮格在數獨方陣上看來,剛好就在一個矩形的頂點。遇到了高級、困難級的數獨謎題,使得唯一候選數法和 隱性唯一候選數法黔驢技窮的時候,雖然你可以優先使用矩形頂點刪減法來尋找下一個解;但大部分的人在 使用刪減法的優先順序上,通常都會將矩形頂點刪減法排在稍後一點,為什麼要如此安排,在實際使用一段時間之後, 相信你自能體會了,但這個方法又是不可或缺的,如果不會運用本刪減法,有很多高級的數獨謎題就將無解了。矩形頂點刪減法示例矩形頂點刪減法只有 2 種狀況:第一種的刪減發生在行、第二種的刪減發生在列。<圖 1> 就是 刪減發生在行的例子了,第二種的情況舉例如下:

<圖 2><圖 2> 是矩形頂點刪減發生在列的例子:圖中第 2 行、第 8 行的數字 3 只出現在第 1 列及第 2 列, 所以可以將數字 3 自(1, 3)、(1, 5)及(2, 1)、(2, 4)、(2, 5)的候選數中安全的刪減掉,其中(2, 4) 的候選數由 2、3、4、6 刪減成 2、4、6 時;(3, 4)將出現隱性唯一候選數 3 啦!

<圖 3><圖 3> 也是一個刪減法綜合運用的例子。在(1, 8)中將可找到下一個解,你能找出來嗎?因為上中九宮格的數字 1 只發生在(2, 4)~(2, 6) 這一個區塊,所以可以利用區塊刪減法 把(2, 7)~(2, 9)候選數中的數字 1 安全的刪減掉。 因為第 1 行及第 7 行的數字 1 只出現在第 4 列及第 9 列,所以可以利用矩形頂點刪減法 把(4, 3)及(9, 6)、(9, 8)、(9, 9)候選數中的數字 1 安全的刪減掉。經過以上刪減之後,(1, 8)出現行隱性唯一候選數 1 啦!

轉發至微博
推薦閱讀:

第10講:規則Wing結構
第20講:雙強鏈(多寶魚)
第51講:形狀變異魚(3)——自噬鰭的引入
第30講:ALS的綜合運用
第34講:超標準環

TAG:數獨 |