[ 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:
- What is the expected number of minimum moves needed?
- 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?