テストパターン生成

下の回路図で，信号線ｆの論理値が常に１となるような故障が起こったとする．
このとき，どのような入力値（テストパターン）を印加することで，このような故障を検出できるでしょうか．



（答え）信号線ａに０，信号線ｂ，ｃに１を印加すればよい．もし故障がなければ出力線ｈは０となるが，故障があった場合には１となる．

このような問題を解く場合，２分決定木（下の図参照）というものが用いられる．
例えば，まずｂ＝０とする．すると，外部出力線が，故障の有無にかかわらず１となるため，テストパターンとしては適さない．そこでｂ＝０を取り消して，ｂ＝１とする．このように直前の決定を取り消して，処理を進めることをバックトラックという．
バックトラックの発生する典型的な問題として８クイーン問題がある．