理学部情報科学科

メニュー

パズル、ゲーム、アルゴリズム(2/3)

(3) ペグソリティア

かなり古いパズル(ゲーム)にペグソリティアというものがあります。ソリティアとは一人遊びという意味です。これは
(3) ペグソリティア01
のような特殊な盤でプレイします。穴にピン(ペグ)を差し込めるようになっていて、左右前後の隣の穴に差されているペグを飛び越えて、次の穴にペグを移動することができます。そのとき、飛び越されたペグは取り除かれます。
(3) ペグソリティア02
○はピンの差し込まれていない穴を表し、●はピンが差し込まれた状態を表しています。

 初期の配置から、このような移動を繰り返し、最終的にペグ一本が残すこができると成功です。最後のペグが中心の位置に残るのが望ましいとされます。上の盤が標準的ですが、これと異なる方法でプレイすることも可能です。より一般的に、平面状の格子点(座標で表したとき、xy座標が共に整数である点)にすべて穴が開いていて、その穴の有限個にペグを差した初期状態からプレイし、最後に1本のペグが残すことを考えます?例えば、
(3) ペグソリティア03
の配置からは、明らかに1本残すことは不可能ですが、
(3) ペグソリティア04
は可能です。実際、
(3) ペグソリティア05
 と移動させればよい。

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

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

お問い合わせ先

東邦大学 理学部

〒274-8510
千葉県船橋市三山2-2-1
習志野学事部

【入試広報課】
TEL:047-472-0666

【学事課(教務)】
TEL:047-472-7208

【キャリアセンター(就職)】
TEL:047-472-1823

【学部長室】
TEL:047-472-7110