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

Use Quake?

[stackdump]

What are you talking about, what did the army use quake to do? Either you are way off base or you didn't link to the story where the army uses Quake. Basically I am saying, WTF?

Too much math nowadays

[MalleusEBHC]

What is it with all these bastards relating simple, enjoyable, time-wasting games with math? First I heard Minesweeper was NP-Hard. No problem, I don't use Windows so my goofing off wasn't affected. Now Tetris is NP-Hard. No big deal, I haven't played Gameboy snce I was 8 probably. (I can see it now... "When I was a kid, we played Gameboy in black and white after walking 15 miles in the snow, uphill, with no shoes on...") But I swear on my geekhood that if someone dares to ever apply math to Snood I will have their head.

What about Bust-A-Move?!?

[natron 2.0]

So if Tetris is NP-Hard does that mean that Bust-A-Move is NP-Crap? It sure feels that way...