Rush Hour(1996) — 木箱の交通渋滞が、PSPACE完全の証明を受け取った年

はじめに — 赤い車を出すためだけの盤

これは1996年、米国のBinary Arts社(現在のThinkFun)が世に出した木製のスライドパズル「Rush Hour」の話である。盤は6×6のマス目。そこに乗用車12台とトラック4台、合わせて16台の駒がひしめく。ルールはたったひとつ——駒は最初に置かれた向きのまま、前か後ろにしか滑らせられない。回転も、持ち上げることも許されない。

目的はさらに単純だ。出口に面した1台だけ赤い車を、周りを塞ぐ駒をどかしながら盤の外へ出す。ただそれだけの遊びのはずが、1台を動かせば、別の1台の逃げ道がふさがる。発売直後から売れ続け、これまでに100万個以上が世に出た。

赤い車と、それを塞ぐ駒たちのイメージ（イメージ・AI生成）

その時代の文脈 — 芦ヶ原伸之という日本のパズル作家

考案者は日本のパズル作家、芦ヶ原伸之(1936-2004)である。東京工業大学で応用化学を学んで化学者になり、のちに高校で数学と化学を教えながら、生涯に80冊を超えるパズルの本を書いた人物だ。同じ芦ヶ原の手は、1983年に発売されたハナヤマの金属パズル「キャストパズル」の監修にも伸びている。

彼が考えたのは、もともと「Tokyo Parking(東京の駐車場)」という名の木製スライドパズルだった。渋滞にはまった車という、誰もが知る苛立ちをそのまま盤にした遊びである。1995年、このパズルはBinary Arts社に持ち込まれた。

開発チームは当初「Bad Traffic」「Move It!」といった、渋滞の不快感をそのまま名乗る仮のタイトルで検討を進めていた。だが方向を180度転換し、渋滞を抜け出す達成感を祝う物語へ作り替える。赤い脱出車の運転手には「Rush Hour Joe」という名が与えられ、1996年、正式に「Rush Hour」として発売された。

木箱のパズルから飛び出す一台のイメージ（イメージ・AI生成）

メカニクス — 前後にしか動かせないという、一つの規則

盤の規則は驚くほど少ない。6×6のマス目に、2マス分の長さを持つ乗用車が12台、3マス分の長さを持つトラックが4台。どの駒も縦か横のどちらかに固定された向きを持ち、その一本の線の上でしか前後に滑らない。斜めにも、別の向きにも動かせない。

赤い車だけは出口の列に固定され、目的はその手前を塞ぐ駒をどかして出口まで押し出すことだけだ。だが1台を動かせば、別の1台の通り道がふさがる。盤全体が、互いの可動域を奪い合う関係で編まれている。

同梱される問題カードは40枚、初級(Beginner)から上級(Expert)まで4段階の難易度で並ぶ。もっとも難しいとされる配置は、駒を動かす回数で数えると51手、1マスずつの移動で数えると93ステップを要することが確認されている。駒を1台動かすたびに盤全体の可能性が組み替わる感覚こそ、この小さな箱の手応えだった。

前後にしか動けない駒たちのイメージ（イメージ・AI生成）

現代への系譜 — 証明と、Steamでの二度目の発売

この「1台を動かすたび全体が組み替わる」という性質は、遊びの外でも注目された。2002年、計算機科学者のJeffrey FlakeとEric Baumは論文「Rush Hour is PSPACE-complete, or “Why you should generously tip parking lot attendants”」を専門誌Theoretical Computer Scienceに発表。盤の大きさを自由にした一般化Rush Hourで「この配置は解けるか」を判定する問題が、PSPACE完全であることを証明した。

PSPACE完全とは、今知られているどんなアルゴリズムを使っても、盤が大きくなるほど解を見つける手間が爆発的に増えることが理論的に保証されているクラスを指す。赤い車を出すだけの素朴な遊びが、計算機科学でもっとも手強い問題群の一員だと証明されたのである。

研究はここで終わらなかった。2020年に発表された論文「1×1 Rush Hour with Fixed Blocks is PSPACE-complete」(Brunner・Chungら、2021年の国際会議FUNで発表)は、駒をすべて1マスに縮めた簡略版ですら同じ結果が成り立つことを示した。1996年の木箱パズルは、四半世紀を経てなお計算複雑性研究の現役の題材であり続けている。

遊びとしてのRush Hourも姿を変え続けた。1998年には鉄道版「Railroad Rush Hour」、2009年にはアプリ版が登場する。そして2022年、ドイツのMarkt+Technik社がThinkFun(Ravensburger)の公式ライセンスのもとデジタル版「Rush Hour Deluxe」をSteamで発売した。60種のチャレンジと最大4人のローカル対戦を備え、木箱として生まれたパズルの規則が、そのままSteamのライブラリに並んでいる。

木の駒から画素の盤への系譜のイメージ（イメージ・AI生成）

参考文献

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

・Wikipedia: Rush Hour (puzzle)

・Wikipedia: Nob Yoshigahara

・ThinkFun: The Evolution of ThinkFun's Rush Hour

・Brandeis University (Storer): Rush Hour's Creation — The Dramatic Story of Rush Hour's Birth

・Flake & Baum, "Rush Hour is PSPACE-complete, or Why you should generously tip parking lot attendants" (2002)

・arXiv: 1×1 Rush Hour with Fixed Blocks is PSPACE-complete (Brunner, Chung, et al., 2020)

・Steam: Rush Hour® Deluxe — The ultimate traffic jam game!

おわりに — 芦ヶ原伸之が遺したもの

芦ヶ原伸之は2004年、68歳でこの世を去った。彼が世に送り出したパズルは数多いが、赤い車を渋滞から出すためだけの、6×6の盤ほど長く生き続けているものは少ない。

歴史がこの一台の盤から教えてくれるのは、遊びの単純さと難しさは反比例しない、ということだ。動かせる向きをひとつに絞るという、たったひとつの制約だけで、盤面は解を探すのに数十年分の数学者の仕事を要するほど広がる。

出口を抜けていく一台のイメージ（イメージ・AI生成）