フォーシング
フォーシング
関連テクニック
それは推測なのか?強制チェーン論争
強制チェーンは証明テクニックとして使われる場合、推測ではない。選んだ出発点からすべての分岐を一時的に調べ、各分岐を論理的に伝播させ、すべての分岐が支持する結論、または矛盾によって強制される結論だけを残す。推測との決定的な違いはコミットメントである。推測は一つの分岐を選び、それが真であるかのように続ける。フォーシングチェーンは出発点から関連するすべての分岐を比較し、その比較が何かを証明したときにのみ行動する。強制チェーンはパターンベースのテクニックより美しくはないが、すべての分岐が正確に確認されていれば、その結論は証明可能なほど正しい。
セルフォーシングチェーン
二値候補のセル{A,B}から始める。各分岐の含意を伝播させる。結果を比較する。矛盾:一方の分岐が無効なので、セルはもう一方の候補でなければならない。配置への収束:両方の分岐が同じ数字を同じ遠くのセルに強制する。消去への収束:両方の分岐が同じセルから同じ候補を消去する。
領域フォーシングチェーン(数字フォーシングチェーン)
あるハウス内の数字の2〜3の位置から始める。各位置を分岐として調べる。推論タイプは同じ三つ。セルフォーシングは、二値候補セルが遠くまで影響を及ぼす場合に効果的である。領域フォーシングは、ある数字の位置が強い連鎖効果を持つ場合に効果的である。
フォーシングネット:分岐数の拡張
セルフォーシングネット:候補が3〜6個のセル。領域フォーシングネット:ある数字に対して4〜6の位置を持つハウス。分岐が増え、コストは高くなるが、強制チェーンでは見つけられない推論を見つけられる。論理は同一である。異なるのは分岐数だけである。
伝播エンジン
各分岐はネイキッドシングル、ヒドゥンシングル、ロックされた候補、ネイキッドペアを通じて、安定するまで反復的に伝播する。一つの仮定が盤面全体にわたる数十の中間ステップに波及することがある。二つの分岐がまったく異なる経路で同じ結論に達したとき、その収束は結論を確実に証明する。
三つの推論タイプ
矛盾:ある分岐が不正な状態を生み出す。その仮定は誤りである。最も一般的。配置への収束:すべての分岐が同じ数字を同じセルに強制する。頻度は低いが決定的。候補排除への収束:すべての分岐が同じセルから同じ候補を排除する。最も繊細なタイプ。
フォーシング技法を使う場面
最後の論理的手段。パターンベースの技法やより簡潔なチェーンが失敗した後に適用する。まず2~3分岐の強制チェーンを試す。3~6分岐のフォーシングネットはより高コストで、通常は後回しにされる。どちらもレベル12(極限)。コンピュータソルバーにとって、有界フォーシングは強力な証明エンジンだが、自動的に完全とはならない。完全性は、必要な仮定を網羅するのに十分なほど探索を広げた場合にのみ得られ、それは網羅的なバックトラッキングに近づく。実際には、フォーシングは固定深さのソルバーがすべての有効なパズルを解ける保証というより、制御された論理探索と表現するのが最適である。
エレガンスと完全性に関する哲学的覚書
パターンベースの技法は構造的関係を明らかにし、よりエレガントである。しかし、フォーシングレベルの論理を必要とする有効なパズルも存在する。フォーシング技法は、パターンベースの技法では扱えないあらゆるパズルを捕らえる安全網である。最も満足のいくアプローチ:まずすべてのパターンベースの技法を試し、パズルが本当に要求するときにのみフォーシングに頼る。
まとめ
強制チェーンとフォーシングネットは最も強力な論理技法の一つで、レベル12(極限)に位置する。選んだ開始点からすべての分岐を探索し、結果を伝播させ、比較する。推論は矛盾、配置への収束、候補排除への収束によって得られる。これらは総当たりバックトラッキングの前の最後の手段であり、実用的な制限なしに拡張すれば完全な探索証明となるが、有界な人間流のフォーシングは的を絞った高度な技法にとどまる。
関連テクニック