DIMACS TR: 2004-11
The Hardness of the Lemmings Game
Authors: Graham Cormode
ABSTRACT
In the computer game `Lemmings', the player must guide a tribe of
green-haired lemming creatures to safety, and save them from an untimely
demise. We formulate the decision problem which is, given a level of the
game, to decide whether it is possible to complete the level (and hence to
find a solution to that level). Under certain limitations, this can be
decided in polynomial time, but in general the problem is shown to be
NP-Hard. This can hold even if there is only a single lemming to save,
thus showing that it is hard to approximate the number of saved lemmings
to any factor.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-11.ps.gz
DIMACS Home Page