Games Are Hard

Also known as Complexity of Games and Puzzles. Original title was NP-completeness.

I love puzzles and games so much. I also enjoy theoretical computer science. Of course this had to be done. Here’s a list of everything I’ve found. This page will (hopefully) be updated every time I get a new thing. Contributions welcome.

Notes

  • In a conversation with Sebastian Schoener, I realized that there is a difference between satisfiability/consistency problems and uniqueness/soundness problems. For certain games/puzzles, there are two questions that make sense: whether a given instance of a puzzle has at least one solution (it is satisfiable/consistent), and whether it has at most one solution (it is sound). We can generalize the soundness problem: given an instance of a partially-solved puzzle, whether there exists “anything” that can be deduced (the contents of a cell, etc).

    Soundness matters. For example, if you’re stuck in Minesweeper (it allows no progress; nothing can be deduced), you must guess, which is obviously bad. Likewise, if you’re doing a puzzle competition, and you can’t deduce anything, it means the puzzle has multiple solutions, and so you must guess the solution intended by the author, which is also bad.

    In most cases, the more natural problem is satisfiability/consistency; we’re concerned whether there exists at least one solution. However, there are some specific cases in which the soundness problem is more natural instead, for example Minesweeper. I’ve marked (hopefully) everything where consistency and soundness can matter with whether they are about consistency or about soundness.

  • This that states several papers showing that Country Road, Ripple Effect, Shikaku, and Yajilin are NP-complete. Anyone knows whether the papers are available online?

Last updated 06-Jun-2016

Puzzles and games that are proven to be in some class, along with what reduces to them…

NP-complete

  • Akari (satisfiability) from 3-SAT
  • Battleships (satisfiability) from 3-SAT, from bin packing
  • Bejeweled (whether a given gem can be popped) from 1-in-3 SAT
  • Corral (satisfiability) from 3-colorability of planar graphs
  • Cryptarithms (Verbal Arithmetic) (satisfiability) from 3-SAT
  • Fillomino (satisfiability) from 3-SAT
  • Galaxies (satisfiability) from 3-SAT
  • Hashi(wokakero) (satisfiability) from existence of Hamiltonian circuits in unit-distance graphs
  • Heyawake (satisfiability) from 3-SAT
  • Kakuro (satisfiability) from 3-SAT
  • KenKen (TomTom) (satisfiability) from Latin Square
  • Kurodoko (satisfiability) from 3-SAT
  • Latin Square (satisfiability) from triangulation of tripartite graphs
  • Lemmings (satisfiability) from 3-SAT
  • Mastermind (satisfiability) from vertex cover
  • Masyu (satisfiability) from existence of Hamiltonian circuits in cubic graphs
  • Minesweeper (satisfiability) from 3-SAT
  • Nonogram (satisfiability) from Nondeterministic Constraint Logic
  • Nurikabe (satisfiability) from 3-SAT
  • Patterna (satisfiability) from 3-SAT
  • Ripple Effect (satisfiability) from 3-SAT, Latin Square
  • Slitherlink (satisfiability) from existence of Hamiltonian circuits in cubic graphs
  • Solitaire Chess (satisfiability) from 3-SAT
  • Sudoku (satisfiability) from Latin Square
  • Super Mario Bros (whether one can reach a target point) from 3-SAT
  • Tetris (whether one can survive over a known finite sequence of pieces) from 3-partition
  • TrackMania (whether one can finish the lap) from 3-SAT
  • Zen Puzzle Garden (satisfiability) from existence of Hamiltonian circuits in cubic graphs

coNP-complete

NP-hard

PSPACE-complete

  • 2048 (reaching target configuration) from Nondeterministic Constraint Logic
  • Bloxorz from Nondeterministic Constraint Logic
  • Sokoban from simulating linear bounded automata

PSPACE-hard

  • Pokémon (whether one can reach a target point) from Sokoban

Undecidable

  • Braid (whether one can reach a target point) from simulating counter machine
Advertisements

8 thoughts on “Games Are Hard

  1. Pingback: NP-Complete Games and Puzzles | Chaos at the Sky

    • @Braid: Woah.

      @Other complexity: If I find a large enough collection of results, I might consider that. However, NP-complete is arguably the second most common complexity categorization (after P), so I focus more on NP-complete.

      Reply
  2. Solitaire Chess is NP-complete: http://arxiv.org/pdf/1501.06398v1.pdf

    Bloxorz is PSPACE-complete: http://arxiv.org/pdf/1411.5951.pdf

    Trackmania is NP-complete: http://arxiv.org/pdf/1411.5765.pdf

    2048 is PSPACE-hard: http://arxiv.org/pdf/1408.6315.pdf

    Game About Squares is NP-hard: http://arxiv.org/pdf/1408.3645.pdf

    Mastermind is NP-complete: http://arxiv.org/pdf/cs/0512049v1.pdf

    Hashiwokakero is NP-complete: http://users-cs.au.dk/koda/thesis.pdf#page=111

    Zen Puzzle Garden is NP-complete (and probably Right Way Robot and Ice Barn by similar constructions): http://www.sciencedirect.com/science/article/pii/S0020019011002870

    Reply
  3. I would like to comment on the fact that I myself did not bring up the difference between soundness and consistency; this is merely an interpretation of my words.
    My original comment criticized the idea that playing Minesweeper (or similar games such as my own Patterna, or the fabulous HexCells) is a process of solving an NP-complete problem. The original proof for NP-completeness of Minesweeper concerns the Minesweeper Consistency Problem (which is also how it was listed on this page), which asks whether there is a way to place mines on the board that is consistent with the information given on the Minesweeper board. To me, this is not a question of whether there is *a solution* to the board (and thus a question of consistency), since the vast majority of these assignments will lead to you loosing the game. If you are asking whether a level is solvable, you are asking whether there is a way to uncover the (necessarily) unique solution by using a sound logical argument, i.e., a proof. Thus the solution of a Minesweeper board must be a consistent assignment together with a proof that this is the only assignment that makes it work. In this perspective, a Minesweeper level is more appropriately specified as a grid with all information given (i.e., you already know where the mines are to begin with) and a set of cells that are initially revealed to the actual player of the game. The question then is whether the player can deduce the position of all mines on the board. This seems more appropriate since it better models the actual playing of the game and is close to the way that Minesweeper levels are stored in memory. In theory, there could of course also be a variant of Minesweeper where there are no mines to begin with, but only hints about where mines should be. Then your job would be to place mines in such a way that is fulfills are the constraints given by the hints — and *this problem* is NP-complete. (Call this problem Minelayer, instead of Minesweeper.) You can read the article about Patterna linked above in the list to read about my point in more detail.

    I would also like to address the question of uniqueness of solutions in this context. The prototypical NP-complete problem is SAT – that is, given a formula, is it satisfiable? There is a variant of this problem, called UniqueSAT, which reads as “given a formula, is there exactly one satisfying assignment of the variables”? (Not to be confused with UnambiguousSAT, which asks whether a formula that is guaranteed to have at most one satisfying assignment is actually satisfiable.) While SAT is NP-complete, UniqueSAT is not. In fact, it is coNP-hard and in DP (but only DP-complete under deterministic polytime reductions if coNP=NP [it is DP-complete under randomized reductions]). It is currently not known whether UniqueSAT is in coNP. I would guess that something similar is true for the uniqueness variant of the Minesweeper Consistency Problem.

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s