Mathematical Digest

Short Summaries of Articles about Mathematics
in the Popular Press

"Maths proves Tetris is tough," by Helen Pearson. Nature ScienceUpdate, 28 October 2002.

Those who have trouble solving Tetris can take heart in the fact that ErikDemaine and two other colleagues have shown that the problem of playing Tetrisefficiently is NP-complete. Tetris is a popular computer game involving fittingpieces -- made up of four squares -- that drop from the top of the screen intoopenings in rows. It may sound easy, but Demaine and his colleagues have nowconfirmed that it is not. Pearson points out that other games, like chess andGo, are even harder.

--- Mike Breen