pathfinding - application of a star algorithm

Algoritmo para resolver el flujo Juego Gratis (5)

Recientemente empecé a jugar al juego Flow Free .

Conecte los colores a juego con la tubería para crear un flujo. Combina todos los colores y cubre todo el tablero para resolver cada rompecabezas en Flow Free. ¡Pero cuidado, las tuberías se romperán si se cruzan o se superponen!

Me di cuenta de que es solo un juego de búsqueda de caminos entre un par de puntos dados con condiciones en las que no se superponen dos caminos. Estaba interesado en escribir una solución para el juego, pero no sé por dónde empezar. Pensé en utilizar el retroceso, pero para tamaños de tableros muy grandes tendrá una complejidad de tiempo alta.

¿Hay algún algoritmo adecuado para resolver el juego de manera eficiente? ¿Puede el uso de heurísticas para resolver el problema ayudar? Solo dame una pista sobre dónde empezar, lo tomaré desde allí.

Observé en la mayoría de las tablas que usualmente

Para los puntos más lejanos, debes seguir el camino a lo largo del borde.
Para el punto más cercano entre sí, siga el camino directo si hay uno.

¿Es esta observación correcta y puede ser usada para resolverla eficientemente?

Reducción a SAT

Idea básica

Reducir el problema a SAT
Utilice un solucionador SAT moderno para resolver el problema
Lucro

Complejidad

Obviamente, el problema está en NP: si adivina una constelación de tableros, es fácil (poli-tiempo) verificar si resuelve el problema.

No está claro si es difícil NP (lo que significa tan difícil como cualquier otro problema en NP, por ejemplo, SAT). Seguramente los solucionadores de SAT modernos no se preocuparán y resolverán grandes instancias en una brisa de todos modos (supongo que hasta 100x100).

Literatura sobre el enlace numérico

Aquí solo copio el comentario de Nuclearman al OP:

La búsqueda de "Formulación SAT de enlace numérico" y "NP-completitud de enlace numérico" conduce a un par de referencias. Como era de esperar, los dos más interesantes están en japonés. La first es la prueba de papel real de NP-completa. El second describe cómo resolver NumberLink usando el solucionador SAT, Sugar. -

Sugerencia de reducción a SAT

Hay varias posibilidades para codificar el problema. Te daré una que pueda maquillar rápidamente.

Observación

j_random_hacker observó que los ciclos independientes no están permitidos. La siguiente codificación los permite. Este problema hace que la codificación SAT sea un poco menos atractiva. El método más simple en el que podría pensar para prohibir los bucles independientes introduciría O (n ^ 2) nuevas variables, donde n es el número de mosaicos en el tablero (recuento de distancia desde el siguiente sumidero para cada mosaico) a menos que uno use la codificación de registro para esto, que lo llevaría a O(n*log n) , posiblemente dificultaría el problema para el solucionador.

Variables

Una variable por pieza, tipo de pieza y color. Por ejemplo, si alguna variable XYTC es verdadera, codifica que el mosaico en la posición X / Y es del tipo T y tiene el color C No necesita el tipo de mosaico vacío ya que esto no puede suceder en una solución.

Establecer variables iniciales

Establezca las variables para el sumidero / fuentes y diga que ninguna otra ficha puede ser sumidero / fuente.

Restricciones

Para cada posición, exactamente una combinación de color / pieza es verdadera (restricción de cardinalidad).
Para cada variable (posición, tipo, color), los cuatro mosaicos adyacentes deben ser compatibles (si el color coincide).

Podría haber perdido algo. Pero debería ser arreglado fácilmente.

Algunas reglas que conducen a una especie de algoritmo para resolver niveles en flujo, basadas en las versiones de IOS de Big Duck Games, esta compañía parece producir las versiones canónicas. El resto de esta respuesta no asume paredes, puentes o urdimbres.

Incluso si eres increíblemente bueno, los enormes tableros cuadrados de 15x18 son un buen ejemplo de cómo hacerlo de una manera que probablemente te atasque justo antes del final una y otra vez y prácticamente tenga que empezar de nuevo desde cero. Esto probablemente tenga que ver con la complejidad de tiempo exponencial ya mencionada en el caso general. Pero esto no significa que una estrategia simple no sea abrumadoramente efectiva para la mayoría de las tablas.

