There's a variety of NP-Complete problems like the Clique problem, the Hamiltonian cycle problem, Satisfiability, etc. Recently i discovered a simple puzzle problem that is NP-Complete (the proof involves a straightforward reduction of the Clique problem). Anyway, i built the actual puzzle game, using flash and i think it's cool because it illustrates the difficulty of solving NP-Complete problems and why, in all likelihood, P != NP. http://www.bloo.us/blog/?blogger=4&pid=13 I'm thinking of putting together a site with NP-Complete puzzle games. I can think of a couple of others.