THE addictive computer game Tetris really is hard. A mathematical proof has shown that even under ideal conditions, there is no way to work out the best moves.
Tetris involves fitting together different-shaped blocks as they appear on the screen. But even if you know which blocks are coming you can鈥檛 guarantee a perfect sequence of moves, say Erik D. Demaine and his colleagues at MIT in Cambridge.
Demaine will tell a workshop on computational geometry at Rutgers University in New Jersey that Tetris is an 鈥淣P complete鈥� problem. In other words, no known algorithm can find the optimal solution.
Advertisement