2048 NP-Complete or PSPACE? What the Complexity Proofs Say

Is 2048 NP-complete, or PSPACE-complete? Neither label fits the game you play, but both come close for a stretched version of it. A 2014 paper proves a variant of 2048 PSPACE-complete on an n by n board, and a 2015 paper proves a generalized 2048 NP-hard. This post explains what each proof covers, what "2048 np-complete" searches usually mix up, and what any of it means when you plan your next slide.

If you want a board to try these ideas on, Evolved 2048 puts the 2048 puzzle on a cube with 54 squares, where every extra move you can make turns planning into a bigger search.

Is 2048 NP-complete? The short answer

Complexity results never label a game by itself. They label a question about a family of boards that can grow without limit. The two papers on arXiv ask different questions, so they reach different classes.

• Rahul Mehta, 2014: "2048 is (PSPACE) Hard, but Sometimes Easy". On an n by n board, finding a sequence of moves that takes one position to a given position is PSPACE-complete, in a version where the player can see the computer player's moves.
• Ahmed Abdelkader, Aditya Acharya and Philip Dasler, 2015: "On the Complexity of Slide-and-Merge Games". Natural yes or no questions on a generalized 2048 are NP-hard, shown by a reduction from 3SAT.

So the honest answer is: NP-hard for a generalized board, PSPACE-complete for one variant, and no proof in either abstract that calls 2048 NP-complete. You can read both abstracts yourself: Mehta's paper on arXiv and the slide-and-merge paper on arXiv.

Why researchers stretch the board first

A 4 by 4 board has a fixed, finite number of positions. In principle a big enough table could hold the answer to every question about it, so on paper it is a fixed amount of work. Complexity theory asks how the work grows as the input grows, so a fixed board tells it nothing.

That is why both papers study a board of any size. Mehta works on an n by n board. The 2015 paper works on "a suitable generalization" of the game. The rules stay the same: slide every row or column one way, and pairs of equal tiles merge into one tile with their sum. Only the board grows.

Keep this in mind when you see a headline. "2048 is NP-hard" is a claim about that growing family. It is not a claim that the 2048 tile on your phone is out of reach.

NP, NP-hard and PSPACE in plain words

NP is about checking. If someone hands you a proposed answer, you can check it quickly, even if finding it could take a very long time. NP-hard means at least as hard as every problem in NP. NP-complete means NP-hard and also inside NP. The 2015 paper proves the first part, hardness.

PSPACE is about problems you can solve with a reasonable amount of memory, even if they take a very long time. It includes NP, and it is where questions about long chains of choices usually sit. PSPACE-complete means a problem is one of the hardest in that class and inside it. That is what Mehta proves for his variant.

Evolved 2048 has a small, everyday case of "checking is easy". For ranked games, the game says: "Every ranked game is checked: the server replays its moves with the game's rules and works out the score itself." Replaying a finished game is quick. Finding a great game to replay is the hard part.

What each paper asks and proves, from its arXiv abstract.

What the 2014 PSPACE proof covers

Mehta's hardness result needs one assumption that the real game does not give you: the player knows the computer player's moves, the new tiles, in advance. Under that assumption, the question is whether some sequence of moves takes the board from a starting position to a particular target position. The proof is a reduction from Nondeterministic Constraint Logic.

The same paper has a "sometimes easy" half. Asking whether a fixed list of k moves, each up, down, left or right, wins on an n by n board is fixed-parameter tractable. The abstract gives an algorithm that runs in O(4k n2) time: try every list of k slides, and replay each one on the board.

The 4k part is the useful bit for a player. It counts the lists of slides you would need to try:

• 3 slides ahead: 4 × 4 × 4 = 64 lists.
• 5 slides ahead: 1,024 lists.
• 10 slides ahead: 1,048,576 lists.

The work grows fast with how far ahead you look, but only gently with the size of the board.

What the 2015 NP-hardness proof covers

Abdelkader, Acharya and Dasler describe 2048 as a "slide and merge" game: it mixes pushing blocks with matching tiles. They define natural decision problems on a generalized board and prove 2048 NP-hard by a reduction from 3SAT, a classic logic problem known to be hard.

A reduction works like a translation. You take any 3SAT problem and build a 2048 board from it, so that the target can be reached exactly when the logic problem has a solution. If anyone found a fast way to answer the 2048 question, it would answer every 3SAT problem fast too, which nobody expects.

Being NP-hard does not make a problem PSPACE-complete, and the two results do not contradict each other. They ask different questions about different stretched versions of the game.

Where random tiles fit

The game you actually play has neither a list of tiles you can read nor an opponent who picks them. It has random numbers. In Evolved 2048, each new tile takes two numbers from a seeded random number generator: one picks an empty square of the front face, and one picks the value, a 2 when the number is under 0.9 and a 4 otherwise. The same seed gives the same tiles.

So the game sits between the two models. If you could read the seed, every game would become the "known tiles" puzzle of Mehta's proof. You cannot, so each slide is a bet on tiles you have not seen yet.

Your own choices still count for a lot. In one test from the same start, slides only on the front face, the order Down, Left, Right, Up got stuck at move 32 with a score of 180. Played Up, Right, Down, Left instead, the same start got stuck at move 28 with 160. That is one game each, not an average, but it shows how much the order matters. More on that balance is in is 2048 luck or skill.

A worked example: count your choices on the cube

The 4k count assumes four slides. Evolved 2048 gives you more moves than that, and each one widens the search the papers describe. Try this once on the cube:

1. Start a game and make two slides. Note the Moves counter.
2. Press Shift and Left. The whole cube turns and Moves does not change: in the game's words, "Turning is free." A turn is a free look, not a choice that adds a tile.
3. Before your next slide, count your real options: four slides, plus each twist that would carry tiles round. A twist counts one move and adds a new tile, just like a slide.
4. Pick three slides ahead and play them. Then ask how many of the 64 slide lists you actually weighed. Most players weigh two or three.

That gap is why players rely on habits, not search. A player who only slid filled the front face at move 46 in one scripted test, with a score of 332. A second scripted test that also twisted whenever the front was stuck made a 128 tile at move 118. The extra moves help, but only if you pick well among more options. Our 2048 AI strategy post covers how computer players score a board to cut that search down.

Frequently asked questions

Has 2048 been proven NP-complete?

Not in the abstracts of the two arXiv papers on it. The 2015 paper proves a generalized 2048 NP-hard, and the 2014 paper proves a variant PSPACE-complete.

Does NP-hard mean the 2048 tile is impossible to reach?

No. NP-hard describes how the work grows on ever larger boards. It says nothing about whether you can make 2048 on a small one.

Why does the 2014 paper say "sometimes easy"?

Checking whether a fixed list of k slides wins can be done in O(4k n2) time. For a short list that is quick, even on a big board.

Is there a complexity result for 2048 on a cube?

Neither paper studies a cube. Treat the cube's extra twists as more options to weigh, not as a solved case.

Get started

You do not need a proof to feel the difference between a planned line and a lucky one. Count your options before a slide, use free turns to look around the cube, and see how far a plan gets you. Playing needs no account, and your game, best score and settings are saved on your device. For how ranked games get replayed and checked, see the 2048 leaderboard post.

Play Evolved 2048: it is free and plays in your browser on a computer or a phone.