[jjs]

Maybe a solver for classic Nintendo games?

http://jeremykun.com/2012/03/22/nintendo-np-hard/

(Caveat: http://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Com... )