Peg Solitaire

野辺山の電波天文台近くの食堂に入ったら、 土産品として売っているパズルの１つ 「Peg Solitaire」がテーブルに置かれていました。 子供の頃見ただけだなあと思って、 やってみると案外難しい。できないうちに食事が出てきてしまいました。

どんなパズルかわからない方は、 Erik Gos (Erik.Gos@hiva.kuleuven.ac.be) さんが 1998 年 7 月にお書になった 「Java Script Solitaire! Version 1.2」 から Peg Solitaire 本来の部分を抜き出しておきましたので、 遊んでみてください。 「開始」をクリックすると初期配置になりますので、 移動したいペグをクリックします。飛び先が複数あるときは、 続けて飛び先もクリックします。 「解く」をクリックすると、 Ernest Bergholt による 18 手の手順を実行します。 John Beasley が 1964 年に 18 手未満の解が存在しないことを証明しました。

どのペグも上下左右に隣接する他の１つのペグを飛び越して、 その先に隣接する空き地に移動し、 同時に飛び越したペグを盤から取り除くことができます。 この飛び越し除去操作を繰り返し実行し、 最後に１つのペグを残せば成功です。

驚くべきことに、この最後の１つは、 中心か、 最後の１手で中心に行けたはずの周辺中央の４箇所しかないことが 証明できますので、最後の１手は中心を選ぶことにすれば、 開始時点の盤のペグと穴を反転した相補的な状態が最終局面になるという 美しいパズルになります。

簡単に解けないとなるとコンピュータに解かせてみたくなりますが、 帰宅後とりあえず作ってみたのが ジャンプテーブルとバックトラックを使ったプログラムです。 解の対称性を完全に除去する、うまい方法を思い付けず、 最初の２手だけプログラムで制限しましたが、 これでは対称の解がまだたくさん残ります。

そして、動かしてみて驚いたのが、 解と飛び越し操作の組み合わせの多さ。 はじめてこのパズルに接した人間に比べれば、 短時間で多量の解を見出しはしますが、 ちょっとやそっとでは終わりません。 解の総数をご存じのかたがいらっしゃれば、 お教えいただきたいです。

とりあえず、多量の解の一部を見付けるには、 こうした力づくのプログラムでなんとかなるにしても、 人間がやるにはもっと考え易い手法が必要で、 少し調べてみると、 古いパズルだけにすぐれた手法が開発されているのが わかりました。(注１)

注１ - 最も包括的なのは、

John D.Beasley,- THE INS AND OUTS OF PEG SOLITAIRE
	(Oxford University Press) 1992, ISBN 0-19-286145-X