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

Oblig XKCD

[Zocalo]

I'd say that this is most definitely NP, for humans and AI alike.

Re:Oblig XKCD

[Crudely_Indecent]

I tied the top score!

0 (zero)

Re:Oblig XKCD

[Anonymous Coward]

I doubled your score, Loser!

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.

P = NP, eh?

[clone53421]

I already wrote a solver for this exact game. It just isn’t efficient.

Re:I'll just have to prove P=NP then.

[clone53421]

Proving that P = NP is easy... you just have to start with contradictory premises.

Re:Sokoban

[owlstead]

"I'm seeing a pattern here..."

Are you sure? Maybe determining if the pattern is correct is also NP-hard.

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.

Re:I solved it

[Anonymous Coward]

But P could be equal to 1 or to 2. That's why this problem is so hard, nobody knows which it is : )