スライドパズルの歴史：15パズルからRush Hourへ

中心のアイデアは、ピースが入り、少し空間の足りない枠です。空いた場所へだけ動かせます。有名な版の前に、すでに紙に記されていました。1878年にErnest Kinseyへ与えられた米国特許は、一つのすき間のある枠内で滑るパズルブロックを説明しています。

有名にしたのは15パズルです。4×4のトレーに15枚の番号付きタイルと一つの空間があります。Jerry SlocumとDic Sonneveldの長年の研究は、2006年の本The 15 Puzzleで、ニューヨーク州Canastotaの郵便局長Noyes Chapmanにたどります。1879年末にはGem Puzzleとして売られていました。

出典1出典1Kinsey, E. U. (1878). Improvement in puzzle-blocks (U.S. Patent No. 207,124). U.S. Patent Office.2出典2Slocum, J., & Sonneveld, D. (2006). The 15 puzzle: How it drove the world crazy. Slocum Puzzle Foundation.

1880年初頭、15パズルは熱狂になりました。数週間で米国全体と欧州へ広がり、事務所、居間、新聞の欄に現れました。正確な週は説明が異なりますが、春には至るところにあり、夏には薄れていました。Chapmanの特許申請は拒否されました。理由は不確かで、以前のスライドパズル特許がすでに覆っていたというのが有力な説明の一つです。

魅力の一部は、解けないように見える初期配置があり、本当に解けないことでした。1879年、William Woolsey JohnsonとWilliam StoryはAmerican Journal of Mathematicsで、配置の正確に半分が解けないと示しました。根拠は偶奇性です。各スライドは隠れた偶数・奇数の数え方を一定に保つため、違う値の配置には、どれほど試しても届きません。

これが最も有名な仕掛けを説明します。完成したトレーの14と15だけを替えると、あと一手に見えて、実際には到達できない配置になります。

出典3出典3Johnson, W. W., & Story, W. E. (1879). Notes on the “15” puzzle. American Journal of Mathematics, 2(4), 397–404.

20世紀の大部分、15パズルは米国の有名パズル作家Sam Loydの発明とされました。Loydは発明したと言い、不可能な14・15交換を解く大きな賞金を出しました。SlocumとSonneveldによれば、最初の主張は熱狂から10年以上後の1891年で、1911年の死まで続けました。発明に関わった証拠も、1880年に賞金を出していた証拠もありません。

有名なLoydの本が広く再版され、後の作家が繰り返したため、主張は定着しました。パズル史も他の歴史同様、記録と照合する価値があると思い出させます。

出典2出典2Slocum, J., & Sonneveld, D. (2006). The 15 puzzle: How it drove the world crazy. Slocum Puzzle Foundation.

次の大きな家族は目標を変えました。順に並べるのでなく、小さなブロックの群れを通し、大きな一つを出口へ動かします。Lewis W. Hardyが1907年に申請し1912年に得た特許は、異なる大きさの10個を箱に詰め、滑らせるだけで動かすものです。近い設計がPennant Puzzleとして売られました。

似たパズルは多くの名で続きました。Smithsonianには、1926年著作権のDad’s Puzzlerがあり、大きな正方形一つ、複数の長方形、小さな正方形二つがあります。現在多くの国でKlotskiと呼び、中国のHuarong Dao（華容道）は将軍の包囲からの脱出を語ります。古典配置の最短解は、一手の数え方によって約80手です。

1990年代、最も成功した現代形が現れました。日本の作家Nob YoshigaharaはTokyo Parkingという滑る車のパズルをつくり、Binary Arts、後のThinkFunが1996年に米国でRush Hourとして発売しました。小さな格子を車とトラックがふさぎ、前後に動かし自分の車を出します。段階別カードで一問からシリーズへ変わり、教室と家族のテーブルの定番になりました。

出典4出典4Hardy, L. W. (1912). Puzzle (U.S. Patent No. 1,017,752). U.S. Patent Office.5出典5Smithsonian National Museum of American History. (n.d.). Dad’s Puzzler, once owned by Olive C. Hazlett [Object 2015.0027.04].6出典6Contreras, M. (2018, February 1). The evolution of ThinkFun’s Rush Hour. ThinkFun. Archived by the Internet Archive, 25 December 2022.

おもちゃに見えますが、計算機科学では重要な対象です。解ける15パズルは最大80回の単一タイル移動で終わると確立したのは1999年でした。KorfとSchultzeは後に、28日間の探索で、80手すべてが必要な配置が正確に17あると確認しました。

2002年、Gary FlakeとEric Baumは、任意サイズの一般化したRush HourがPSPACE完全だと証明しました。有名なNP完全よりさらに難しいと考えられる問題のクラスです。Robert HearnとErik Demaineは2005年、すべて同じ小さなドミノでも、一般のスライドブロックがPSPACE完全だと示しました。簡単にいえば、全盤面をすばやく解く既知の近道はなく、それが良いパズルが興味深い理由です。

出典7出典7Korf, R. E., & Schultze, P. (2005). Large-scale parallel breadth-first search. In Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI-05) (pp. 1380–1385). AAAI Press.8出典8Flake, G. W., & Baum, E. B. (2002). Rush Hour is PSPACE-complete, or “Why you should generously tip parking lot attendants”. Theoretical Computer Science, 270(1–2), 895–911.9出典9Hearn, R. A., & Demaine, E. D. (2005). PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1–2), 72–96.

OutBrickは一つを出す系統に属し、独自のひねりがあります。すべてのブロックに行き先があります。同じ色のゲートからだけ出られ、いまはとなりのブロックと入れ替えて、同じ色を3つ並べて消すこともできます。HardyのブロックやYoshigaharaの車と同じく、クリアには順序を考えます。

現代の道具は1880年の人がうらやむ助けになります。OutBrickの2,000ステージは公開前にすべてソルバーがクリアし、14・15の交換には出会いません。実用面はスライドブロックの解き方に戦略があり、ブラウザで試すこともできます。

• 1870年代後半：枠内の滑るブロックが米国特許に現れる
• 1879年末：15パズル発売。JohnsonとStoryが半分は解けないと証明
• 1880年：米国と欧州を熱狂が席巻
• 1891年：Sam Loydが初めて発明を主張
• 1907〜1912年：Hardyの一つを出すパズルが特許を取得
• 1996年：Rush Hourが米国で発売
• 2002〜2005年：Rush HourとスライドブロックのPSPACE完全性を証明