Los bloques nunca se dejan vacíos, por lo tanto, los bloques huérfanos significan que has hecho algo mal.
Se deben conectar células cardinales vecinas del mismo color. Esto elimina 2x2 bloques del mismo color y en los triángulos hexagonales de 3 celdas vecinas.
Con frecuencia, puede hacer un progreso permanente estableciendo que un color va o está excluido de un cuadrado determinado.
Debido a los puntos 1 y 2, en la rejilla hexagonal de las placas que tienen forma hexagonal, una tubería que va a lo largo de un borde generalmente se atasca a lo largo de todo el camino hacia la salida, moviendo efectivamente el borde exterior hacia adentro y haciendo que la tabla sea más pequeña. El proceso se puede repetir. Es predecible qué tipo de condiciones vecinas garantizan y qué clases pueden romper este ciclo para ambos tipos de cuadrícula.

La mayoría, si no todas las variantes de terceros que he encontrado, faltan de 1 a 4, pero dadas estas restricciones que generan tableros válidos puede ser una tarea difícil.

Responder:

El punto 3 sugiere que se almacene un valor para cada celda que puede ser un color o un conjunto de valores falsos / indeterminados, siendo uno para cada color.

Un solucionador podría usar repetidamente los puntos 1 y 2 junto con los datos almacenados para el punto 3 en pequeñas vecindades de caminos alrededor de los extremos de las tuberías para establecer cada vez más colores o establecer los valores indeterminados en falso.

Encontré una publicación de blog en Needlessly Complex que explica completamente cómo usar SAT para resolver este problema.

El código también es de código abierto, por lo que puede verlo (y entenderlo) en acción.

Aquí le proporcionaré una cita que describe las reglas que necesita implementar en SAT:

A cada celda se le asigna un solo color.
El color de cada celda de punto final es conocido y especificado.
Cada celda de punto final tiene exactamente un vecino que coincide con su color.
El flujo a través de cada celda sin punto final coincide exactamente con uno de los seis tipos de dirección.
Los vecinos de una celda especificada por su tipo de dirección deben coincidir con su color.
Los vecinos de una celda no especificados por su tipo de dirección no deben coincidir con su color.

Gracias @Matt Zucker por crear esto!

Me gustan las soluciones que son similares al pensamiento humano. Puedes (bastante fácilmente) obtener la respuesta de un Sudoku por fuerza bruta, pero es más útil obtener un camino que pudieras haber seguido para resolver el rompecabezas.

Observé en la mayoría de las tablas que, por lo general, 1. Para los puntos más lejanos, es necesario seguir el camino a lo largo del borde. 2.Para el punto más cercano entre sí, siga el camino directo si hay uno. ¿Es esta observación correcta y puede ser usada para resolverla eficientemente?

Estos son verdaderos "la mayoría de las veces", pero no siempre.

Yo reemplazaría tu primera regla por esta: si ambos sumideros están a lo largo del borde, debes seguir el camino a lo largo del borde. (Podrías construir un contra-ejemplo, pero es cierto la mayoría de las veces). Después de hacer un camino a lo largo del borde, los bloques a lo largo del borde deben considerarse parte del borde, por lo que su algoritmo intentará seguir el nuevo borde creado por la tubería anterior. Espero que esta frase tenga sentido ...

Por supuesto, antes de usar esas reglas "la mayoría de las veces", debe seguir las reglas absolutas (consulte las dos deducciones de la publicación de j_random_hacker).

Otra cosa es tratar de eliminar los tableros que no pueden conducir a una solución. Llamemos a una tubería sin terminar (una que comienza desde un fregadero pero que aún no llega a la otra) una serpiente, y el último cuadrado de la tubería sin terminar se llamará cabeza de la serpiente. Si no puede encontrar una ruta de cuadrados en blanco entre las dos cabezas del mismo color, significa que su tablero no puede llevar a una solución y debe ser descartado (o necesita retroceder, dependiendo de su implementación).

