@inproceedings{2001296,
author={David Arthur and  Raphaël Clifford and  Markus Jalsenius and  Ashley Montanaro and Benjamin Sach},
title={ The Complexity of Flood Filling Games},
booktitle={Proceedings of the 5th International Conference on FUN WITH ALGORITHMS (FUN)},
publisher={Springer LNCS},
pages={307--318},
month={June},
year={2010},
abstract={We study the complexity of the popular one player combinatorial game known as Flood-It. In this game the player is given an n by n board of tiles, each of which is allocated one of c colours. The goal is to fill the whole board with the same colour via the shortest possible sequence of flood filling operations from the top left. We show that Flood-It is NP-hard for c > 2, as is a variant where the player can flood fill from any position on the board.  We present deterministic (c-1) and randomised 2c/3 approximation algorithms and show that no polynomial time constant factor approximation algorithm exists unless P=NP. We then demonstrate that the number of moves required for the 'most difficult' boards grows like Theta(sqrt(c)n). Finally, we prove that for random boards with c>2, the number of moves required to flood the whole board is Omega(n) with high probability.},
abstract-url={http://www.cs.bris.ac.uk/Publications/pub_master.jsp?id=2001296},
keyword={Algorithms},
pubtype={102}
}