Tetris Is Hard: NP-Hard 345
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."
Tetris is NP-hard! (Score:5, Funny)
Are you goofing off playing tetris... (Score:5, Funny)
They used math to figure this out? (Score:5, Funny)
I don't get it. They used math to figure out that tetris is hard, but math is hard too.
Hey... (Score:5, Funny)
In Other News (Score:5, Funny)
The only way to win at Tetris... (Score:5, Funny)
Further studies... (Score:2, Funny)
Then NASA will use Moon Buggy as a simulator for the next Mars mission.
And eventually the Army will use Quake to train... ummm... too late on that one. Hey, at least they build their own!
Ravenn
It's not that Tetris is HARD... (Score:5, Funny)
I always sucked at tetris... (Score:4, Funny)
So that's why... (Score:3, Funny)
[self duck];
F-bacher
I wonder... (Score:2, Funny)
Brain Strain in the Ukraine (Score:1, Funny)
man... that is so not fair (Score:4, Funny)
MIT kids do research in TETRIS.
wtf? tell me again why MIT is one of the best engineering school again?
oh wait... i just got it.
I was doing home-work the whole time. (Score:3, Funny)
You'd be amazed at some of the Heuristics you have to use at Level 10!
Re:Hrm. (Score:3, Funny)
Can't you be satisfied with one? I mean do you have any idea how hard it is to get dead Russions to invent anything?
My theory (Score:5, Funny)
Re:They used math to figure this out? (Score:5, Funny)
Instead of studing for my Linear Algebra exam,
I've been busy proving tecmobowl is NP-Fun!
Re:ending of tetris (Score:3, Funny)
Re:and yet (Score:1, Funny)
Re:Online Tetris tournaments (Score:3, Funny)
The nice part: you bet real money. If you are somewhat good you can make some cash."
Maybe the MIT dudes should have known about this...
They could have made their Tetris simulator pay for
their research project and more.
Re:They used math to figure this out? (Score:1, Funny)
Sounds like a talking Barbie:
"Math is hard!"
"Pink is pretty!"
"Ken is hard, and I am easy!"
Re:the second I read the article (Score:3, Funny)
No, but, from own experiences, it's an NP-hard problem to get it out of your head once you've heard it, so please don't give me a link to where it can be downloaded.
Re:ending of tetris (Score:2, Funny)
My father brought it home from work one day, and I played it for the next few months. Took me a while to finally see the 3D blocks. =\
It's scary watching Tetris blocks fill up to the screen TOWARDS you.
A good new view into women... (Score:4, Funny)
New fresh roast student - "Excuse me, but this task it's too hard for me. It deals with a NP-hard task and I don't have the brains for it... Couldn't you give a more simple task for me?.."
Me - "Well go and play some Tetris while I think how we can ease your work..."
After a few hours - "Well what's the score? And you say NP-hard algorithms are too hard for you? You trying to solve a NP-hard algorithm for more than an hour! Cool, go and try to do the same with that task you don't have brains for..."
Tetris is very easy on a Hercules - I should know (Score:3, Funny)
How can this be easy, you ask? Well, I put a delay in there too, it was adjustable from the command line of the TSR. When my score went past -32768 at the highest level, I decided enough was enough, and I didn't play Tetris for many years after.
Re:My theory (Score:3, Funny)
Re:Hrm. (Score:5, Funny)
Are there any other NP-hard games which were invented by dead Russians?
Is Russian Roulette NP-hard?
NP-Hard? (Score:2, Funny)
(Zap! Kapow! Kersplat!)
....I think my geek factor just increased by 1 x 10^2...ouch...
Re:The only way to win at Tetris... (Score:5, Funny)
Look, I know they're from MIT and all... (Score:5, Funny)
Re:Tetiris / Eyeball RSI Warning (Score:5, Funny)
Thanks, if I ever meet you I'll be sure not to be freaked out
Re:Tetiris / Eyeball RSI Warning (Score:1, Funny)
Kirby's Avalanche (Score:2, Funny)
However, when I was about 14, I played a match of Kirby's avalanche against my friend's au pair (mom was divorced and he had a little bro). We had been lpaying all summer, so we were pretty good, but this match lasted well over an hour. The game speed got ridiculous, where the pieces seemed to fall as fast as the graphics processor could display them
Ahhhhh, those were the days!
Re:Poll (Score:5, Funny)
It's reasurring to know that even HE thinks it's rigged.
Re:Tetiris / Eyeball RSI Warning (Score:2, Funny)
Just a warning. I still play it on and off.
It's probably more fun when it's on, right?
Re:A good new view into women... (Score:5, Funny)
And here I thought the rest of your story would involve the use of the pickup line, "Hey baby, wanna play with something that is very NP-Hard?!"
But this doesn't explain why... (Score:2, Funny)
Re:Look, I know they're from MIT and all... (Score:2, Funny)
128-bit Tetris encryption (Score:4, Funny)
This could make the Bovine distributed cracking clients a lot more fun to watch.