Tetris Is Hard: NP-Hard

bughunter writes "Analysts at MIT Laboratory for Computer Science, who have been busy translating, rotating and dropping, have demonstrated what the rest of us suspected: Tetris is hard. Technically, it's 'NP-hard,' meaning that there is no efficient way to calculate the necessary moves to "win," even if you know in advance the complete order of pieces, and are given all the time you need to make each move. At least there's one geek classic that refuses to fall to the scrutiny of mathematicians."

Comments

This article is false...there is one who can

[dolphin558]

http://www.geocities.com/lilmacumd/escape.html

Re:Further studies...

[MrMetlHed]

Moon Buggy? No no no... Moon Patrol. That way they could blow up or jump over everything in their path on the Martian surface.

Charlie

Re:Winning

[jericho4.0]

Mod Parent up. Some of us might knopw what an NP problen is, but this guy laid down the hard facts.

Quadra

[Anonymous Coward]

Tetris is boring, Try quadra

Whoever downmodded me don't know science

[Jeppe Salvesen]

I am quite shocked to see someone downmodded my suggestion we experimentally test the conclusion of the paper. They have created a theory that can be tested. Let's test it, folks.

The knowledge we have today comes from a careful interplay between theory and experiment. They have set forth theories that can be tested and verified. What appears to be solid logic may also have loopholes in it - maybe even hidden deep into the assumptions. Experimentation can at least sometimes expose incorrect theories.

So - get a grip, and lose the awe of what appears to be definite proof for the NP-completeness of the game you've struggeled with for so long.

Re:ending of tetris

[Anonymous Coward]

Your mom screws after a few lines?

Big surprise.

Re:Look, I know they're from MIT and all...

[Xaroth]

Me fail English? That's unpossible!