アプリ「ソートパズル」は、問題を出す前に、コンピューターで解けることを確かめています。「ひらめき」の次の一手も、同じ解法が見つけた手順の1手目です。ここでは、その解法のしくみを紹介します。
局面と手をたどる
ソートパズルの盤の状態(どの器に何色が入っているか)を局面と呼びます。1手移すと、別の局面になります。最初の局面から手をたどっていき、そろった局面に着けば、たどった道が答えです。
いちばん素直な探し方は、1手で行ける局面を全部、次に2手で行ける局面を全部……と広げていく幅優先探索です。必ず最少手数の答えが見つかりますが、色が多いと調べる局面が膨大になります。
そろうまでの「遠さ」の目安
そこでアプリは、局面ごとにそろうまでの遠さの目安を数え、近そうな局面から先に調べます。目安は、次の2つの合計です。
- 器の中の色の切れ目の数: 下から見て、色が変わるところの数。
- 底の重なり: 同じ色がいくつもの器の底にあれば、その数から1を引いたもの。
この盤なら、色の切れ目は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) | 調べた局面 | 答えの手数 |
|---|---|---|
| 幅優先探索 | 537 | 11.8 |
| A*(重み1) | 203 | 11.8 |
| A*(重み3) | 39 | 11.9 |
| ★2(6色・空き2) | 調べた局面 | 答えの手数 |
|---|---|---|
| 幅優先探索 | 2934 | 18.1 |
| A*(重み1) | 622 | 18.1 |
| A*(重み3) | 64 | 18.8 |
どちらも20問の平均です。重み3は、幅優先探索の数十分の一の局面で答えを見つけ、手数の増え方はわずかでした。
調べる手を減らす工夫
アプリの解法は、ほかにも次の工夫で、調べる局面を減らしています。
- 器の並び順を区別しない: 器の中身が同じなら、並び順がちがっても同じ局面として扱う。
- 意味のない手を調べない: 1色だけの器を空いた器へ移す手(形が変わらない)と、2つ目以降の空いた器へ移す手(1つ目と同じ局面になる)は除く。
- 「注ぐ」の手だけで探す: 「積む」の問題も、注ぐ手で解けるかを調べる(「注ぐ」と「積む」の違い)。
- 上限を決める: 6万局面を調べても見つからなければ、「分からない」として、その配りは使わない。
この解法で、問題作りの「解けるかの確認」(必ず解ける問題の作り方)と「ひらめき」(ひらめきの使い方)の両方をまかなっています。底の色の考え方は、どの色から集める?でも紹介しています。
