Slashdot Mirror
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."
Mod Parent up. Some of us might knopw what an NP problen is, but this guy laid down the hard facts.
"A language that doesn't affect the way you think about programming, is not worth knowing" - Alan Perlis
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.
Stop the brainwash
Me fail English? That's unpossible!
That green slime had it coming.