Slashdot Mirror

← Back to Stories (view on slashdot.org)

Tetris Is Hard: NP-Hard

Posted by timothy on from the lots-of-chin-scratching dept.

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."

15 of 343 comments (clear)

  1. Tetris is NP-hard! by DeadMoose · · Score: 5, Funny

    Yeah, that's it; I'm not bad at it, it's just too hard. Just like, um, most every other video game I've played...

  2. Are you goofing off playing tetris... by aero6dof · · Score: 5, Funny

    No, I'm empirically testing some NP theories...

  3. They used math to figure this out? by Uhh_Duh · · Score: 5, Funny


    I don't get it. They used math to figure out that tetris is hard, but math is hard too. :(

    --
    -- People who hate Windows use Linux. People who love UNIX use BSD.
    1. Re:They used math to figure this out? by the.jedi · · Score: 5, Funny

      Yeah well we mit people are crazy like that.
      Instead of studing for my Linear Algebra exam,
      I've been busy proving tecmobowl is NP-Fun!

      --
      ThunderBird. Nuff said.
  4. Hey... by bluemilker · · Score: 5, Funny

    those guys are dumb. Everyone knows you just leave a single block wide path in the center... you're _sure_ to get a 4-long column before you hit the... ARGH! ... this would be so much easier if I had a version of tetris that told me all the pieces in advance, like theirs does...

  5. In Other News by GroovBird · · Score: 5, Funny

    Ron Rivest of RSA Security (NASDAQ: RSAS) announced that are releasing a new assymetric encryption algorithm based on Tetris. Since Tetris has been under the scrutiny of millions of people, experts say that it is much more secure than current outdated algorithms such as RSA and Elliptic Curve. This will bring a new era in computer security, Ron says.

  6. The only way to win at Tetris... by gpinzone · · Score: 5, Funny

    Is to prove the P = NP challenge. I think I'll play Quake 3 instead.

    1. Re:The only way to win at Tetris... by SpaceLifeForm · · Score: 5, Funny

      ...is not to play.

      --
      You are being MICROattacked, from various angles, in a SOFT manner.
  7. It's not that Tetris is HARD... by Steve+Cowan · · Score: 5, Funny

    Mathematicians simply can't concentrate on the movement of the pieces, even given all the time they need, because it's too easy to get distracted by that wacky Russian folk music.

  8. My theory by Jugalator · · Score: 5, Funny

    Tetris wouldn't be NP-hard if it just released that damn 1x4 brick when you need it!

    --
    Beware: In C++, your friends can see your privates!
  9. Re:Hrm. by 6Yankee · · Score: 5, Funny

    Are there any other NP-hard games which were invented by dead Russians?

    Is Russian Roulette NP-hard?

  10. Look, I know they're from MIT and all... by MattRog · · Score: 5, Funny

    but that doesn't give them the right to flat-out make up words. "Inapproximability" indeed!

    --

    Thanks,
    --
    Matt
  11. Re:Tetiris / Eyeball RSI Warning by isorox · · Score: 5, Funny

    Just a warning. I still play it on and off.

    Thanks, if I ever meet you I'll be sure not to be freaked out

  12. Re:Poll by Limynali · · Score: 5, Funny

    Last weekend I was priviliged enough to hear Alexey Pajitnov, the creator of Tetris, give a talk on how he came up with tetris, the design process of games, etc... The best part was at the end somene asked him about the dificulty of Tetris and he replied that even though he knew that each piece had the same probabilty (because he coded it) there must be some little guy inside the computer purposefully giving him the 'wrong' pieces and witholding the one he needed, "that Son-of-a-bitch!" (yes, he actually said that)

    It's reasurring to know that even HE thinks it's rigged.

  13. Re:A good new view into women... by tswinzig · · Score: 5, Funny

    The next time I see a girl dealing with NP-hard algorithms and crying she can't hold up, I'll play the dirty trick...

    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?!"

    --

    "And like that ... he's gone."