Number of moves to solve a flood-it/sock-dye game

[ Question based on the sock dye game ]

[ Update: It appears that this game is better known as "Flood it" and is NP-hard. Also, "the number of moves required to flood the whole board is $\Omega(n)$ with high probability." ]

Question: How many color changes (= moves) are needed to complete a $n\times n$ game of $c$ colors? That is:

1. What is the expected number of minimum moves needed?
2. What is the maximum number of moves needed?

Is there a strategy that always solves the game with minimum moves?*

Description of the game

Given an $n\times m$ grid where each node is painted with a random color between $c$ possible colors, we define a cluster ("our" cluster) of neighboring nodes that contains only nodes of the same color and must include the upper left node. We can change the color of our cluster at will, thus extending it. The goal is to expand our cluster to all the grid.

* Where is the proper place to ask this?

• Also please suggest a better title. – Eelvex Apr 21 '11 at 1:12
• You've got $c$ colors in the Description but $m$ colors in the Question. Could be slightly confusing. Nice question. – Matthew Conroy Apr 21 '11 at 4:12
• @Matthew: The difference was intentional to draw attention to the fact that I'm asking for a square grid not the rectangular, general case of the game. Thanks for your comment. – Eelvex Apr 21 '11 at 4:15
• Do neighbouring nodes include diagonally adjacent nodes? Also, the example you drew happens to be staircase-shaped -- do I understand correctly that that's not a requirement and the cluster can extend into the grid in an arbitrarily complex shape? – joriki Apr 21 '11 at 4:58
• See also stackoverflow.com/q/1430962: "How to optimally solve the flood fill puzzle?" – Hans Lundmark Apr 21 '11 at 8:15

Well, it's easy to say something about the case $c=2$. There is no strategy, since all you can do is alternate between the two colors. Since there is a path of length $2n-2$ (counting the edges) between any two points, no game can take more than $2n-2$ moves. It's easy to construct a game that takes $2n-2$ moves; just use a checkerboard coloring.
At the other extreme, it's easy to say something about the case $c=n^2$. If each node is a different color, then you can always extend by one node at each move, and you can never extend by more than one node, so an optimal strategy will take $n^2-1$ moves.
• If $c=n^2$, which I take to mean all $n^2$ colors are used, then with perfect play best case equals average case equals worst case equals $n^2-1$. At each move, you extend by exactly one more node. – Gerry Myerson Feb 29 '12 at 3:21