ペグソリティアの答えは、コンピューターで探せます。アプリ「ペグソリティア」の「ひらめき」も、この記事のサイトで答えを確かめるときも、同じ考え方のプログラムを使っています。ここでは、そのしくみをやさしく紹介します。

すべての手を順に試す

いちばん素直な方法は、打てる手を1つ選んで打ち、また打てる手を1つ選んで打つ、をくり返すことです。行き詰まったら1手戻して、まだ試していない別の手を選びます。

  1. 今の盤面で打てる手を、1つ選んで打つ。
  2. 玉が1つになったら、答えが見つかった。
  3. 打てる手がなくなったら、1手戻して、別の手を試す。
  4. どの手も試し終わったら、さらに1手戻す。

この方法を深さ優先探索と呼びます。人が「ひとつ戻る」を使って試すのと同じことを、ものすごい速さでくり返します。

同じ盤面を何度も調べない

ペグソリティアでは、ちがう順番で打っても、同じ盤面になることがよくあります。英国式33穴では、7手目の後の打ち方は22万通りを超えますが、できあがる盤面は2万2千種類ほどです(解き方は何通り?)。

そこで、一度調べて行き詰まると分かった盤面を覚えておき、また出会ったら、すぐに引き返します。これだけで、調べる量が大きく減ります。

この記事のサイトで使ったプログラムでは、英国式33穴を真ん中から始めて真ん中に残す答えが、一瞬(0.1秒もかからず)で見つかりました。ただし、いつも速いわけではありません。2手目を変えた盤から同じように探すと、9秒ほどかかりました。どの手から試すかで、かかる時間は大きく変わります。

先を読まずに打ち切る

もうひとつの工夫は、この盤面からは、どう打っても目標に届かないと分かったら、その先を調べずに打ち切ることです。これを「枝切り」と呼びます。

アプリでは、次の2つで枝を切っています。

  • 3色の塗り分け: 盤を斜めに3色で塗ると、1手ごとに3色すべての玉の数の偶数・奇数が入れかわります。そのため、今の盤面から最後の1つを残せる穴は、計算だけで分かります(3色の塗り分けの記事)。
  • 親玉の行と列: 親玉は1回に2つずつ動くので、いる穴の行と列の偶数・奇数が変わりません(親玉を最後に残すコツ)。

2つの条件を両方満たす穴が盤に1つもなくなったら、親玉を最後に残せる穴はありません。その盤面は、先を読むまでもなく「解けない」と分かります。

アプリの「ひらめき」では

アプリの「ひらめき」は、今の盤面から目標に届く次の一手を探して、金の輪で光らせます。

  • 問題の答えを先に覚える: 「問題」の盤は、逆向きに跳んで作るので、作ったときの答えが分かっています(必ず解ける問題の作り方)。その答えの道の上の盤面は「解ける」と覚えておくので、すぐに答えられます。道からそれた盤面でも、探しているうちに答えの道に合流すれば、そこで止められます。
  • 調べる量に上限を付ける: 1回のひらめきで調べるのは、150万盤面か3秒までです。大きな盤では、それまでに答えが出ないこともあります。
  • 戻る手数を教える: 今の盤面からもう目標に届かないときや、上限までに分からないときは、「ひとつ戻る」で戻れる盤面を調べ、「3手戻すと残せます」のように、何手戻せばよいかを教えます。戻れる盤面を、半分ずつにしぼりながら調べるので、手数が多くても速く見つかります。

人が解くときのヒント

コンピューターの工夫は、人が解くときにも使えます。

  • 行き詰まった形を覚える: 一度失敗した形は、別の順番でたどり着いても、やはり失敗します。
  • ゴールから考える: 最後に残せる穴は、始めから決まっています。目指す穴を先に決めると、手を選びやすくなります(真ん中へ残すには)。
  • 戻して試す: 深さ優先探索のように、迷ったら少し戻して別の手を試すのは、正しいやり方です。