強制
強制
這是猜測嗎?強制鏈的爭議
當強制鏈被用作證明技巧時,它們並不是猜測。你暫時檢查從選定起點出發的每一個分支,對每個分支進行邏輯傳播,只保留所有分支都支持的結論,或由矛盾所強制的結論。與猜測的關鍵區別在於承諾。猜測會選擇一個分支並當作它是真的繼續下去。強制鏈則比較從起點出發的所有相關分支,只有當比較證明了某些東西時才採取行動。強制鏈不如基於模式的技巧優雅,但當每個分支都被準確檢查時,它們的結論是可證明正確的。
單元格強制鏈
從一個雙值單元格{A,B}開始。為每個分支傳播蘊含關係。比較結果。矛盾:一個分支無效,因此單元格必須是另一個候選數。收斂於填數:兩個分支都強制同一個數字進入同一個遠處的單元格。收斂於刪減:兩個分支都從同一個單元格中刪減同一個候選數。
區域強制鏈(數字強制鏈)
從一個數字在一個宮中的2-3個位置開始。將每個位置作為一個分支進行探索。同樣是三種推理類型。當雙值格具有影響深遠的蘊含關係時,單元格強制很有效。當一個數字的位置具有強大的級聯效應時,區域強制很有效。
強制網:擴展分支數量
單元格強制網:具有3-6個候選數的格。區域強制網:一個數字在一個宮中有4-6個位置。分支更多,代價更高,但能找到強制鏈無法找到的刪減。邏輯完全相同。只是分支數量不同。
傳播引擎
每個分支透過唯一候選數、隱性唯一候選數、鎖定候選和顯性數對進行傳播,迭代直到穩定。一個假設可以在整個棋盤上引發數十個中間步驟的連鎖反應。當兩個分支透過完全不同的路徑得出相同結論時,這種收斂就以確定性證明了該結論。
三種推理類型
矛盾:某個分支產生了無效狀態。該假設為假。最常見。位置收斂:所有分支都將同一個數字強制填入同一個單元格。較少見但具有決定性。排除收斂:所有分支都從同一個單元格中排除同一個候選數。最微妙的一種。
何時使用強制技巧
最後的邏輯手段。在基於模式的技巧和更簡潔的鏈都失敗後使用。先嘗試有2-3個分支的強制鏈。有3-6個分支的強制網代價更高,通常留到後面使用。兩者都是第12級(極限)。對於電腦求解器而言,有界強制是一種強大的證明引擎,但並不自動完備。只有當搜尋被允許擴展到足以涵蓋所需假設時,完備性才會出現,而這已接近窮舉回溯。在實踐中,強制最好被描述為一種受控的邏輯搜尋,而不是保證任何固定深度的求解器都能解出每一個有效謎題。
關於優雅與完備性的哲學思考
基於模式的技巧揭示結構關係,更為優雅。但存在一些有效謎題需要強制級別的邏輯。強制技巧是安全網,能接住所有基於模式的技巧無法處理的謎題。最令人滿意的做法:先嘗試所有基於模式的技巧,只有當謎題確實需要時才訴諸強制。
總結
強制鏈和強制網是最強大的邏輯技巧之一,屬於第12級(極限)。它們從選定的起點探索每一個分支,傳播後果並比較結果。推理透過矛盾、位置收斂或排除收斂得出。它們是在暴力回溯之前的最後手段;如果不受實際限制地擴展,它們會成為完備的搜尋證明,但有界的人類風格強制仍是一種有針對性的高級技巧。