The Complexity of Flood Filling GamesDavid Arthur, Raphaël Clifford, Markus Jalsenius, Ashley Montanaro, Benjamin Sach, The Complexity of Flood Filling Games. Proceedings of the 5th International Conference on FUN WITH ALGORITHMS (FUN), pp. 307–318. June 2010. No electronic version available. External information
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.
- Homepage of Raphaël Clifford
- Homepage of Markus Jalsenius
- Homepage of Ashley Montanaro
- Homepage of Benjamin Sach