WW (pp. 218-219; see references below) is disparaging of this sort of result, writing that "this asymptotic result says little about the difficulties of calculating good strategies", describing NP-hard game positions as "degenerate" and "relatively dull", and advocating (as a response to hardness proofs) looking for additional rules and conditions that would make the game easier. But to me NP-completeness is not the end but the beginning of the study of a game: it shows that the game is complex enough that we can encode interesting computational problems within it. If a game is in P, it becomes no fun once you learn "the trick" to perfect play, but hardness results imply that there is no such trick to learn: the game is inexhaustible. And of course NP-completeness or PSPACE-completeness doesn't even rule out the possibility of computing game values exactly; true, it seems to imply that worst-case-exponential algorithms are required, but there is still plenty of interesting work in designing, analyzing, and implementing such algorithms.
There is a curious relationship between computational difficulty and puzzle quality. To me, the best puzzles are NP-complete (although some good puzzles are in P, relying on gaps in human intuition rather than on computational complexity for their difficulty). Some puzzles are even harder than NP (for instance, sliding block puzzles and Sokoban are PSPACE-complete) but to me this means only that the problem can have an annoyingly long sequence of manipulations in its solution. For two-player games, one encounters a similar phenomenon at a higher level of complexity. The tree of potential interactions in a game typically gives rise to PSPACE-completeness results of a sort I find more interesting than PSPACE-completeness in puzzles. However some games are harder, EXPTIME-complete, which to me means that it may sometimes be necessary for a well-played game to go on for a tediously long sequence of moves. Perhaps some games or puzzles in which the players start with incomplete knowledge of the game or puzzle configuration might lead to other types of completeness (e.g. MA-completeness or #P-completeness) for finding the starting move most likely to succeed, but I know of no such results.
I primarily list here real games and puzzles, games that were invented to be played, rather than to be analyzed. So I'm not including some of the more artificial entries in e.g. WW or GJ, such as "sequential truth assignment". If someone can point me to a tournament for these games, a copy of the game sold in stores, or a program for people to play them against their computers, I'll consider adding them.
One caveat: NP-completeness is not a concept that applies to a single puzzle or game position, or even a finite collection of positions. It only makes sense to talk about an infinite family of problems as being NP-complete. For this reason games like chess cannot themselves be NP-complete, as they only have a finite (albeit unthinkably large) number of possible positions. In many cases however there is a natural generalization from some finite game or puzzle to an infinite family of game positions on arbitrarily large game boards, in which it makes sense to talk about NP-completeness. The fact that these infinite generalizations are computationally hard gives us some justification for believing that the original finite games are also hard in some less well-defined sense.
Puzzles and solitaire games: Alphametics; Clickomania; Cryptarithms; Cubic; 15-puzzle; Instant Insanity; KPlumber; Mah Jongg; Pearl puzzles; Rush Hour; Shanghai; Sokoban
Two-player games: Amazons; Bridge-It; Checkers; Chess; Dots and boxes; Draughts; Go; Hex; Mastermind; Othello; Phutball; Reversi; Shannon switching game; Twixt
Description: Players move queens on an n*n board, as part of each move shooting an arrow from the moved piece. Arrows move like a chess queen when shot but are immovable afterwards. The arrows eventually block the movement of the queens; the last player to complete a move wins. Game-play combines go-like goals of surrounding territory with chess-like tactics of blocking opposing pieces' lines of play. The most commonly used starting configuration involves four queens of each color placed around the edges of a 10*10 board.
Status: PSPACE-complete. Endgames in which pieces of opposing colors are separated from each other are NP-hard.
- M. Buro, Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs, Proc. 2nd Int. Conf. Computers and Games, 2000.
- R. A. Hearn, Amazons is PSPACE-complete, cs.CC/0502013.
Description: Players move pieces diagonally forward one square at a time on alternating squares of an n*n board, removing the other players' pieces by jumping diagonally over them. Object is to leave opponent with no move by blocking or jumping all pieces. The 8*8 version is called checkers, but on larger boards it is called draughts.
- GJ 256 [GP10].
- A. S. Fraenkel, M. R. Garey, D. S. Johnson, T. Schaefer, and Y. Yesha, The complexity of checkers on an N*N board - preliminary report, Proc. 19th IEEE Symp. Found. Comp. Sci. (1978) 55-64.
- J. M. Robson. N by N checkers is Exptime complete. SIAM Journal on Computing, 13(2):252-267, May 1984.
Description: This game is both too complicated and too well-known to describe here in detail, but the basic idea is to move pieces around an 8*8 board, capturing one's opponents' pieces, until the game is ended either by checkmate (one player winning by forcing the capture of the opposing player's king) or by various kinds of draws.
Status: This is a finite game, but generalizations to n*n boards are EXPTIME-complete.
- A. S. Fraenkel and D. Lichtenstein, Computing a perfect strategy for n*n chess requires time exponential in n, Proc. 8th Int. Coll. Automata, Languages, and Programming, Springer LNCS 115 (1981) 278-293 and J. Comb. Th. A 31 (1981) 199-214.
Description: In these puzzles, also known as alphametics, a sequence of letters is arranged in the form of an arithmetic problem, a famous example beingSEND +MORE ----- MONEYThe problem is to construct a 1-1 mapping from letters to digits that makes the arithmetic work out correctly.
Status: This is a finite problem, but generalizations to bases other than decimal are NP-complete.
- D. Eppstein, On the NP-completeness of cryptarithms, SIGACT News 18(3) (1987) 38-40.
Description: This childhood game is played with pencil and paper, starting from a drawing of a rectangular lattice of dots. The players alternately connect adjacent dots with line segments; if a player forms a four-segment square he or she scores a point and gets another move.
Status: WW describes a generalized version of the game that is NP-hard, by a reduction from finding many vertex-disjoint cycles in graphs. The same result would seem to apply as well to positions from the actual game, by specializing their reduction to trivalent planar graphs. (This is very closely related to, but not quite the same as, maximum independent sets in maximal planar graphs.)
- WW, chapter 16. E. Berlekamp, The Dots and Boxes Game: Sophisticated Child's Play, A. K. Peters, 2000.
Description: Something of a cross between Sokoban and Same Game, this puzzle involves pushing blocks left or right in a polygonal region, where they are subject to a gravity that pulls them downward whenever possible. Blocks have colors, and when multiple blocks of the same color become adjacent, they vanish. The goal is to eliminate all blocks.
Status: Friedman claims to prove that Cubic is NP-complete. His reduction clearly shows that it is NP-hard, but it is less obvious to me that it is in NP.
- E. Friedman, Cubic is NP-complete, Proc. Florida MAA Section Meeting, 2001.
Description: 15 of the 16 positions in a 4*4 matrix are filled by tiles, leaving one unfilled hole. Tiles adjoining the hole can be shifted into the hole, the object being to form some particular permutation of the tiles (typically forming a picture out of fragments printed on the tiles).
Status: this is a finite problem, but can easily be generalized to n*n matrices. Testing whether a solution exists is in P but finding the solution with the fewest moves is NP-complete.
- D. Ratner and M. Warmuth, Finding a shortest solution for the N*N-extension of the 15-puzzle is intractable, J. Symb. Comp. 10 (1990) 111-137.
Description: This ancient game is played by placing stones on a 19*19 board. When a group of stones of one color is completely surrounded by stones of the other color, the surrounded group is removed from the board. The object is to control empty squares by surrounding them; after both players are unwilling to continue play, these squares are counted and the scores adjusted by the numbers of stones that had been removed.
Status: This is a finite game, but can be generalized to n*n boards. Even without ko (special rules related to repetition of positions) the game is PSPACE-hard; with ko (Japanese rules) it is EXPTIME-complete. It is apparently still open whether Chinese or US rules Go is EXPTIME-complete. Even certain "simple" endgames in which the go board has been decomposed into many small independent regions of play are PSPACE-hard.
- GJ 257 [GP11].
- D. Lichtenstein and M. Sipser, Go is polynomial-space hard, J. ACM 27 (1980) 393-401.
- J. M. Robson, The complexity of Go, Proc. IFIP (1983) 413-417.
- J. M. Robson. Combinatorial games with exponential space complete decision problems. Proc. Mathematical Foundations of Computer Science, Springer-Verlag, LNCS 176, 1984, pp. 498-506.
- E. Berlekamp and D. Wolfe, Mathematical Go: Chilling Gets the Last Point, A. K. Peters, 1994.
- D. Wolfe, Go endgames are hard, MSRI Combinatorial Game Theory Research Worksh., 2000.
- M. Crâşmaru and J. Tromp, Ladders are PSPACE-complete, Proc. 2nd Int. Conf. Computers and Games, Springer-Verlag, 2000, pp. 241-249.
Description: players take turns placing pieces on a diamond-shaped board composed of hexagonal tiles. Each player owns two opposite sides of the board, and aims to connect those sides by a contiguous path of pieces.
Status: First player wins by a strategy-stealing argument but PSPACE-complete in general. The "Shannon switching game" in which pieces are placed on edges (known on the square grid as "Gale"; a related game has been sold as "Bridge-It") is in P.
- GJ 254 [GP1]. S. Even and R. E. Tarjan, A combinatorial problem which is complete in polynomial space, Proc. 7th ACM Symp. Theory of Computing (1975) 66-71 and J. ACM 23 (1976) 710-719.
- S. Reisch, Hex ist PSPACE-vollständig, Acta Inf. 15 (1981) 167-191.
Description: four multicolored cubes are to be stacked so that no color appears twice on a single side of the resulting column.
Status: This is a finite problem, but a generalized version with n cubes and n colors is NP-complete.
- GJ 258 [GP15]. E. Robertson and I. Munro, NP-completeness, puzzles, and games, Util. Math. 13 (1978) 99-116.
* Trademark of Parker Brothers, Inc.
Description: rotate tiles containing drawings of pipes, to make the pipes form a connected network.
- D. Kral et al. It is tough to be a plumber. Theor. Comp. Sci., to appear.
Description: One player sets up a secret configuration of colored pins, and the other player makes a sequence of guesses about the configuration. After each guess, the player with the secret tells the other player how many many pins are correct and how many are the correct color but in the incorrect position. The object is to make as few guesses as possible.
Status: Since this game relies on secret information, it can be treated using classical game theory, but the relevant payoff matrices are so large as to make computation with them intractible. Finding a solution compatible with the guesses made so far is NP-complete; the complexity of determining whether such a solution is unique, or of playing either side of the game optimally, remain open.
- M. de Bondt, Master Mind en andere NP-complete spellen, manuscript, July 2002.
Description: This game (also known as Reversi) is played with reversible pieces on a square board. Players alternate placing pieces on the board, placed with the player's color up; when a piece is placed, the player also reverses lines of pieces of the opposite color sandwiched between the new piece and old pieces of the same color, so that those lines also become pieces of the player's color. The object is to have the most pieces when the board becomes filled.
- S. Iwata and T. Kasai, The Othello game on an n*n board is PSPACE-complete, Theor. Comp. Sci. 123 (1994) 329-340.
Description: Played on a Go board, with one black stone and many white stones. Players on each turn either place a single white stone on any vacant position, or make a sequence of jumps of the black stone over contiguous groups of white stones, removing the jumped stones. The object is to move the black stone to the edge of the board nearest the opponent.
Status: Testing for the existance of a winning move is NP-complete. The complexity of determining the correct outcome of a game position is PSPACE-hard.
Description: A Japanese pencil and paper puzzle in which black and white "pearls" are placed in a square grid. The object is to draw a polygon with edges parallel to the grid lines, through all the pearls, with vertices at each black pearl and adjacent to each white pearl, but no vertices adjacent to any black pearl or at any white pearl.
- E. Friedman, Pearl puzzles are NP-complete, Manuscript, 2002.
Description: This is a commercial sliding block puzzle in which pieces representing cars are placed on a 6x6 grid, with walls surrounding its perimeter except for one exit edge. The cars take up two or three adjacent grid cells, and can only move forwards or backwards. The goal is to move a specially marked target car out through the exit. Similar Java applets are available at PuzzleWorld and RhymeZone.
Status: This is a finite puzzle, but generalizations to arbitrarily large rectangles are PSPACE-complete.
- H. Fernau et al., On the parameterized complexity of a generalized Rush Hour puzzle, CCCG 2003.
- G. W. Flake, Rush Hour is PSPACE-complete, or why you should generously tip parking lot attendants.
- J. Tromp, On size 2 Rush Hour logic.
- R. A. Hearn and E. D. Demaine, The nondeterministic constraint logic model of computation, ACM Computing Research Repository.
* Trademark of Binary Arts, Inc.
Description: This is a computer puzzle, also known as Clickomania, in which a grid is filled with colored tiles. Contiguous groups of two or more tiles of the same color can be removed, causing the tiles above them to drop down. The goal is to remove all tiles.
Status: Solvable in polynomial time for one column of tiles. NP-complete for two or more columns and five or more colors of tiles, or five or more columns and three or more colors of tiles.
Description: This solitaire game is played with Mah-Jongg tiles, which (like playing cards) can be arranged in groups of four similar or identical tiles. The tiles are placed randomly face-up into stacks, forming some particular shape (most computer solitaire implementations include several shapes of varying difficulty). Only the top tile of a stack is visible, although some shapes involve tiles partially covered by other tiles which can be seen but not removed. The object is to remove matching pairs of uncovered tiles until all tiles have been removed.
Status: NP-complete even if all tile positions are known. PSPACE-hard even to approximate the strategy with maximum probability of success when some tiles are covered and unknown.
Proof (of NP-completeness): reduction from 3-SAT. We classify the groups of four tiles into four types: variables, clauses, and keys. We form one stack with one tile from each clause tile group on top (in any order), underneath which are stacked two tiles from each key tile group. For each variable we form three stacks: one with a variable tile on top, two matched keys, and another tile from the same variable tile group; one with a variable tile on top of tiles from all clauses in which the variable appears, and one with a variable tile on top of tiles from all clauses in which the negated variable appears. Then from a satisfying assignment we can produce an ordering of pair removals that frees one pair of tiles from each variable, freeing at least one pair of tiles from each clause, which in turn frees the keys and the remaining variable and clause tiles. Conversely any solution to the Shanghai puzzle produces a satisfying assignment from the original 3-SAT formula.
- A. Condon, J. Feigenbaum, C. Lund, and P. Shor, Random debaters and the hardness of approximating stochastic functions, SIAM J. Comput. 26:2 (1997) 369-400.
Description: A warehouseman moves around a rectilinear maze, pushing pallets one at a time from initial locations scattered throughout the maze until they are all placed in a designated loading dock.
- D. Dor and U. Zwick, Sokoban and other motion planning problems.
- J. Culberson, Sokoban is PSPACE-complete. Int. Conf. Fun with Algorithms, Elba, June 1998. Proceedings in Informatics 4, Carleton Scientific, Waterloo, Canada, 1999, pp. 65-76.
- R. A. Hearn and E. D. Demaine, The nondeterministic constraint logic model of computation, ACM Computing Research Repository.
Description: Players alternate placing vertices on a square grid. Each player's vertices may be connected with edges connecting pairs of vertices a knight's move apart. After placing a vertex, the player may remove some of his own edges or add more of them. No two edges may cross. The object is (like Hex) to connect opposite sides of the board by a path.
Status: NP-complete to determine whether a single set of vertices can support a connecting path. What this implies about the game itself is unclear but it can likely be turned into a proof that determining the correct outcome is NP-hard.
References: D. Mazzoni and K. Watkins, Uncrossed knight paths is NP-complete, manuscript, October 1997.
Combinatorial Games, David Eppstein, ICS, UC Irvine.