強制
強制
当てずっぽうですか?強制チェーンに関する論争
強制チェーン は証明技法として使用される際、推測ではありません。あなたは選択した出発点からすべての分岐を一時的に検討し、各分岐を論理的に展開し、すべての分岐が支持する結論、または矛盾によって強制される結論のみを保持します。
推測との主な違いは、コミットメントです。推測は1つの分岐を選び、それが真であるかのように続けます。強制チェーンは、出発点からのすべての関連する分岐を比較し、比較によって何らかのことが証明されたときにのみ行動します。
強制チェーン はパターンベースの技法よりもエレガントではありませんが、すべての分岐が正確に確認された場合、その結論は証明可能に正しいです。
セル 強制チェーン
二値のセル {A, B}から開始する。各分岐の影響を伝搬させる。結果を比較する。
矛盾:一方の分岐が無効であるため、セルは他の候補でなければならない。
配置への収束:両方の分岐が、同じ遠方のセルに同じ数字を強制する。
削除への収束:両方の分岐が、同じセルから同じ候補を削除する。
領域強制チェーン(数字強制チェーン)
ハウス内の数字の2〜3つの位置から開始する。各位置を分岐として検証する。同じ3種類の推論手法を使用する。
セル フォースは、2値セルが広範な影響を持つ場合に有効である。リージョンフォースは、数字の位置が強い連鎖反応を引き起こす場合に有効である。
強制ネット:分岐数の拡張
セル 強制ネット:3〜6候補を持つマス。領域強制ネット:数字の配置が4〜6通りある領域。より多くの分岐があるため、コストが高くなるが、強制チェーンが見つかる可能性がある。
論理は同一。分岐数のみが異なる。
プロパゲーションエンジン
各ブランチは、ナードシングル、ヘイドンシングル、ロックされた候補、ナードペアを通じて伝播し、安定するまで反復的に処理されます。1つの仮定が、ボード全体にわたって数十の中間ステップにわたって波及する場合があります。
2つのブランチが完全に異なる経路をたどって同じ結論に達した場合、収束によりその結論の確実性が証明されます。
3つの推論タイプ
矛盾:分岐により無効な状態が生じます。その仮定は誤りです。最も一般的です。
配置への収束:すべての分岐が同じセルに同じ数字を強制します。あまり一般的ではありませんが、決定的です。
候補の削除への収束:すべての分岐が同じセルから同じ候補を削除します。最も微妙なタイプです。
強制技術を使用するタイミング
最後の論理的手段。パターンベースの技法とクリーナーなチェーンが失敗した後に適用される。
2〜3分岐の強制チェーンが最初に試行される。3〜6分岐の強制ネットはよりコストが高く、通常は後で使用される。両方ともレベル12(極度)である。
コンピュータソルバーにおいて、制限付き強制は強力な証明エンジンだが、自動的に完全ではない。完全性は、検索が必要な仮定を十分にカバーできるように拡張された場合にのみ得られる。これは、網羅的なバックトラッキングに近づく。実際には、強制は固定深さソルバーがすべての有効なパズルを解けるという保証ではなく、制御された論理的探索と説明されるのが最適である。
洗練と完全性に関する哲学的考察
パターンベースのテクニックは構造的な関係を明らかにし、より洗練されたものです。しかし、強制レベルの論理を必要とする正当なパズルも存在します。強制テクニックは、パターンベースのテクニックでは対処できないすべてのパズルをカバーする安全網です。
最も満足のいくアプローチ:まずすべてのパターンベースのテクニックを試み、パズルが本当にその必要を示した場合にのみ、強制的手法に頼る。
要約
強制チェーンと強制ネットは、レベル12(極限)で最も強力な論理的手法の一つです。これらは選択した出発点からすべての分岐を調査し、結果を伝播させ、その結果を比較します。推論は矛盾、配置への収束、または除外への収束によって得られます。ブルートフォースによるバックトラッキングを最後の手段とする前に、これらは使用されます。実用的な制限なしに展開された場合、完全な探索証明になりますが、制限付きの人間的な強制手法はターゲットされた上級技術のままです。