Simple "real life" NP-hard problems?

Question

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).

Answer 1

• 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.

Answer 2

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.

Answer 3

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)

Answer 4

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

Answer 5

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.

Answer 6

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.