ソートパズルを解くのに、少なくとも何手かかるのでしょうか。アプリ「ソートパズル」の★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手)

123456
1手目 3→5(2つ)
123456
2手目 1→3(2つ)
123456
3手目 4→5(2つ)
123456
4手目 2→4(2つ)
123456
5手目 1→2(2つ)
123456
そろった

どの器も、同じ色が2つずつ重なっています。空いた器2つを使って、5手でそろいます。

いちばん手数のかかる盤(16手)

123456

1番と2番、3番と4番が、まったく同じ並びになっています。どの器も、となりあう色がすべてちがっていて、赤と黄緑はそれぞれ2本の器の底にあります。

16手の手順を見る
123456
1手目 1→5
123456
2手目 1→6
123456
3手目 2→5
123456
4手目 2→6
123456
5手目 1→2
123456
6手目 1→5
123456
7手目 2→1(2つ)
123456
8手目 2→5
123456
9手目 3→2
123456
10手目 3→6
123456
11手目 3→1
123456
12手目 2→3
123456
13手目 4→3
123456
14手目 4→6
123456
15手目 4→1
123456
16手目 3→4(3つ)
123456
そろった

手数の下限を見つける

最少手数は、全部調べなくても、下限(これより少なくはならない数)なら盤を見るだけで分かります。

  1. 器の中の、色の切れ目の数を数える。
  2. 同じ色がいくつもの器の底にあれば、「その数-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問の最少手数を求めるのにも時間がかかります。

アプリの「ひらめき」は、最少手数ではなく、早く見つかる解き方を教えます。最少手数に挑戦するなら、下限を目安に、自分で手順を考えてみてください(ひらめきの使い方)。