31
$\begingroup$

There are many proofs lying around that games like Lemmings or Sudoku or Tetris are NP-hard (generalized version of those games, of course). The proofs, as I recall, are not difficult but not simple either.

I wish to give my students a question in their homework assignment which tackles some known game or something similar, so I'm interested in examples to such problem for which the proof of hardness is not hard (at least, the student can solve it with some direction).

  • 0
    Only semi-serious: I figure that "read Ian Stewart's [Million Dollar Minesweeper](http://www.sciamdigital.com/index.cfm?fa=Products.ViewIssuePreview&ARTICLEID_CHAR=419729DA-943E-4A29-A584-87FC20CC910)" would not be acceptable (even if quite profitable) as an assignment... However, I think that you could make an assignment out of that article, but probably the effort you'd need to invest for making it "do-able" for your students is quite high.2011-05-17
  • 0
    There is nice variation on minesweeper which is NP-complete and described in Sipser's book; it is already in the HW... :-)2011-05-17
  • 0
    Naturally, you can think of the Game of Go. There are many articles on this topic. In particular, you can concentrate only on parts of the game: for example, determining the winner after 150 moves or so, or whether a ladder works are more than NP-complete. Actually there are known to be PSPACE-complete if I remember it well.2011-05-17
  • 0
    There are indeed many two-player games that are PSPACE-complete, a very common example being Generalized Geography (also shown in Sipser). But this is already "too hard", since PSPACE-completeness is not a topic covered by the homework.2011-05-17
  • 2
    @Gadi: could you give us an example of a problem/proof of appropriate difficulty? This will help narrow the search.2011-05-18
  • 0
    The Minesweeper problem presented at Sipser is my role model; you are given a graph with natural numbers on some of the vertices, and question is whether you can add mines to some of the non-numbered vertices in such a way that every numbered vertex is connected exactly to that number of mines (Vertex Cover can be reduced to this problem with a little trick).2011-05-18
  • 0
    @Gadi A: http://xkcd.com/287/2011-05-20
  • 0
    Gadi: actually, AFAICT 'core' Sudoku's NP-completeness (i.e., given a partially-filled grid, answering the question 'is there a solution for this grid?') is still an open problem; all the references for Sudoku I've seen point to the 'find a second solution' problem. I would consider looking for a Tetris-style problem, maybe some version of bin-packing; reductions in those cases aren't necessarily easy to _find_, but they should be easy to _prove_.2011-05-20
  • 0
    Eric: This comics appears in one of our homeworks and indeed, we give as question based on it :-)2011-05-20

6 Answers 6

8
  • The SameGame (random arrangement of colored blocks; clicking on a block removes the group of connected blocks of the same color and then the blocks above fall down to fill the void) is NP-Complete for instances as small as 3 colors and 5 columns. The reduction from 3-SAT isn't incredibly straightforward, though.
  • The problem of deciding if a partially filled Latin square can be completed is also NP-complete (Latin squares are a generalization of Sudoku), however, the reduction used to prove this isn't very straightforward.
  • Battleship (which is similar to Minesweeper and Sipser's problem from Michaël's answer) is NP-Complete, but the reduction from 3-SAT is likewise complicated.
  • I don't know if you would consider it "real life", but exact inference in Bayesian networks is NP-Hard; it's a straightforward reduction from 3-SAT (I guess one could argue that Bayesian inference is used in the playing of many games).
  • There are also all sorts of vehicle routing and depot location problems that are very easy to conceptualize that have relatively straightforward reductions from TSP.

Edit:

  • Scheduling with profits and deadlines is NP-Complete. The decision version goes something like,

    Let $A$ be a set of $n$ tasks, $\{a_1, \ldots, a_n\}$, each with an associated execution time, $t_i$, profit, $p_i$, and deadline, $d_i$. You can only execute one task at a time; if the task does not complete before its associated deadline, then you do not receive its profit. Does there exist a schedule that returns a profit of $k$?

It's relatively easy to show, e.g., Hamiltonian cycle $\leq_P$ scheduling with profits and deadlines.

4

Sipser gives two such problems in the exercice section of the NP-completeness chapter on his book. The first one is inspired from Minesweeper, as one comment proposed:

Let $G$ be an undirected graph, where each node either contains a single, hidden mine or is empty. The player chooses nodes, one by one. If the player chooses a node containing a mine, the player loses. If the player chooses an empty node, the player learns the number of neighboring nodes containing mines. (A neighboring node is one connected to the chosen node by an edge.). The player wins if and when all empty nodes have been so chosen. In the mine consistency problem you are given a graph $G$, along with numbers labeling some of $G$'s nodes. You must determine whether a placement of mines on the remaining nodes is possible, so that any node $v$ that is labeled $m$ has exactly $m$ neighboring nodes containing mines. Formulate this problem as a language and show that it is NP-complete.

The other one is a solitaire game:

You are given an $m \times m$ board. On each of its $m^2$ positions lies either a blue stone, a red stone, or nothing at all. You play by removing stones from the board so that each column contains only stones of a single color and each row contains at least one stone. You win if you achieve this objective. Winning may or may not be possible, depending upon the initial configuration. Let SOLITAIRE $= \{\langle G\rangle \;|\; G \mbox{ is a winnable game configuration}\}$. Prove that SOLITAIRE is NP-complete.

  • 0
    Thank you. I'm familiar with those examples (I'm the one that gave the Minesweeper one in the comments...) but this is still better than nothing...2011-05-23
4

I had a math class where we had to solve the rubiks cube: http://web.mit.edu/sp.268/www/rubik.pdf (this isn't from my specific class but it was similar)

  • 0
    The rubik's cube is solved easily, I don't think it is NP-complete.2011-05-25
  • 0
    Eric: You might be surprised! Optimal solutions (or even 'can this position be solved in k moves or fewer?' queries) are known to be hard for a lot of similar problems, and for permutation groups in general; see, for instance, http://3dpancakes.typepad.com/ernie/2010/06/complexity-of-rubiks-cube.html ...2011-05-25
  • 6
    The problem of whether optimally solving the nxnxn Rubik's cube is NP-Hard or not is open: http://cstheory.stackexchange.com/questions/783/is-optimally-solving-the-nnn-rubiks-cube-np-hard. I guess if you have a student named Dantzig it might be a good idea to give as homework :-)2011-05-25
2

Sokoban!!! It is NP-hard and P-SPACE complete.

1

A somewhat recent paper proves in what I think is a relatively straightforward way that Super Mario Brothers is NP-complete (along with NP-hardness of many other classic Nintendo games). See http://jeremykun.wordpress.com/2012/03/22/nintendo-np-hard/ for a highlight and the linked paper for more details.

Your assignment could either be for them to design the gadgets for the game of their choice, or for them to combine the gadgets together to prove NP-hardness.

1

I can recommand the book Puzzles, Games, and Computations by Erik Demaine and Robert Hearn. It contains lots of results. Most are obtained by expressing games like Sokoban in the non-deterministic costraint logic model (NCL). This computation model is equivalent to a space-bounded turing machine. Since NCL is PSPACE-complete, it suffices to model NCL with the games. This results in not-so-tricky gadgets.