アプリ「ソートパズル」は、問題を出す前に、コンピューターで解けることを確かめています。「ひらめき」の次の一手も、同じ解法が見つけた手順の1手目です。ここでは、その解法のしくみを紹介します。

局面と手をたどる

ソートパズルの盤の状態(どの器に何色が入っているか)を局面と呼びます。1手移すと、別の局面になります。最初の局面から手をたどっていき、そろった局面に着けば、たどった道が答えです。

いちばん素直な探し方は、1手で行ける局面を全部、次に2手で行ける局面を全部……と広げていく幅優先探索です。必ず最少手数の答えが見つかりますが、色が多いと調べる局面が膨大になります。

そろうまでの「遠さ」の目安

そこでアプリは、局面ごとにそろうまでの遠さの目安を数え、近そうな局面から先に調べます。目安は、次の2つの合計です。

  1. 器の中の色の切れ目の数: 下から見て、色が変わるところの数。
  2. 底の重なり: 同じ色がいくつもの器の底にあれば、その数から1を引いたもの。
123456

この盤なら、色の切れ目は1番が2つ、2番が2つ、3番が3つ、4番が3つで、合わせて10。水色が3番と4番の底にあるので、底の重なりが1。目安は11です。そろった局面では、切れ目も重なりもなくなるので、目安は0になります。

目安は、最少手数より大きくならない

この目安には、よい性質があります。1手で、目安は1より多くは減らないのです。

  • 注ぐ1回で、移す元の器の切れ目は、多くても1つしか減りません。移す先は同じ色の上か空いた器なので、切れ目はふえも減りもしません。
  • 器が空になって底の重なりが1つ減るのは、その器の最後のひと続きを移したときだけで、そのとき切れ目は減りません。

つまり、目安が11の盤は、少なくとも11手かかります。いろいろな盤で12万通りあまりの手を調べても、1手で目安が2以上減る手はありませんでした。上の盤の最少手数は、ちょうど11手です。

重みつきA*探索

アプリは、局面に「ここまでの手数 + 3 × 目安」という点をつけ、点の小さい局面から先に調べます。これを重みつきA*(エースター)探索といいます。

  • 重みを1にすると(ふつうのA*探索)、目安が最少手数の下限なので、必ず最少手数の答えが見つかります。
  • 重みを3にすると、目安が小さい局面をどんどん先に調べるので、答えがずっと早く見つかります。その代わり、最少手数より少し長い答えになることがあります。

アプリと同じ作り方で作った問題20問ずつで、そろうまでに調べた局面の数と、見つけた答えの手数を比べました(★3の幅優先探索は、局面が多すぎるので数えていません)。

★1(4色・空き2)調べた局面答えの手数
幅優先探索53711.8
A*(重み1)20311.8
A*(重み3)3911.9
★2(6色・空き2)調べた局面答えの手数
幅優先探索293418.1
A*(重み1)62218.1
A*(重み3)6418.8

どちらも20問の平均です。重み3は、幅優先探索の数十分の一の局面で答えを見つけ、手数の増え方はわずかでした。

調べる手を減らす工夫

アプリの解法は、ほかにも次の工夫で、調べる局面を減らしています。

  • 器の並び順を区別しない: 器の中身が同じなら、並び順がちがっても同じ局面として扱う。
  • 意味のない手を調べない: 1色だけの器を空いた器へ移す手(形が変わらない)と、2つ目以降の空いた器へ移す手(1つ目と同じ局面になる)は除く。
  • 「注ぐ」の手だけで探す: 「積む」の問題も、注ぐ手で解けるかを調べる(「注ぐ」と「積む」の違い)。
  • 上限を決める: 6万局面を調べても見つからなければ、「分からない」として、その配りは使わない。

この解法で、問題作りの「解けるかの確認」(必ず解ける問題の作り方)と「ひらめき」(ひらめきの使い方)の両方をまかなっています。底の色の考え方は、どの色から集める?でも紹介しています。