山下（Seamless）
2014年から幅広い分野の研究論文をピックアップして解説しているメディア「Seamless」を個人運営。 X（@shiropen2）でも更新情報を発信中。
米MIT Hardness Groupに所属する研究者らが発表した論文「Tetris is Hard with Just One Piece Type」は、降ってくるブロックが1種類に制限された『テトリス』の計算複雑性を分析した研究報告である。
ほとんどのミノで「NP困難」
テトリスは7種のテトロミノ（テトリミノ、I・J・L・O・S・T・Z）で構成されるパズルゲームだが、コンピュータサイエンスにおける計算複雑性の研究対象としても扱われる。この種の研究では、初期の盤面状態とこれから落ちてくるピースの順番がすべてわかっている状況を前提とし、与えられたブロックで盤面を消去しきれるかという「クリア」や、ゲームオーバーを回避できるかという「生存」の判定が可能かどうか、が焦点となる。
もしテトリスでI型ブロック1種類しか出現しない場合、その問題は多項式時間で解ける、すなわちコンピュータで効率的に解を出せると23年間にわたって予想されていた。
しかし今回の研究では、Oブロック（2×2の正方形）を除くテトロミノのブロック1種類だけの場合、テトリスのクリアと生存の判定は計算論的に極めて難解な「NP困難」であることを証明し、この長年の予想を覆したとしている。
ブロック回転時の「壁蹴り」処理がくせ者に
I型ブロックだけが降ってくるなら、ただ消していけばよさそうに見えるが、計算複雑性の観点から想定する初期盤面は空の盤面ではなく、解きたい論理パズルを盤面の形に変換した、ブロックが入り組んだ特殊な初期盤面であるため難しくなっている。
さらにこの難しさを生み出している原因は、現代のテトリスに採用されている「スーパーローテーションシステム」（SRS）という回転ルールにある。SRSでは、ピースが回転しようとして壁や他のブロックにぶつかった際、システムが代わりの位置を順にテストして回転を成立させる「壁蹴り」（Wall Kick）という処理が行われる。
この仕様により、ブロックが特定の階段状の地形を登ったり、複雑な隙間に入り込んだりすることが可能になり、手順の組み合わせが増加する。
また、すべてのピースが同じ種類であるため、現代のテトリスにあるブロックを保留するホールド機能を使ったとしても、配置されるブロックの順序が変わらないため問題の難易度には影響を与えないという。
さらにこの研究では、実際のゲームで使われる、7種類のテトロミノを必ず1個ずつ含む7個1組のグループが順次供給される方式「7-bag」の条件下であっても、クリアがNP困難であることを示した。
一方で、特定の条件下ではテトリスが解けるケースも証明されたとしている。例えば、ブロック2つからなる2マスドミノ（1×2の長方形）において、特定の回転ルールを仮定した場合は、多項式時間で解くアルゴリズムが存在するという。
また、長さがkの直線状のブロックを使用する場合において、盤面の一番上からk-1行分が空いていれば、生存とクリアを判定できることもわかったと論文は示している。つまり、I型ブロック（1×4の長方形）を用いる場合、NP困難となるには、盤面の上部3行にあらかじめブロックが配置されている初期状態が必要ということである。
Source and Image Credits: MIT Hardness Group, M. H., Brunner, J., Demaine, E. D., Hendrickson, D., & Li, J. (2026). Tetris is Hard with Just One Piece Type. arXiv preprint arXiv:2603.09958.
