關鍵數刪減法

(Colors)

概說
  • 遇到了高級、困難級的數獨謎題,使得唯一候選數法 隱性唯一候選數法黔驢技窮的時候,就是各種刪減法上場的時機了。在各種的刪減法中,哪一個要先用 是隨個人之喜好的,並無限制。本頁介紹的例子雖然可能可以使用其他刪減法完成解題,但在大部份的情況 下是無可取代的,不過本刪減法成立的條件和其他方法相比稍嫌繁雜,所以一般在使用時,均將其優先順序 放在後面,只在不得已時才用之!
    <圖 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 。分色的過程如下:
    1. 先假設 (1, 1)應填入 4。( 為方便記錄,記成 (1, 1)= 真; 反之,假設 (1, 1)不能入 4,則記成 (1, 1)= 假。)
    2. 利用前述關鏈數的特性,(1, 1)= 真 ==> (1, 5)= 假、(2, 2)= 假、(7, 1)= 假。
    3. (2, 2)= 假 ==> (2, 4)= 真、(8, 2)= 真。
    4. (2, 4)= 真 ==> (7, 4)= 假。
    5. (1, 5)= 假 ==> (9, 5)= 真。
    6. (8, 2)= 真 ==> (8, 7)= 假。
    7. (9, 5)= 真 ==> (9, 7)= 假。
    8. (9, 7)、(8, 7)= 假 ==> (7, 7)= 真。
    假設把具有真值的宮格填入淺藍色,把具有假值的宮格填入粉紅色,一面判斷宮格的真、假值,一面填入顏色, 當判斷完成時就成了<圖 2> 的樣子了。
  • 接下來,我們就可以根據這兩組宮格的分佈情形,做一些確切的判定:
    1. 當在底色為淺藍的宮格中填入數字 4 時,並無任何不妥!
    2. 若在底色為粉紅的宮格中填入數字 4 時,則第 7 列或第 7 行都將出現兩個數字 4,這是違反填製規則的。
    所以所有底色為粉紅的宮格都不可能填入數字 4,這些宮格候選數中的數字 4,全部都可以刪減掉!回到 <圖 1>,我們可發現,進行刪減之後,下一個解的尋找根本就不成任何問題了。

  • 上述的矛盾判斷是藉助已完成的圖面來進行的,有時容易造成讀者的不易了解;如果您有這個困擾, 那大可以重新來過:既然(1, 1)= 真 不會造成矛盾,那麼就設成 (1, 1)= 假吧!
    1. (1, 1)= 假 ==> (1, 5)= 真、(2, 2)= 真、(7, 1)=真。
    2. (2, 2)= 真 ==> (2, 4)= 假、(8, 2)= 假。
    3. (2, 4)= 假 ==> (7, 4)= 真。產生矛盾了,第 7 列出現了兩個 4。
    (1, 1)= 假 會產生錯誤,意即(1, 1)= 真 才是對的,所以由關鏈數的特性,可以把 <圖 2>中粉紅宮格的 候選數 4 全部安全的刪減掉。
  • 大部分情況下,利用行列及九宮格的關鍵數將相關宮格區分為兩組後,並不一定可找出上述的矛盾狀況, 而確切的據以判定某一組宮格可進行候選數的刪減,例如<圖 3>就是一個例子:由第 9 列的關鍵數 6 所引發區分的兩組宮格,不論將數字 6 填到粉紅或淺藍為底色的宮格中,都是不會產生矛盾的。
    <圖 3>
  • 不過<圖 3>卻展示了關鍵數刪減法的另一種刪減狀況;請看第 1 列中的 (1, 5) 及 (1, 8),它們有什麼 特殊之處呢?尤怪居然要用淺綠的底色來標示!
  • 哈!哈!相信你已看出來了,在這兩個宮格的同一行上,都有兩個不同底色的宮格存在,這代表:不論最後 數字 6 應填到哪一組底色的宮格中,因為本行的數字 6 已被填入了,所以這兩個宮格都不可能再填入數字 6 了,因此這兩個宮格的候選數 6 都可被安全的刪減掉!
  • 為了更清楚的說明這類的刪減,假設有某個數獨殘局的數候選數 1 分布如<圖 4> :
    <圖 4>
  • 利用<圖 4>第 1 列中的關鍵數 1,可將部分宮格區分為兩組獨立的宮格,分別以粉紅及淺藍為底色來標示; 只要其中的一組宮格被填入數字 1,另一組宮格就不可能再填入數字 1。雖然在本圖中的任一組宮格中填入 數字 1 都不會產生矛盾,但是仍可以利用這些宮格的分布,對其他宮格進行刪減。
    1. 先看 (3, 7)、(3, 8)、(3, 9),因為上右九宮格中己擁有粉紅及淺藍為底色的宮格各一個,表示不論 數字 1 應填到哪一組底色的宮格中,因為本九宮格中的數字 1 已被填入了,所以其他宮格都不能再 使用數字 1 了,因此這三個宮格的候選數 1 都可被安全的刪減掉!
    2. 再看 (4, 9),因為同行的(2, 9)有一個粉紅底色的宮格,同列的(4, 4)又有一個淺藍底色的宮格,所以 不論數字 1 應填到哪一組底色的宮格中,因為同一個行、列中的數字 1 已被填入了,所以本宮格就不能 再使用數字 1 了;這個宮格的候選數 1 可安全的刪減掉!
    3. 最後來看看 (4, 1)、(5, 1),因為同行中己擁有粉紅及淺藍為底色的宮格各一個,所以這兩個宮格的 候選數 1 都可安全的刪減掉!
  • 利用「以關鍵數的關係找出矛盾的組合,或者找出確切可進行刪減的宮格,進而將該數字自宮格候選數中刪減掉」 的方法就叫做關鍵數刪減法(Colors, Colouring)。由於在說明本法的分組狀況時, 以顏色來區分是最清楚明瞭的,所以外國人就以 「colors 顏色」為名,也是十分傳神的。
 
 
 
本網頁建置日期:94.09.21 | 最近更新日期:97.12.12  | 回上頁 | 回首頁 |