およそ100～150年の歴史を持つといわれる 箱入り娘 というパズルがあります。
空いているマスを利用してブロックをスライドし、「娘」と書かれた下段の中央列まで移動できればクリアです。開始時のブロックの配置次第で、楽に解けるものにもなれば、非常に難解な問題にもなります。
先日 Rust の勉強の一環でこの箱入り娘の解法を見つけ出すプログラムを書いたのですが (公開は準備中です🙇)、解くだけでは勿体ないので 一番手数のかかる問題 (=もっとも気難しい箱入り娘) はどれなのか、全配置パターンを分析しました。この記事では、その結果を記します。
なお、局面を洗い出すにはいたってシンプルな方法を採用しています。ペントミノ と同じ要領で、ブロックおよび2つの空きマス領域を盤面に敷き詰めてみて、すべて敷けたら解けるかどうかを試す、というのをひたすら繰り返しました。
ブロックの構成について
以下の画像は筆者の手元にある箱入り娘で、ブロックとして「娘」(2x2) の他に、横長 (2x1) または縦長 (1x2) として使えるものが5つ、最小の正方形 (1x1) のものが6つ入っています。日本で流通しているものでは、これが一般的のようです。
パズルの開始局面とするには、ここから2マス分のブロックを取り除いて空きマスを作らないと、ブロックをスライドできません。どれを取り除くかによって、使用するブロックの構成は次の2通りあります。
| ブロックの構成 | 「横長/縦長5個」形 | 「横長/縦長4個」形 |
|---|---|---|
| 取り除くブロック | 最小正方形を2個 | 横長/縦長を1個 |
| 使用する「娘」の個数 | 1 | 1 |
| 使用する「横長/縦長」の個数 | 5 | 4 |
| 使用する「最小正方形」の個数 | 4 | 6 |
なお、さらに多くのブロックを取りのけてもある程度はパズルとして成立しますが、単に難易度が下がるだけで本稿の趣旨から外れるため調査はしていません。
手数について
箱入り娘では、「同じブロックを移動させ続けている限り、一手と数える」という慣習があります。たとえば、次のように右下のブロックを左、上と連続して移動させた場合も一手とします。
本稿の手数のカウントも、この方式に従っています。
もっとも気難しい娘
では、結果です。「横長/縦長5個」形と「横長/縦長4個」形の両方についてそれぞれ記します。
まずは「横長/縦長5個」形。手数は138手です。
局面は3つありますがブロックの配置は微差で、実質的には同じといえます。あと言い忘れてましたが箱入り娘は左右対称なので、左右反転した局面は同一とみなして片方だけ載せています (以下同様)。
つづいて「横長/縦長4個」形ですが、75手でした。こちらも局面が2つありますが、右上の最小正方形の位置以外は同じです。
ということで、もっとも気難しかったのは「横長/縦長5個」家のご息女で、138手でした。もはや人力では、解ける気がしない手数です。冒頭に載せた写真の配置は81手かかる問題で、箱入り娘では有名な「難しい」部類の配置なのですが、最長手数問題はそこからさらに50手以上多いことになります。
さて、これで結論は書いてしまったのですが、もう少し続けます。個人的には、最長手数問題の「娘」の位置が最上段の隅でなかったのが意外でした。なんとなく「ゴールまで最も遠い場所にあるのが、一番難しいんじゃいか」と思っていたからです。
そこで、娘の開始位置別の最長手数問題を調べてみることにしました。つまり、地域別の最も気難しい娘が誰なのか、分析してみました ということです。
「最上段 左端」の気難しい娘
「横長/縦長5個」形では、135手が最長です。
「横長/縦長4個」形では69手。
「最上段 中央」の気難しい娘
「横長/縦長5個」形では128手が最長です。
「横長/縦長4個」形では75手。前述したように、「横長/縦長4個」形での最長手数です。
「2段目 左端」の気難しい娘
「横長/縦長5個」形では138手。既に記しましたが、箱入り娘の最長手数です。
「横長/縦長4個」形では、68手が最長です。
「2段目 中央」の気難しい娘
「横長/縦長5個」形では103手。娘の開始位置別でみると、「横長/縦長5個」形で最も短い手数です。局面が完全に左右対称ですね。
「横長/縦長4個」形では59手です。
「3段目 左隅」の気難しい娘
「横長/縦長5個」形では112手。
「横長/縦長4個」形では62手です。2 つの局面はおおむね同じものの、一方からもう一方の局面にするには4手必要です。
「3段目 中央」の気難しい娘
娘をあと一マス下へずらせれば終わりですが、けっこう手数がかかります。「横長/縦長5個」形では109手。
「横長/縦長4個」形では71手。
「4段目 左端」の気難しい娘
やはり娘を右に一つずらせば終わりですが、最長手数を誇る問題は容易ではありません。「横長/縦長5個」形では105手。最長手数同士だと似通った局面が多かったですが、この 2 つの局面には割と差異があります。
「横長/縦長4個」形では56手。娘の開始位置別でみると、「横長/縦長4個」形で最も短い手数です。
おわりに
まとめると、最長手数は次の通り。
| 使用するブロックの型 | 「横長/縦長5個」形 | 「横長/縦長4個」形 |
|---|---|---|
| 娘の位置は問わない | 138 | 75 |
| 「最上段 左端」に娘 | 135 | 69 |
| 「最上段 中央」に娘 | 128 | 75 |
| 「2段目 左端」に娘 | 138 | 68 |
| 「2段目 中央」に娘 | 103 | 59 |
| 「3段目 左端」に娘 | 112 | 62 |
| 「3段目 中央」に娘 | 109 | 71 |
| 「4段目 左端」に娘 | 105 | 56 |
「横長/縦長5個」形のほうは、手数がすべて3桁。対する「横長/縦長4個」形はすべて2桁で、最長でも75手となっています。「横長/縦長5個」は横長/縦長ブロックが一つ多いので、ブロックの移動の制限がより厳しくなります。それが、手数の増加を招いているようです。
解析に要する時間は逆で、圧倒的に「横長/縦長5個」形のほうが速く終わりました。Intel Core i7 12700 を積んだ PC 上で 8 スレッド並列による解析を実施したところ、「横長/縦長5個」形は5時間ほどでしたが「横長/縦長4個」形では14時間ほどかかりました。「横長/縦長5個」はブロックの配置にも制約が大きいため、解法を持つ局面の数が144,000個程度なのに対して、「横長/縦長4個」形では約270,000個とおよそ2倍見つかるためです。
(これら局面の総数では、娘が右端の列にいる局面と、娘が下段中央にいて手数ゼロで解ける局面を除外しています。)
各局面の解法については、巷で公開されているアプリ等で確かめて下さい。拙作のプログラムが公開できればそれを使うこともできるのですが、しばらくお待ち下さいませ。