## Flood-It: The Colourful Game of Board Domination## Markus JalseniusThis talk is about the popular one player combinatorial game known as Flood-It. In this game the player is given an n by n board of tiles where each tile is allocated one of c colours. The goal is to make the colours of all tiles equal via the shortest possible sequence of flooding operations. In the standard version, a flooding operation consists of the player choosing a colour k, which then changes the colour of all the tiles in the monochromatic region connected to the top left tile to k. After this operation has been performed, neighbouring regions which are already of the chosen colour k will then also become connected, thereby extending the monochromatic region of the board. We will present various interesting facts about Flood-It that we have discovered. For example, we will see that finding an optimal solution is NP-hard if the number of colours is at least three and that this even holds when the player can perform flooding operations from any position on the board. We will also demonstrate how well greedy approaches solve the game, give some approximation results and examples of "most difficult" boards. At the end of the talk we will take a look at random boards, where the colour of each tile is randomly chosen. Joint work with David Arthur, Raphael Clifford, Ashley Montanaro, Benjamin Sach. For those interested in playing the game, publiclty available versions, including our own implementation, can be found linked from http://floodit.cs.bris.ac.uk.Back |