  Tetravex is a widely played one person computer game in which you are given
$n^2$ unit tiles, each edge of which is labelled with a number. The objective
is to place each tile within a $n$ by $n$ square such that all neighbouring
edges are labelled with an identical number. Unfortunately, playing Tetravex is
computationally hard. More precisely, we prove that deciding if there is a
tiling of the Tetravex board is NP-complete. Deciding where to place the tiles
is therefore NP-hard. This may help to explain why Tetravex is a good puzzle.
This result compliments a number of similar results for one person games
involving tiling. For example, NP-completeness results have been shown for: the
offline version of Tetris, KPlumber (which involves rotating tiles containing
drawings of pipes to make a connected network), and shortest sliding puzzle
problems. It raises a number of open questions. For example, is the infinite
version Turing-complete? How do we generate Tetravex problems which are truly
puzzling as random NP-complete problems are often surprising easy to solve? Can
we observe phase transition behaviour? What about the complexity of the problem
when it is guaranteed to have an unique solution? How do we generate puzzles
with unique solutions?
