15パズルのはなし

並べ方の半分は、どうやっても完成しない。1879年に証明されたその理由と、発明者をめぐる取り違え。

15パズルは、4×4の枠に1から15までの番号つきタイルが並び、空きマスが1つだけあるパズルです。タイルを空きマスへすべらせて、番号を順番に並べます。いちばん不思議なのは、ばらばらの並べ方のちょうど半分は、どんなに動かしても完成しないことです。

なぜ半分は解けないのか

タイルを1枚動かすと、空きマスと隣り合ったタイルが入れ替わります。ここで、空きマスを除いて左上から順に数字を読み、「大きい数が、小さい数より先に出てくる組」を数えてみます。これを「逆転」と呼ぶことにします。完成形の並びには逆転が1組もありません。

左右にすべらせる場合、数字を読む順番は変わらないので、逆転の数も変わりません。上下にすべらせる場合は、動いたタイルが同じ列の間にある3枚を飛び越えます。飛び越えられる3枚との前後が1組ずつ入れ替わるので、逆転の数は3、1、あるいは−1、−3のどれかだけ変わります。つまり偶数か奇数かが必ず入れ替わるのです。いっぽう空きマスは、上下に動くたびに1行ずつ動きます。そこで「逆転の数」と「空きマスの行」を足した値の偶奇は、どう動かしても変わりません。

だから、完成形と偶奇が違う並べ方は、永遠に完成形になりません。偶奇が合う並べ方はすべて解けることもわかっていて、解ける配置は全体のちょうど半分です。 4×4では、全部で16!通りの並べ方のうち、解ける並べ方は約10兆（16!÷2＝10,461,394,944,000）通りです。たとえば、完成形の14と15だけを入れ替えた配置は、逆転が1組だけ増えて偶奇が変わるので、解けません。

この性質は1879年に、W・W・ジョンソンが「奇数のものは不可能」、W・E・ストーリーが「偶数のものはすべて可能」と、2人の論文で示したとされています。このサイトの3×3版では、すべての並べ方（9! ＝ 362,880通り）について、この偶奇の判定が実際に動かして到達できるかどうかと一致することを、プログラムで確かめています。作品ページの「解けない盤面を試す」で、実際に確かめられます。

発明者は、サム・ロイドではなかった

15パズルは、アメリカの有名なパズル作家サム・ロイドの発明だと長く言われてきました。けれども、近年の研究では、ロイドは発明にも流行にも関わっていないとされています。考案者は、ニューヨーク州の小さな町の郵便局長ノイズ・パーマー・チャップマンとされています。1870年代半ばには、前身にあたるブロックのパズルがあったようです。チャップマンは特許を申請しましたが、通らなかったらしい、とされています。

ロイドが「自分が発明した」と言いはじめたのは、1880年の流行より10年以上あとのことです。ロイドが「14と15を入れ替えた配置を戻せたら1000ドル」という懸賞を出したという話も有名ですが、実際に出たかどうかは確かめられていません。ロイド本人が晩年に、そのような懸賞を出したと書き残している、というところまでが確かな話です。

1880年の大流行

1879年の暮れごろ、ボストンの木工業者が「ジェム・パズル」の名前で売りだしました。流行は1880年1月にアメリカで始まり、4月にはヨーロッパに届き、夏にはおさまったとされています。半年足らずの大騒ぎでした。

日本には、1907年の本『世界遊戯法大全』に「十五置き換え遊び」という名前で紹介されたとされています。

最短で何手？

「最短」は、どう数えるかで変わります。タイルを1枚ずつ動かす数え方では、3×3の8パズルは、解ける配置のすべてが31手以内で解けます。このサイトのプログラムで、到達できる181,440通りの配置を近い順にすべて調べ、いちばん遠いものが31手であることを確かめました。 4×4の15パズルでは、1枚ずつの数え方で最大80手とされ、80手かかる配置は17通りあります。この数字は1990年代の終わりに、大がかりな探索で確かめられました。列になったタイルを一度にまとめて動かすことを1手と数えれば、最大43手になります。

このサイトの遊ぶ画面は、まとめて動かす1回の操作を1手と数えます。

解くときの考え方

上の行から順に固める。1、2、3、4の行ができたら、もうその行は動かしません。次は左の列、というように、盤を小さくしていきます。
最後の2枚は、ひと工夫。行の最後の2枚は、そのまま入れようとすると空きマスが届きません。わざと一度ずらして、2枚を同時に入れる手順を考えます。
空きマスは「運ぶもの」。タイルを動かしたいときは、空きマスをその隣へ回り込ませます。すでに並べたタイルをくずさない道を考えます。
解けない盤面もある。どうしても最後の2枚が逆になるなら、その並びは偶奇が合っていません。