El juego de flujo libre (y otros juegos similares) aceptan como una solución válida un tablero donde hay dos líneas del mismo color una al lado de la otra, pero creo que siempre existe una solución sin líneas una al lado de la otra. Eso significaría que cualquier cuadrado que no sea un sumidero tendría exactamente dos vecinos del mismo color, y los sumideros tendrían exactamente uno. Si la regla resulta ser siempre cierta (creo que lo es, pero no puedo demostrarlo), esa sería una restricción adicional para disminuir el número de posibilidades. Resolví algunos de los enigmas de Free Flow usando líneas en paralelo, pero la mayoría de las veces encontré otra solución sin ellos. No he visto líneas en paralelo en el sitio web de soluciones de Free Flow.

Sospecho que no se garantiza que ningún algoritmo de tiempo polinomial solucione cada instancia de este problema. Pero dado que uno de los requisitos es que cada casilla debe estar cubierta por tubería, un enfoque similar al que usan las personas y las computadoras para resolver el Sudoku debería funcionar bien aquí:

Para cada cuadrado vacío, forme un conjunto de colores posibles para ese cuadrado, y luego realice repetidamente deducciones lógicas en cada cuadrado para reducir el conjunto de colores permitido para ese cuadrado.
Cada vez que el conjunto de colores posibles de un cuadrado se reduce al tamaño 1, se determina el color para ese cuadrado.
Si alcanzamos un estado en el que ya no se pueden realizar más deducciones lógicas y el rompecabezas aún no está completamente resuelto (es decir, hay al menos un cuadrado con más de un color posible), elija uno de estos cuadrados indecisos y hágalo en cada uno, probando cada uno de los colores posibles a su vez. Cada intento conducirá a una solución o a una contradicción; este último elimina ese color como una posibilidad para ese cuadrado.

Al elegir un cuadrado para ramificar, generalmente es una buena idea elegir un cuadrado con la menor cantidad de colores posibles.

[EDIT: Es importante evitar la posibilidad de formar "bucles" no válidos de tubería. Una forma de hacerlo es manteniendo, para cada color permitido i de cada cuadrado x, 2 bits de información: si el cuadrado x está conectado por una ruta de mosaicos de color i definidos al primer punto final de color i, y el mismo cosa para el segundo punto final de i-color. Luego, cuando haga recursividad, nunca elija un cuadrado que tenga dos vecinos con el mismo conjunto de bits (o sin ningún conjunto de bits) para cualquier color permitido.]

En realidad, no necesita usar ninguna deducción lógica, pero cuantas más y mejores deducciones use, más rápido se ejecutará el programa, ya que (posiblemente, dramáticamente) reducirá la cantidad de recursión. Algunas deducciones útiles incluyen:

Si un cuadrado es la única forma posible de extender la ruta para un color en particular, entonces se le debe asignar ese color.
Si un cuadrado tiene color i en su conjunto de colores permitidos, pero no tiene al menos 2 cuadrados contiguos que también tengan color i en sus conjuntos de colores permitidos, entonces no puede ser "alcanzado" por ningún camino de color i , y el color i puede ser eliminado como una posibilidad.

Las deducciones más avanzadas basadas en la conectividad de la ruta podrían ayudarlo más: por ejemplo, si puede determinar que cada ruta que conecta algún par de conectores debe pasar a través de un cuadrado en particular, puede asignar ese color inmediatamente al cuadrado.

Este sencillo enfoque infiere una solución completa sin ninguna recursión en su ejemplo de 5x5: los cuadrados en (5, 2), (5, 3), (4, 3) y (4, 4) se ven obligados a ser de color naranja; (4, 5) es forzado a ser verde; (5, 5) también se ve obligado a ser verde por el hecho de que ningún otro color puede llegar a este cuadrado y luego regresar; ahora el camino naranja que termina en (4, 4) no tiene a dónde ir, excepto para completar el camino naranja en (3, 4). También (3, 1) es forzado a ser rojo; (3, 2) es forzado a ser amarillo, lo que a su vez obliga a (2, 1) y luego (2, 2) a ser rojo, lo que finalmente obliga a la trayectoria amarilla a terminar en (3, 3). El tubo rojo en (2, 2) obliga a (1, 2) a ser azul, y los caminos rojo y azul terminan siendo completamente determinados, "obligándose unos a otros" a medida que avanzan.