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

1 of 322 comments (clear)

  1. Re:Oblig XKCD by Lord+Bitman · · Score: 0, Redundant

    that is not tetris.

    --
    -- 'The' Lord and Master Bitman On High, Master Of All