15パズル(1880) — サム・ロイドが世界を騙した、解けない一手

はじめに

1880年の冬、アメリカ中が掌に収まる小さな箱に取り憑かれた。四角い枠のなかに1から15までの番号札が並び、空いた一マスを頼りに札を滑らせて、ばらばらの数字を順番どおりに並べ直す。それだけの玩具が、酒場でも事務所でも汽車のなかでも人々の指を止めさせ、新聞は「この熱病が仕事を麻痺させている」と書き立てた。これが、後に「15パズル」と呼ばれる滑り札遊びの最初の世界的流行である。

完成形(目標)。1から15まで順に並び、空白は右下に収まる。1880年、世界中がこの単純な並べ替えに熱狂した。

だが私が今回掘り返したいのは、流行そのものよりも、世間がこの箱の「発明者」として長く記憶した人物の正体だ。その名はサム・ロイド(Samuel Loyd, 1841-1911)。アメリカ随一のパズル作家にして元チェス棋士であった彼は、自分こそがこの狂騒を生んだ張本人だと語り、解けば千ドルを払うと懸賞まで掲げた。ところが、その主張には決定的な嘘が混じっていた。

本稿では、1880年の狂騒の本当の出自をたどり、ロイドが賞金を賭けた一つの盤面が、彼の名乗りより前の1879年に「数学的に絶対へ到達できない」と証明されていた事実を掘り起こす。そして、この古い木箱が、現代のデジタルパズルにまで受け継いだ「解けることをどう保証するか」という問いを、歴史の側から読み直してみたい。

その時代の文脈

滑り札のからくり自体は、1874年ごろニューヨーク州カナストタの郵便局長ノイズ・パーマー・チャップマン(Noyes Palmer Chapman)が考案したと考えられている。それが数年のあいだに人づてに広まり、商品として量産されると、1880年1月にアメリカで爆発的な流行が始まった。波は同年4月にはヨーロッパへ渡り、そして7月ごろにはあっけなく引いていく。狂騒はわずか半年ほどの、短くも激しい熱病だった。

サム・ロイドがこのパズルを「自分の発明だ」と語り始めたのは、流行が去ってずっと後のことである。彼が15パズルについて最初の記事を世に出したのは1896年、狂騒の最高潮から数えて十六年も後だった。実際の流行に彼が関与した形跡はない。にもかかわらずロイドは、死ぬまでの長い年月をかけて、繰り返し自作を主張し続けた。

この詐称が完全に解きほぐされたのは、ずっと近年のことだ。パズル史家ジェリー・スロカム(Jerry Slocum)とディック・ソネベルト(Dic Sonneveld)が2006年の著書『The 15 Puzzle』で当時の一次資料を突き合わせ、ロイドの名乗りが百十五年にわたる作り話であったことを丹念に立証した。発明の栄誉は、無名の郵便局長にこそ帰すべきものだった。

メカニクス

ルールは単純きわまる。4×4の枠に15枚の札と一つの空白があり、空白に隣接した札だけを滑り込ませて動かせる。目標は数字を1から15まで順に並べ、空白を所定の隅へ収めること。手数の上限はなく、誰にでも触れる。この素朴さこそが、1880年の人々を捉えた魅力だった。

ロイドが懸賞に出した盤面。1〜13は順に並び、14と15だけが入れ替わっている(破線)。目標は左上から順に揃え空白を右下へ送ることだが、この配置はパリティが逆で、どう滑らせても到達できない。

ところが、この遊びには見えない壁があった。アメリカの数学者ウィリアム・ジョンソン(William Woolsey Johnson)とウィリアム・ストーリー(William E. Story)は、1879年に『American Journal of Mathematics』へ「15パズルについての覚書」を寄せ、パリティ(置換の偶奇)による議論で、初期配置の半分は何手かけても絶対に揃わないことを証明した。すなわち、ある盤面が解けるか否かは、運や根気ではなく、最初から数学的に決まっている。

