“¿Cuál es la lógica”:
Hay una cuadrícula con 14 filas y columnas de cuadrados.
Cada cuadrado es de un color diferente, elegido al azar (le pregunté al autor) de seis colores diferentes (también dijo que lo actualizaría para que la solución sea posible en ‘capas’, pero no entiendo cuáles son las ‘capas’ son, y no sé si se ha realizado una actualización).
Cuando comienzas el juego por primera vez, la cantidad de movimientos que puedes realizar durante el juego se ve en la esquina superior derecha de la pantalla. A medida que continúa haciendo movimientos, cada vez que realiza un movimiento, muestra el número de movimientos restantes en la esquina inferior izquierda.
El objetivo del juego es hacer que cada cuadro en el tablero sea del mismo color.
Para hacer un movimiento, elige uno de los seis colores.
Cuando haces un movimiento, esto es lo que sucede:
1) El programa encuentra la gota de color contigua a partir de la esquina superior izquierda. El blob contiguo inicial está conectado horizontal o verticalmente, desde la esquina superior izquierda. A veces es solo un cuadrado o, a veces, una forma del mismo color que está conectado a ese primer cuadrado en la esquina superior izquierda. Si es una matriz, entonces esa es la coordenada (1,1) pero si usó las coordenadas x, y podría ser (1, -1) o (1,14) dependiendo de dónde coloque el origen verticalmente.
2) Cuando eliges un color, suceden las siguientes cosas:
a) El blob conectado a la esquina superior izquierda cambia al color que elegiste
b) Como efecto secundario, el nuevo blob contiguo ahora también incluirá los cuadrados adyacentes que sean del mismo color que el color que elegiste, y los blobs que estén conectados a los cuadrados de ese blob.
c) también, ahora tiene 1 movimiento menos permitido antes de que se agote.
Esto aún no está muy claramente definido. Déjame aclararlo
Definición: Cuadrados adyacentes y conectados
Llame a dos cuadrados “adyacentes” si su distancia en la métrica de Manhattan es igual a 1, p. Ej. | X1 – x2 | + | y1 – y2 | = 1. Están “conectados” si son adyacentes y son del mismo color.
Definición: Blob
El “blob” conectado a cualquier cuadrado A dado es el conjunto de cuadrados X que satisfacen la condición …
Blob (A) = {X: X es un cuadrado, y X está conectado a A o existe una secuencia finita de cuadrados intermedios distintos M1, M2, … Mn tal que M1 está conectado a A, M2 está conectado a M1, etc. y Mn está conectado a M (n-1) y X está conectado a Mn}
Por ejemplo, podría verse así para empezar
RGGWBB …
RGWR …
YYYY …
……
Entonces, si eliges Y para comenzar, tendrás una gota más grande de Y porque el RR cambiará a Y. O si eliges G para comenzar, tendrás una gota más grande de G. Pero si eliges W para comenzar, no será ninguna mejora, porque todavía tiene los blobs del mismo tamaño que tenía cuando comenzó. ¡Eso es un desperdicio de turno!
Si logras aumentar el blob inicial para cubrir los 196 cuadrados en menos del número inicial de movimientos asignados, te dice “¡Lo hiciste!”, Lo cual es muy satisfactorio, y luego te da otro rompecabezas, que será más difícil , en promedio, porque el número asignado de movimientos se reducirá en uno.
Si usa los movimientos asignados y los cuadrados en la pantalla todavía tienen más de un color, le dará algo como “Intentar de nuevo”. y sabes que has fallado
Ahora podemos discutir cómo tener éxito en Drench.
Mi experiencia en búsquedas no es extremadamente extensa. Siempre he sido algo malo en eso. Hay algunas cosas que he intentado hacer. Juegos que he intentado programar:
1) Otelo
2) El juego donde tiras canicas en 12 platos y recoges más canicas, pero algunas se ponen en los extremos
3) una vez escribí un probador de teoremas, pero eso sería lo mejor para el problema de Zebra
Hay varios enfoques
Uno es el algoritmo ‘codicioso’, donde simplemente elegirías cualquier movimiento que te diera inmediatamente los mejores resultados. Probablemente esa no sea la mejor estrategia. A veces puede ayudar mucho elegir un color en el que solo crezca tu blob principal en 1, porque el próximo turno podrás hacer crecer tu blob principal en 10 porque hay un blob conectado realmente grande cerca.
Aquí hay otro intento de una idea: sería considerar los seis movimientos y ver cuánto más cerca podría llegar a todos los bordes. Esto es un poco difícil de contemplar. Podría hacer esto en un programa para resolver Drench:
- Considere cada pieza de borde y vea cuántos pasos de blob se necesitan para hacer un camino de regreso a la esquina superior izquierda. Eso hace una sola matriz de números, uno para cada blob en la pantalla, con la longitud mínima de la ruta desde ese borde hasta el origen
- Considere la nueva posición después de cada una de las seis opciones hipotéticamente (obviamente ignórelo si agrega cero cuadrados)
- Para cada una de esas nuevas posiciones, recalcule la matriz (espero que sea fácil) y vea si la respuesta máxima disminuye.
En el juego práctico, lo mejor que he empapado en un tablero son 17 movimientos, pero eso no significa mucho porque algunos tableros son mucho más fáciles de mojar que otros, debido a las manchas más grandes inicialmente.
En el juego práctico, parezco progresar en varias fases:
a) Al principio y durante el juego, trato de acercarme a gotas más largas rápidamente, para hacer que la gota principal se agrande rápidamente
b) Intento moverme hacia el centro de la cuadrícula para empezar. Esto puede ser una compensación con el primer objetivo.
c) Después de esto, hay varias ideas que me gustaría tratar de mirar un poco hacia adelante para ganar eficiencia, tratando de evitar descuidar cualquiera de las tres esquinas distantes, tratando de atacar el centro de áreas que presentan muchas pequeñas gotas cuadradas A veces, si un color es irregular, simplemente lo rodeo y limpio todas las partes irregulares hacia el final.
d) En el final del juego, con 12-6 movimientos restantes, trate de planificar el final para que se acerque lo suficiente a todos los colores del borde, y evite tener que usar el mismo color dos veces. Eliminar un color antes de llegar a 6 movimientos restantes puede ser un buen bono que muestra que vas a tener éxito.
Estoy seguro de que un programa bien escrito podría ser mucho mejor que yo en la mayoría de los casos, y evitar perder en los casos en que pierdo
Obviamente, no hay un gran premio en dinero por ganar en Drench, por lo que parece ser más divertido como un pasatiempo o un misterio. Pero sería bueno ver una buena solución.
Alguien ha publicado que el problema es NP-hard o algo así, pero es una tontería decir eso porque 14 no es igual al infinito y 14 no va al infinito si vas al sitio flashbynight.
