Considere el siguiente juego: hay un n×n , donde cada celda es de color al azar en uno de los m colores. Dejar que un grupo de células de un conjunto del mismo color de las células s.t. cada célula de un grupo tiene al menos una arista común con otro del mismo color de la célula. Un grupo de s$\geq$k las células se puede "estallar", es decir, se retiran del campo y un jugador se le asigna una puntuación. Cuando un grupo es eliminado, el resto de las células son desplazadas s.t. ninguna célula tiene una celda vacía debajo de la misma (básicamente, las células restantes "caer"). Si una columna se desvanece como resultado de estallar, cada no-vacía de la columna de la izquierda se desplaza una celda a la derecha. El juego termina cuando no hay grupos de izquierda en el campo. El resultado es una función de s, y en el final un puntaje acumulado se calcula. El objetivo del juego es conseguir el máximo de puntuación acumulada.
La pregunta es si existe un algoritmo que permite calcular el máximo posible de puntuación para una determinada partida la disposición de las células? Sospecho que tiene algo que ver con el gráfico de la búsqueda, pero tengo poca experiencia con este tipo de cosas. Puede alguien por favor sugieren cómo puede un enfoque de este tipo de problema? También he pensado en hacer algo con autómatas celulares, pero realmente tengo la duda de este enfoque, sin embargo la diversión puede ser).