ロイドが千ドルを賭けた盤面は、まさにこの「解けない半分」に属していた。彼が出題したのは、14と15だけが入れ替わった、ほぼ完成した配置である。一見あと一歩に見えて、パリティが逆ゆえに正解へは決して到達できない。賞金は安全だった。彼は、数学的な不可能性を「解けそうな難問」として売り、群衆に永遠の徒労を競わせたのだ。これは発明ではなく、不可能性の演出だった。

現代への系譜

ジョンソンとストーリーが拓いた「盤面の状態空間を数学で読む」という視座は、その後の計算機科学へまっすぐ伸びている。1990年にダニエル・ラトナー(Daniel Ratner)とマンフレッド・ウォーマス(Manfred Warmuth)は、15パズルをn×nに一般化した問題で「最短手数を求めることはNP困難である」と示した(初出は1986年のAAAI)。盤を大きくすれば、最適解探索は計算量的に手に負えなくなる。1879年の偶奇の問いは、現代の難しさの理論へと地続きだったのだ。

盤を n×n に一般化すると、最短手順を求めることは計算量的に手に負えなくなる(NP困難)。1879年の偶奇の問いは、現代の「難しさ」の理論へと地続きだった。

そしてこの系譜は、いまデジタルで滑り札を扱うすべての作り手に、静かに重くのしかかっている。タイルをランダムに混ぜて出題するパズルを実装する者は、必ずジョンソン=ストーリーの定理を踏まえねばならない。素朴に札を散らすと、半分の確率で「絶対に解けない盤面」をプレイヤーへ突きつけてしまうからだ。だから現代のスライドパズルの生成器は、内部でパリティを検査し、解ける盤面だけを配るよう作られている。1879年の証明は、いまも実装の前提として生きている。

ロイドが残したものは、発明の栄誉ではなく、もっと厄介な教訓だった。パズルの難しさは、ときに「困難」を通り越して「不可能」に達しうること。そして、その不可能性を見抜けぬ者には、解けない盤面と難しいだけの盤面の区別がつかないこと。出題者が解の存在を保証する責任を負う、という現代パズル設計の倫理は、皮肉にも彼の千ドルの嘘が最も鮮やかに照らし出している。

参考文献

本記事で参照した情報源:

・Wikipedia: 15 puzzle

・Cut the Knot: Sam Loyd's Fifteen, the history of the puzzle

・David Richeson: A picture of frustration — Sam Loyd's 15 puzzle

・MacTutor History of Mathematics: Samuel Loyd (1841-1911)

・Wikipedia: Sam Loyd

・Jerry Slocum & Dic Sonneveld, The 15 Puzzle: How It Drove the World Crazy (Slocum Puzzle Foundation, 2006)

・W. W. Johnson & W. E. Story, “Notes on the ‘15’ Puzzle,” American Journal of Mathematics, vol. 2, no. 4 (1879), pp. 397–404

・D. Ratner & M. Warmuth, “The (n²−1)-puzzle and related relocation problems,” Journal of Symbolic Computation, vol. 10 (1990), pp. 111–138 (初出: AAAI 1986)

・Wolfram MathWorld: 15 Puzzle

おわりに

15パズルが歴史的に示したのは、二つのことだと私は考える。一つは、ごく単純な滑り札の規則が、状態空間という近代数学の対象を一般大衆の掌に乗せてしまったということ。1880年の人々は、自分が偶置換と奇置換の境界をなぞっているとは知らずに、純粋な論理の壁に指を擦り減らしていた。パズルが数学を民主化した、稀有な瞬間である。

もう一つは、出題者の誠実さという問題だ。サム・ロイドは発明者ではなかったが、彼が懸賞に仕込んだ「解けない盤面」は、皮肉にもパズル設計の核心を後世へ突きつけた。解の存在を保証できない出題は、難問ではなく欺瞞である。1879年の証明と1880年の狂騒は、百四十年を経たいまも、札を混ぜるすべての作り手に同じ問いを投げかけている――その盤面は、本当に解けるのか、と。