制約伝播

せいやくでんぱ

数字の確定により生じる制約を関連マスに波及させ、候補を自動的に絞り込むアルゴリズム的手法。

制約伝播 (Constraint Propagation) は、ある数字が確定した際に、その影響を受ける行 / 列 / ブロックの候補を即座に更新する手法である。人間が行うメモの更新と本質的に同じだが、コンピューターでは影響を自動で伝播できる。

ソルバーでの役割

制約伝播はバックトラッキングの効率を改善する。数字を仮置きするたびに制約を伝播させ、候補が 0 になるマスが発生すれば即座にバックトラックする (早期枝刈り)。候補が 1 つになるマスは自動確定させる。

人間の解法との対応

人間が行うネイキッドシングルの発見とメモの更新は、制約伝播の手動版と言える。

このページは役に立ちましたか?