Slashdot Mirror

← Back to Stories (view on slashdot.org)

All the Best Games May Be NP-Hard

Posted by kdawson on from the easy-for-you-to-say dept.

Catullus writes "Following in the footsteps of Tetris and Minesweeper, the simple yet addictive multiplatform game Flood-It is the latest puzzle to be proven to be hard — NP-hard, to be exact. This means that there's no way to write an efficient program to beat the game, unless P=NP. This research by computer scientists from Bristol University raises the intriguing question: are these games fun precisely because they're hard for computers to solve, and need a spark of human creativity?"

4 of 322 comments (clear)

  1. Metaquestion by camperdave · · Score: -1, Offtopic

    games science complexity story
    it askslashdot wiki iso9001 goodluckwiththat story
    crime atm bank malware money story
    science space planets pluto leavepoorplutoalone story
    crime privacy yro identitytheft money story

    Why is every story tagged story?

    --
    When our name is on the back of your car, we're behind you all the way!
  2. Re:MetaMetaquestion by Anonymous Coward · · Score: -1, Offtopic

    Why do tacos taste like tacos?

  3. Proven to be hard??? by thijsh · · Score: -1, Offtopic

    My P is proven to be hard for a girl with NP.

  4. Re:The fun is in the simplicity by somersault · · Score: 1, Offtopic

    No, but you are inobservant. It's called Minesweeper.

    --
    which is totally what she said