Peg Solitaire - 続き (2)

人間の頭脳に適した解法

複雑で手強い問題を人間が扱う場合は、「分割統治」による各個撃破を考えるのが戦略の１つで、これができると楽になりますが、 John D. Beasley の本とか、最近では、

  Elwyn R.Berlekamp, John H.Conway, Richard K.Guy,-
	Winning Ways For Your Mathematical Plays
	Volume 4 SECOND EDITION
	(A K Peters, Ltd.) ISBN 1-56881-144-6

にこの手法が見られます。 ( http://www.cut-the-knot.org/proofs/pegsolitaire.shtml に同じものがあります)

まず、

複数のペグから構成される区画で、
隣接ないし内蔵する
1. １つの空き地と、
2. 他のペグの除去に使われるだけで自分は同じ場所に残存する「触媒」として機能する１つのペグを使って、
区画内のすべてのペグを除去できるような配置(purge)

を考えます。

いろいろなパターンがありますが、最も実用的なのが下記の３つで、それぞれ「3-purge」「6-purge」「 L-purge」と呼ばれます。(注１) x は除去されるペグ、 c と d のうちいずれか１つが触媒ペグで、残りは触媒が働くための空き地ですが、触媒ペグは x を 2 つ除去して元に戻りますので、 x の除去によって他の領域の配置を乱すことがなく、この性格が「分割統治」の手段として使えます。「.」は空き地です。

                             x
     x        c . d        c x d
     x          x x x        x
   c x d        x x x        x x x

  3-purge     6-purge      L-purge

次に、この３つのパターンで、 Peg Solitaire の初期配置をうまく分割できれば、分割統治が可能になるわけですが、例えば、次のような分割ができます。パターン 1, 2, 3, 4, 5, 6 がパターンの適用順、 1, 2 が 3-purge、3, 4, 5 が 6-purge、6 が L-purge のパターンで、 * が分割統治で除去した後、最後に残るペグです。

      4 4 4
      4 4 4
  5 5 2 2 2 3 3
  5 5 6 . 1 3 3
  5 5 6 * 1 3 3
      6 * 1
      6 6 6

触媒ペグを使った除去パターンには下記のようなものもあって、分割方法も、いろいろあります。

     x          c
     c          d
     d          x x x
     x          x x x

  2-purge      6-purge

注１ - 前記の文献には、18 手未満の手順が存在しないという John Beasley の証明を含む、 Peg Solitaire に関するいろいろな情報があります。なお、Beasley の本では「L-purge」を「L-move」)と呼び、この種の解法を「Block Play」と呼んでいます。