Flood-It: a game worth a million dollars

3 moves in a game of Flood-It. Starting in the top left corner, the object is to 'flood' the board with one single colour.

Press release issued: 9 April 2010

Flood-It is a computer game played by millions the world over. Dr. Raphaël Clifford and colleagues from the University of Bristol have analysed this popular game and for the first time shown it to be ‘NP-hard’, which means that anyone finding a simple solution to Flood-It could become a millionaire

Flood-It is a computer game played by millions the world over. The object is to turn a board full of coloured squares into one single colour in a limited number of ‘flood-filling’ moves. It is easy to play, yet challenging, great fun and addictive.

Dr. Raphaël Clifford and colleagues from the University of Bristol have analysed this popular game and for the first time shown it to be ‘NP-hard’, which means that anyone finding a simple solution to Flood-It could become a millionaire.

Being NP-hard allows Flood-It to stand alongside the most difficult of all mathematical problems: those where the answer can be quickly checked, but which require an impossibly long time to solve.

Some of the world’s most popular games such as Tetris and Minesweeper have previously been shown to be NP-hard and Flood-It now joins this select list. The fact that these games are NP-hard means they are likely to be fun as human ingenuity is needed in order to beat the computer.

It has been estimated that solving large NP-hard problems could take longer than the current age of the Universe (~14 billion years), even using the fastest computers currently available.

Anyone finding a simple solution to Flood-It could immediately become a millionaire, since this would solve the notorious P (easy to solve) versus NP (easy to check) problem, and would win one of the seven million-dollar Millennium Prizes offered by the Clay Mathematics Institute in Massachusetts, USA. The prize is awarded to anyone cracking one of the (now six) most difficult mathematical problems in the world.

In another entertaining application, the results have implications for models of zombie infestation. Dr Clifford said: “Flood-It can also be thought of as a model for a number of different applications. For example, these results supplement that of recent work on zombie infestation, if one regards the flooding operation as one where the minds of neighbouring non-zombies are infected by those who have already been turned into zombies”.

On a more serious level, the results indicate that even very simple models of the way infectious diseases spread may be difficult to analyse. The new work also implies that a fast way of solving Flood-It would allow many problems of immense practical and economic interest to be solved. These range from cracking codes sent by foreign governments to designing perfect aeroplane wings and making robots with human intelligence.

The Flood-It results were discovered by David Arthur, Raphaël Clifford, Markus Jalsenius, Ashley Montanaro and Benjamin Sach from the University of Bristol’s Algorithms Research Group in the Department of Computer Science.

Their results will be presented by Markus Jalsenius at a conference in Edinburgh on 9 April.

Dr Jalsenius said: “The team hopes that our work demonstrating core concepts of computer science using a well-known game will make the field more appealing and accessible. Maybe it will even inspire more A-level students to become interested in the theoretical aspects of the subject”.

Further information

For more information on the Millennium Prize offered for solving the P versus NP problem see: http://www.claymath.org/millennium/P_vs_NP. The Millennium Prizes were conceived to record the seven most difficult problems with which mathematicians were grappling at the turn of the second millennium. In March 2010, a million dollars was awarded to Dr. Grigory Perelman (who refused to accept the money) for resolution of the Poincaré Conjecture, leaving only six problems to be solved.

Please contact Cherry Lewis for further information.