Número de movimientos para resolver un juego de inundación/teñido de calcetines

Question

[ Pregunta basada en la juego de teñir calcetines ]

[ Actualización: Parece que este juego es más conocido como "Flood it" y es NP-difícil . Además, "el número de movimientos necesarios para inundar todo el tablero es $\Omega(n)$ con alta probabilidad". ]

Pregunta: ¿Cuántos cambios de color (= movimientos) se necesitan para completar un $n\times n$ juego de $c$ ¿Colores? Así es:

1. ¿Cuál es el número previsto de movimientos mínimos necesarios?
2. ¿Cuál es el número máximo de movimientos necesarios?

¿Existe alguna estrategia que resuelva siempre el juego con el mínimo de movimientos? *

Descripción del juego

Dado un $n\times m$ cuadrícula en la que cada nodo se pinta con un color aleatorio entre $c$ colores posibles, definimos un clúster ("nuestro" clúster) de nodos vecinos que contiene sólo nodos del mismo color y debe incluir el nodo superior izquierdo.

Podemos cambiar a voluntad el color de nuestro racimo, ampliándolo así. El objetivo es ampliar nuestro clúster a toda la cuadrícula.

* ¿Cuál es el lugar adecuado para preguntar esto?

Answer 1

Bueno, es fácil decir algo sobre el caso $c=2$ . No hay estrategia, ya que todo lo que puedes hacer es alternar entre los dos colores. Como hay un camino de longitud $2n-2$ (contando los bordes) entre dos puntos cualesquiera, ninguna partida puede durar más de $2n-2$ se mueve. Es fácil construir un juego que tome $2n-2$ movimientos; sólo usa una coloración de tablero de ajedrez.

En el otro extremo, es fácil decir algo sobre el caso $c=n^2$ . Si cada nodo es de un color diferente, entonces siempre se puede extender un nodo en cada movimiento, y nunca se puede extender más de un nodo, por lo que una estrategia óptima tomará $n^2-1$ se mueve.

Así que ahora sólo tenemos que rellenar todos los casos entre....