All the Best Games May Be NP-Hard

Catullus writes "Following in the footsteps of Tetris and Minesweeper, the simple yet addictive multiplatform game Flood-It is the latest puzzle to be proven to be hard — NP-hard, to be exact. This means that there's no way to write an efficient program to beat the game, unless P=NP. This research by computer scientists from Bristol University raises the intriguing question: are these games fun precisely because they're hard for computers to solve, and need a spark of human creativity?"

Comments

Re:Just to throw this out there

[Anonymous Coward]

I have no idea what you just said. Can you use a car analogy?

Re:The fun is in the simplicity

[quantumplacet]

exactly, because every single windows user plays minesweeper, but not tetris which is unfortunately only available for ps2.

Re:Oblig XKCD

[Anonymous Coward]

I doubled your score, Loser!

I solved it

[jimbolauski]

P=N*P
N=1

P! = N * P
(P-1)! = N
(P-1)! = 1
P = 1

Now where in my Nobel Peace Prize.