かなり古いパズル（ゲーム）にペグソリティアというものがあります。ソリティアとは一人遊びという意味です。これは

のような特殊な盤でプレイします。穴にピン（ペグ）を差し込めるようになっていて、左右前後の隣の穴に差されているペグを飛び越えて、次の穴にペグを移動することができます。そのとき、飛び越されたペグは取り除かれます。

○はピンの差し込まれていない穴を表し、●はピンが差し込まれた状態を表しています。

　初期の配置から、このような移動を繰り返し、最終的にペグ一本が残すこができると成功です。最後のペグが中心の位置に残るのが望ましいとされます。上の盤が標準的ですが、これと異なる方法でプレイすることも可能です。より一般的に、平面状の格子点（座標で表したとき、ｘｙ座標が共に整数である点）にすべて穴が開いていて、その穴の有限個にペグを差した初期状態からプレイし、最後に１本のペグが残すことを考えます？例えば、

の配置からは、明らかに１本残すことは不可能ですが、

は可能です。実際、

　と移動させればよい。

　さて一般に、どのような最初の配置からだと、１本だけ残す手順が存在するだろうか？このような問題設定にすると、パズルというより、数学の問題といってもいいですね。

　与えられた配置から一本のペグを残す手順を、コンピュータにさせようとして、単純に考えられるのは、全探索です。ある配置から移動できるすべての可能性をチェックし、行きづまったら元に戻ってやりなおす、という方法です。しかし、このようなやり方では手数がかかりすぎて、どんな高速のコンピュータをもってしても実行不可能になってしまうことが多いのです。ある条件を満たすパターン（組み合わせ）の数はとてつもない数になることが多く、これを組み合わせ的爆発といいます。このような問題をコンピュータで解くためには、やはり「良い」アルゴリズムの工夫が必要なのです。