15パズルの短い歴史
15パズルは昔からずっとあるように見えますが、だいたいの「誕生日」があります。1879年から1880年にかけての冬です。数字の木片が入った小さな箱が、数か月のうちにニューヨーク州北部の珍しいおもちゃから、アメリカとヨーロッパを席巻するブームになりました。
誰が発明したのか
長いあいだ、発明者はアメリカの有名なパズル作家サム・ロイドだとされてきました。ロイド自身が1890年代から自分の発明だと言っていたからです。でも実際は違いました。パズル史家のジェリー・スローカムとディック・ソンネフェルトがたどっていくと、ニューヨーク州カナストータの郵便局長ノイズ・チャップマンに行き着きました。彼は1870年代半ばにはこのパズルの一種を友人たちに見せていたのです。パズルはシラキュースへ、そしてボストンへと伝わり、1879年の終わりにはそこの木工職人が作って売り始めました。チャップマンは1880年に特許を出願しましたが、認められませんでした。
1880年のブーム
1880年の初め、「ジェム・パズル」「ボス・パズル」などの名前で売られたこの箱は、どこにでもありました。新聞には小箱にかじりつく人々の風刺画が載り、雇い主は仕事の時間が奪われると嘆き、禁止する店まで出ました。数週間で大西洋を渡り、イギリス、フランス、ドイツへ。そして来たときと同じくらいの速さで、夏までにはブームは去っていきました。
「14–15」パズルと賞金
熱狂の理由のひとつは、意地の悪い仕掛けでした。パズルは 14 と 15 だけが入れ替わった状態で売られることが多く、それを直してみろと挑まれたのです。解いた人に賞金を出すという話もありました。サム・ロイドは後に、自分も1,000ドルの賞金をかけたと語っていますが、実際にかけた証拠はありません。それでもこの話は広まりました。
賞金を手にした人はいません。誰にもできなかったからです。1879年、アメリカの数学者ウィリアム・ジョンソンとウィリアム・ストーリーが『アメリカン・ジャーナル・オブ・マセマティクス』に証明を発表していました。どのスライドでも、ある数え方の偶数・奇数は変わりません。だから並べ方のちょうど半分は完成形から行けて、残りの半分は行けないのです。「14–15」の配置は行けない側にありました。人気の遊びが数学の証明で決着した、最初期の例のひとつです。
盤面はいくつあるか
15枚のタイルと空きマスの並べ方は 16!（約20.9兆）通りあり、そのうち約10.5兆通りが解けます。紙と鉛筆で一つずつ確かめるには多すぎて、「いちばん難しい盤面は何手かかるのか」という問いは1世紀近く答えが出ませんでした。
それを変えたのがコンピューターです。1985年、リチャード・コーフは15パズルを題材に IDA* という探索法を発表しました。今も使われている方法で、このサイトのソルバーも使っています。1990年代にはチューリッヒの研究者たちが、どの15パズルも最大80手で解けること、そして80手ちょうどが必要な盤面も実際にあることを示しました。小さい8パズルなら最大31手です。5×5 の24パズルについては、正確な値はまだ分かっていません。
いろいろな呼び名
中国では15パズルを「数字华容道」（数字の華容道）と呼びます。もとになったのは、もっと古い中国のスライドパズル「華容道」です。三国志の曹操が、華容道で待ち伏せから抜け出すためにブロックを動かしていく遊びです。日本では「15パズル」、フランスでは taquin、スペインや中南米では juego del 15 と呼ばれています。このパズルが廃れたことはありません。安いプラスチック版は定番のポケットおもちゃになり、今のスピード勝負の名人は 4×4 を数秒で解いてしまいます。