32
$\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).

$\endgroup$
9
  • $\begingroup$ Only semi-serious: I figure that "read Ian Stewart's Million Dollar Minesweeper" 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. $\endgroup$
    – t.b.
    May 17, 2011 at 8:49
  • $\begingroup$ There is nice variation on minesweeper which is NP-complete and described in Sipser's book; it is already in the HW... :-) $\endgroup$
    – Gadi A
    May 17, 2011 at 11:09
  • $\begingroup$ 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. $\endgroup$
    – Thomas Connor
    May 17, 2011 at 11:39
  • $\begingroup$ 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. $\endgroup$
    – Gadi A
    May 17, 2011 at 12:39
  • 2
    $\begingroup$ @Gadi: could you give us an example of a problem/proof of appropriate difficulty? This will help narrow the search. $\endgroup$
    – ShyPerson
    May 18, 2011 at 17:27

6 Answers 6

Reset to default
8
+50
$\begingroup$
  • 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.

$\endgroup$
1
  • $\begingroup$ You should make separate answers, such that it is possible to up- or downvote them separately. $\endgroup$
    – azimut
    Nov 14, 2021 at 10:33
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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... $\endgroup$
    – Gadi A
    May 23, 2011 at 18:36
4
$\begingroup$

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)

$\endgroup$
3
  • $\begingroup$ The rubik's cube is solved easily, I don't think it is NP-complete. $\endgroup$
    – Eric Naslund
    May 25, 2011 at 0:16
  • $\begingroup$ 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, 3dpancakes.typepad.com/ernie/2010/06/… ... $\endgroup$
    – Steven Stadnicki
    May 25, 2011 at 0:20
  • 6
    $\begingroup$ The problem of whether optimally solving the nxnxn Rubik's cube is NP-Hard or not is open: cstheory.stackexchange.com/questions/783/…. I guess if you have a student named Dantzig it might be a good idea to give as homework :-) $\endgroup$
    – Aryabhata
    May 25, 2011 at 1:37
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .