1,000ドルの懸賞と、絶対に揃わない16パズルの話

Claudeに、16パズルを作ってもらいました。

4×4のマスに1から15までのパネルが並んでいて、空いた一マスにずらしていく、あれです。頼んだのは、それだけ。

簡単な注文のつもりでした。1から15までとカラを並べて、シャッフルして、順番に揃ったら終わり。難しいところは、どこにもなさそうに見えます。

ところが、返ってきた説明に、こう書いてありました。

ランダムに並べると、絶対に揃わない問題が出てしまうので、完成形から逆に崩しています

絶対に揃わない問題。なんのことだか、最初はわかりませんでした。

適当に並べては、いけない

16個をランダムに置く。プログラムとしては1行です。でも、それをやると本当に、どうやっても揃わない問題が出てしまう。しかも、たまにではありません。

正確には、ちょうど半分です。16個の置き方は全部で16の階乗、20兆通りあまり。そのうち半分は、どんなに動かしても1から15の順番にはなりません。もう半分は必ず揃います。きれいに半々です。

いちばん有名な例が、これです。1から13までは正しく並んでいて、14と15だけが入れ替わっている。あと一手に見えます。でも、揃いません。何時間動かしても、何年動かしても揃いません。

パネルをずらすという操作には、崩せない決まりがあります。空白を1回動かすたびに、並びの「ねじれ具合」と空白の位置が、必ずセットで裏返る。だから、最初にどちらの側に置かれたかで、行ける先が決まってしまう。ずらして遊んでいるだけのつもりが、実は半分の世界には最初から入れないわけです。

調べてみたら、このパズルには相当な前科がありました。

アメリカで生まれたのは1870年代の後半。ニューヨーク州カナストータの郵便局長、ノイズ・パーマー・チャップマンという人が考案したとされています。長いあいだ、有名なパズル作家サム・ロイドの発明だと信じられていましたが、それは違ったことが後の研究でわかりました。

そして1880年、ヨーロッパまで巻き込んで流行が頂点に達します。

ロイドはここに乗りました。本人が後年語ったところによれば、新聞社に持ちかけて、あの14と15が入れ替わった配置を「解けたら1000ドル」の懸賞問題として載せたそうです。賞金は自分が払うとまで言った。

もちろん、誰も受け取れませんでした。

ついでに言うと、ロイドはこのパズルをアメリカで特許にしようとして、断られています。理由が愉快で、「解けないパズルには、動く模型が作れない」。特許庁の役人の言い分としては、まったく正しい。

そして、いちばん皮肉なのはここです。懸賞が出るより前の1879年に、数学者がすでに答えを出していました。ジョンソンが「揃わない側は絶対に揃わない」ことを示し、ストーリーが「揃う側は必ず揃う」ことを示した。二本とも『アメリカ数学雑誌』に載っています。

証明は、すでに世に出ていた。それでも人々は、何日も机に向かっていたわけです。

というわけで、最初の説明に戻ります。このサイトの16パズルは、シャッフルという処理をしていません。

やっていることは逆です。まず1から15まで完成した状態を作る。そこから空白を、上下左右にランダムに400回動かす。それだけです。1回だけ、直前に戻る動きは禁止にしてあります。同じところで往復して、ほとんど崩れないのを防ぐためです。

完成形から実際に動かして作った配置なので、手順を逆にたどれば必ず完成形に戻ります。揃わない問題は、原理的に一問も出ません。判定式を書く必要もありません。

あの半分の世界には、そもそも足を踏み入れていない、という作り方です。

3×3の9パズルも選べるようにしました。4×4がしんどいときは、こちらでどうぞ。タイムは端末の中に残るので、自分の記録とだけ勝負できます。

1880年の人たちが何日もかけて格闘した配置を、私たちは最初から避けている。ずるいような気もしますが、信号待ちの30秒で解けない問題を渡されても困りますからね。

遊んでみてください。→ 16パズル