Thursday, March 27, 2014

2048 is in NP

(This post assumes some familiarity with the game.)

Turning interactive games into pen/paper puzzles

In computer science, \(NP\) is the collection of all the types of pen/paper puzzles whose solutions are easy to double-check (but not necessarily easy to find). These span a wide range of difficulties, from mazes to Sudoku to who owns the zebra?-style logic puzzles.

(Formally, \(NP\) is the set of decision problems for which yes answers can be verified in polynomial time.)

Of course, 2048 is a Category 1 life-threatening memetic contagion video game, not a pen/paper puzzle. So we're going to need to do a little bit of massaging to talk about it as if it was.

That's where Tetris comes in.

Chen, C. Rectangular grids and puzzle game addiction: a journey into the collective human subconscious. Dissertation. Published Jun 2048.