ソートパズルを解くのに、少なくとも何手かかるのでしょうか。アプリ「ソートパズル」の★1(4色・空き2)の大きさなら、配りを全部調べられます。「注ぐ」の手で、すべての配りの最少手数を数えてみました。
調べ方
- 同じ色が3つ以上続く器のない「公平な配り」だけを調べる(アプリが出すのは、この配りだけです)。
- 器の並び順を入れかえただけの配りや、色を塗りかえただけの配りは、同じものとみなす。すると89,675種類になります(配り方は何通り?)。
- それぞれの配りで、1手で行ける局面、2手で行ける局面……と全部広げて、最初にそろう手数を求める(幅優先探索)。
最少手数の分布
| 最少手数 | 配りの種類 |
|---|---|
| 5手 | 3 |
| 6手 | 8 |
| 7手 | 124 |
| 8手 | 741 |
| 9手 | 3,523 |
| 10手 | 11,070 |
| 11手 | 21,321 |
| 12手 | 26,778 |
| 13手 | 19,271 |
| 14手 | 6,635 |
| 15手 | 197 |
| 16手 | 4 |
いちばん多いのは12手で、10〜13手で全体の8割以上になります。5手で解ける配りは3種類、16手かかる配りは4種類しかありません。
(ここでの数は「種類」です。アプリで実際に配られる確率は、種類ごとに少しずつちがいます。)
いちばん短い盤(5手)
どの器も、同じ色が2つずつ重なっています。空いた器2つを使って、5手でそろいます。
いちばん手数のかかる盤(16手)
1番と2番、3番と4番が、まったく同じ並びになっています。どの器も、となりあう色がすべてちがっていて、赤と黄緑はそれぞれ2本の器の底にあります。
16手の手順を見る
手数の下限を見つける
最少手数は、全部調べなくても、下限(これより少なくはならない数)なら盤を見るだけで分かります。
- 器の中の、色の切れ目の数を数える。
- 同じ色がいくつもの器の底にあれば、「その数-1」を足す。
この合計は、注ぐ1回で多くても1しか減らないので、最少手数より大きくなりません(コンピューターで解く)。
- 5手の盤: 切れ目が4つ、赤が2本の底にあるので1を足して、下限は5。ちょうど最少手数です。
- 16手の盤: 切れ目が12、赤と黄緑がそれぞれ2本の底にあるので2を足して、下限は14。実際には16手かかります。
89,675種類のうち、下限と最少手数がちょうど一致したのは38,571種類(約43%)でした。残りは、下限より多くかかります。
もっと大きい盤では
色が増えると、配りが多すぎて全部は調べられません。アプリと同じ作り方で作った問題20問ずつの最少手数の平均は、★1が11.8手、★2(6色)が18.1手でした。★3以上は、1問の最少手数を求めるのにも時間がかかります。
アプリの「ひらめき」は、最少手数ではなく、早く見つかる解き方を教えます。最少手数に挑戦するなら、下限を目安に、自分で手順を考えてみてください(ひらめきの使い方)。
