All the Best Games May Be NP-Hard 322
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?"
Oblig XKCD (Score:3, Funny)
Re:Just to throw this out there (Score:4, Funny)
I have no idea what you just said. Can you use a car analogy?
Re:The fun is in the simplicity (Score:5, Funny)
exactly, because every single windows user plays minesweeper, but not tetris which is unfortunately only available for ps2.
P = NP, eh? (Score:3, Funny)
I already wrote a solver for this exact game. It just isn’t efficient.
Re:Oblig XKCD (Score:4, Funny)
I tied the top score!
0 (zero)
Re:I'll just have to prove P=NP then. (Score:3, Funny)
Proving that P = NP is easy... you just have to start with contradictory premises.
Re:Oblig XKCD (Score:4, Funny)
I doubled your score, Loser!
Re:Sokoban (Score:3, Funny)
"I'm seeing a pattern here..."
Are you sure? Maybe determining if the pattern is correct is also NP-hard.
I solved it (Score:5, Funny)
N=1
P! = N * P
(P-1)! = N
(P-1)! = 1
P = 1
Now where in my Nobel Peace Prize.
Re:I solved it (Score:1, Funny)
But P could be equal to 1 or to 2. That's why this problem is so hard, nobody knows which it is : )