Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with puzzles:
TR14-116 | 6th September 2014
Rahul Mehta

2048 is (PSPACE) Hard, but Sometimes Easy

We prove that a variant of 2048, a popular online puzzle game, is PSPACE-Complete. Our hardness result
holds for a version of the problem where the player has oracle access to the computer player's moves.
Specifically, we show that for an $n \times n$ game board $G$, computing a
more >>>

ISSN 1433-8092 | Imprint