箱入り娘のはなし

箱入り娘は、4×5マスの箱の中で駒をすべらせ、いちばん大きな駒「娘」を下の出口まで運ぶパズルです。 駒は持ち上げられず、空いている2マスを使って少しずつ動かすしかありません。

「1手」の数え方で、最短が変わる

よく知られた配置の最短は81手です。ただしこれは「同じ駒を続けて動かす操作は、角を曲がっても1手」と数えた場合です。 駒が1マス動くごとに1手と数えると、最短は116手になります。

どちらの数字も、このサイトのプログラムで確かめました。最初の配置から1手で行ける並び方、2手で行ける並び方…と、近い順にすべて調べる方法（幅優先探索）です。 同じ形の駒を区別しなければ、この配置からたどり着ける並び方は全部で25,955通りあり、その中でゴールから最も遠い並び方は93手かかります。 このサイトの「最難」の配置がそれです。

同じしくみ、国ごとに違う物語

同じ系統のスライドパズルは、いくつもの国で別の名前と物語をまとってきました。

国・地域	名前と物語
アメリカ	ルイス・W・ハーディーが1907年に特許を出願し、1912年に認められました。1909年には「ペナント・パズル」の名で著作権が登録されています。野球の優勝旗（ペナント）が題材でした。 のちに「Dad's Puzzle（おやじのパズル）」などの名前でも広まりました。
イギリス	1934年に発行された特許に、箱入り娘とほぼ同じ配置が載っています。
フランス	「赤いロバ（L'Âne Rouge）」という名前の同系統のパズルがあります。
中国	「華容道」。大きな駒を三国志の曹操に見立て、関羽に見逃されて華容道を逃げのびる場面になぞらえています。 物語は古いのですが、パズルとしての確かな記録は1938年が最も古く、「華容道」という名前が本に出てくるのは1949年です。
日本	「箱入り娘」。大きな駒を大切に育てられた娘、まわりの駒を家族に見立てています。1930年代には遊ばれていたとされますが、誰が名付けたかは分かっていません。

英語圏でよく聞く「Klotski」という名前は、1991年のパソコン用ゲームの名前が広まったものとされています。

誰が最初に作ったのか

これは分かっていません。アメリカの特許は早い記録ですが、配置は箱入り娘とは違うものだったという資料もあり、そのまま「元祖」とは言えません。 中国の華容道も「三国時代から伝わる」と言われることがありますが、それを裏づける記録は見つかっていません。

1964年、数学コラムで世界へ

アメリカの科学雑誌『サイエンティフィック・アメリカン』で数学パズルの連載を持っていたマーティン・ガードナーが、1964年2月号でスライドパズルを特集しました。 81手の解はこの頃に誌面で紹介され、広く知られるようになりました。

解くときの考え方

• 空きマス2つを並べる。大きな駒は、空きが2マス並んでいないと動けません。まず空きを横か縦にそろえることを考えます。
• 小さな駒は「空きを運ぶ道具」。小さな駒を動かすのは、空きマスを行きたい場所へ移すためです。
• 横長の駒が関所。娘が下へ抜けるには、横長の駒をどけて2マス幅の通り道を作る必要があります。そこから逆算すると、次に何をすべきか見えてきます。

行き詰まったら、作品ページの「ヒント」で次の1手を見られます。最短手順の再生もできます。