Recientemente he empezado a jugar El Flujo De Juego Libre.

Algoritmo para resolver problemas de Flujo Libre Juego de la

Conectar la coincidencia de colores con tubo para crear un flujo. Par todos los colores, y cubrir todo el tablero para resolver cada puzzle en Flujo Libre. Pero cuidado, los tubos se romperá si se cruzan o superponen!

Me di cuenta de que es sólo camino para encontrar el juego entre el mismo par de puntos con las condiciones de que no hay dos rutas se superponen. Yo estaba interesado en escribir una solución para el juego, pero no saben por dónde empezar. Pensé en el uso de retroceso, pero para el tablero de grandes tamaños tendrá tiempo de alta complejidad.

Es allí cualquier algoritmo que resuelva el juego de forma eficiente. Puede el uso de la heurística para resolver el problema de la ayuda? Me acaba de dar una pista sobre por dónde empezar, voy a tomar desde allí.

He observado en la mayoría de los consejos que generalmente

  1. Para más puntos, usted necesita seguir el camino a lo largo del borde.
  2. Para el punto más cercano a cada uno de los otros, seguir camino directo si es que hay uno.

La correcta es esta observación y puede ser utilizado para resolver de manera eficiente?

  • La frase clave es: «la mayoría de las juntas». Libre Flujo es una representación visual de modernización de un conocido NP-Duro (si no NP-Completo) de juego, cuyo nombre(s) no se me ocurre de improviso. Por lo tanto, no se sabe ni se espera tener soluciones eficientes en todos los casos, lo que es más fácil ver si tratas de resolver los más grandes.
  • Así que no hay solución para el rompecabezas?
  • No, simplemente no hay solución eficiente. Un ordenador puede resolver cualquier instancia de Flujo Libre, pero el tiempo que se tarda en promedio crece exponencialmente con el puzzle tamaño. Una estimación aproximada podría decir que un 10×10 es algo así como 30 veces más difícil de resolver que un 5×5, por ejemplo. Yo veo esto en la práctica como puedo resolver el 5×5 rompecabezas en menos de un segundo, pero por lo general toma un poco más tiempo para resolver el 10×10. Mientras tanto, una de 20×20 podría ser acerca de 1000x más difícil de resolver que un 10×10. No hay 20x20s en Flujo Libre, pero he resuelto todos los puzzles en el juego y algunos han tomado un montón de tiempo.
  • Creo que es un caso restringido de multicommodity de flujo, pero eso no necesariamente significa que es NP-duro.
  • Me tomó un tiempo para encontrar, pero here es donde llegué por primera vez a través de ella. Un poco de investigación en línea parece que la confirma. El juego que yo estaba pensando era NumberLink. Me recordó que era por un conocido juego Japonés editor, Nikoli y encontrar el nombre de esa manera.
  • Usted puede tratar de una simulación:stackoverflow.com/questions/18511095/….
  • Bueno, el problema es, sin duda, en NP (ver mi respuesta). La pregunta es si es NP-duro y por lo tanto del tipo NP-completo.
  • La búsqueda de «SAT formulación de numberlink» y «NP-completitud de numberlink» nos lleva a un par de referencias. Como era de esperar, los dos más interesantes son en Japonés. El primero es el papel real de la prueba de NP-completitud. El segundo describe cómo resolver NumberLink utilizando el SAT solver, el Azúcar.
  • Mi programa github.com/thomasahle/numberlink resuelve cualquier rompecabezas en una décima de segundo, si quieres comprobar el codee. Básicamente usa una rama-n-bound de búsqueda con la heurística. La página de Github tiene más información sobre el algoritmo exacto.

InformationsquelleAutor coder hacker | 2014-05-13

5 Comentarios

  1. 7

    Reducción al SAT

    Idea básica

    1. Reducir el problema a SAT
    2. Uso de un moderno SAT solver para resolver el problema
    3. De lucro

    Complejidad

    El problema es, obviamente, en NP: Si adivina una junta de la constelación, es fácil (poli-tiempo) para ver si se soluciona el problema.

    Si es NP-duro (significado tan duro como todos los otros problemas en NP, por ejemplo, SAT), no está claro. Seguramente moderno SAT solvers no de atención y resolución de grandes instancias en una brisa de todos modos (supongo que hasta 100×100).

    Literatura sobre el Número de Enlace

    Aquí tengo una copia Nuclearman comentario de la OP:

    De la búsqueda para «SAT formulación de numberlink» y «NP-completitud de numberlink» nos lleva a un par de referencias. Como era de esperar, los dos más interesantes son en Japonés. El primero es el papel real de la prueba de NP-completitud. El segundo describe cómo resolver NumberLink utilizando el SAT solver, el Azúcar. –

    Pista para la reducción de la SAT

    Hay varias posibilidades para codificar el problema. Te voy a dar uno que yo podría hacer rápidamente.

    Comentario

    j_random_hacker señaló que independiente de los ciclos no están permitidos. La siguiente codificación permite. Este problema hace que el SAT de codificación de un poco menos atractivo. El método más simple de lo que podía pensar para prohibir el pie libre de bucles de introducir O(n^2) nuevas variables, donde n es el número de fichas en el tablero (recuento de distancia a partir de la próxima lavabo para cada azulejo), a menos que uno de los usos de registro de codificación para este, que iba a bajar a O(n*log n), es posible hacer el problema más difícil para el solver.

    Variables

    Una variable por azulejo, pieza tipo y color. Ejemplo si alguna variable X-Y-T-C es cierto que se codifica de que el azulejo en la posición X/Y es de tipo T y tiene un color C. Usted no necesita el vacío tipo teja dado que esto no puede suceder en una solución.

    Conjunto inicial de variables

    Conjunto de las variables para el lavamanos/fuentes y decir ninguna otra pieza puede ser sink/source.

    Restricciones

    1. Para cada posición, exactamente un color/pieza combinación es cierto (restricción de cardinalidad).
    2. Para cada una de las variables (posición, tipo, color), los cuatro fichas adyacentes han de ser compatibles (si coincide con el color).

    Yo podría haber perdido algo. Pero debe ser fácilmente corregido.

    • Cualquier sugerencia sobre cómo reducir el problema al SAT
    • Me pareció muy satisfactorio para reducir los problemas al SAT. Si usted está trabajando en la JVM, que sólo puede tirar en un SAT solver como Maven de dependencia (SAT4J). Es realmente sencillo y rápido.
    • Solución agradable! Creo que se podría reducir a un número entero de programación lineal (ILP) de la misma manera y sólo tiene que utilizar un estándar de solver. Las restricciones son del tipo: cada fuente/sumidero que tiene 1 o 3 vecinos del mismo color, cada célula tiene 2 o 4 vecinos del mismo color. Tema abierto: formalmente demostrar que una solución que cumple con estas restricciones es válido. No puede ser muy difícil por la contradicción.
    • Mientras que la reducción de la ILP es ciertamente posible, yo no recomendaría hacerlo. Esto no es un problema de optimización, sino simplemente un satisfiability problema. El uso de un CSP formato podría ser más cómodo de usar que el SAT, a pesar de que. La diferencia entre el SAT y el CSP es que CSP permite que las variables con más valores de los dos.
    • Sí, tienes razón, no es realmente un problema de optimización.
    • Asumiendo que usted tiene la pieza 2 tipos de «tubo» (las baldosas en su lugar) y «extremo» (las fichas presentes en el inicio), creo que las limitaciones a que está suministrando no se descarta la posibilidad de ciclos (bucles) de «pipe» azulejos. Usted necesita agregar el equivalente de «subtour la eliminación de las restricciones» para el TSP.
    • Ver mi respuesta para un ejemplo de cómo resolverlo con el SAT.

  2. 3

    Sospecho que no polinomio de tiempo de algoritmo está garantizado para resolver en cada instancia de este problema. Pero puesto que uno de los requisitos es que cada cuadrado debe ser cubierto por la tubería, un enfoque similar a lo que ambas personas y equipos de uso para la resolución de Sudoku debería funcionar bien aquí:

    1. Para cada plaza vacía, forma un conjunto de colores posibles para que la plaza, y luego repetidamente realizar deducciones lógicas en cada cuadrado para reducir el tamaño del conjunto permitido de colores para esa plaza.
    2. Siempre un cuadrado del conjunto de posibles colores se reduce a un tamaño de 1, el color para que la plaza se determina.
    3. Si se llega a un estado donde no hay más deducciones lógicas se pueden realizar y el rompecabezas no está completamente resuelto todavía (es decir, hay al menos una plaza con más de un color), elija uno de estos indecisos plazas y recurse en ella, tratando cada uno de los colores posibles en turno. Cada intento se conducen a una solución, o una contradicción; el último elimina el color como una posibilidad para esa plaza.

    Al escoger una plaza en rama, es generalmente una buena idea escoger un cuadrado con tan pocos permitido colores como sea posible.

    [EDITAR: Es importante para evitar la posibilidad de formación no válido «bucles» de la tubería. Una manera de hacer esto es mantener, para cada permitido color i de cada cuadrado de x, 2 bits de información: si el cuadrado de x está conectado por un camino definitivo de la i-azulejos de colores para el primer i-color extremo, y lo mismo para el segundo i-color de extremo. Luego, cuando recursing, no siempre se elige un cuadrado que tiene dos vecinos con el mismo conjunto de bits (o con ninguna conjunto de bits) para cualquier permitido color.]

    Que en realidad no necesita utilizar ningún deducciones lógicas a todos, pero el que más y mejor deducciones de usar, más rápido que el programa se ejecute como ellos (posiblemente dramáticamente) reducir la cantidad de recursividad. Algunas de las deducciones incluyen:

    1. Si un cuadrado es el único camino posible para ampliar la ruta de acceso de algún color en particular, entonces debe ser asignados a ese color.
    2. Si un cuadrado tiene color i en su conjunto de colores, pero no tiene por lo menos 2 de las plazas vecinas que también tienen color i en sus conjuntos de colores, entonces no puede ser «engañado» por cualquier camino de color i, y el color me puede ser eliminado como una posibilidad.

    Más avanzada de las deducciones basadas en la ruta de conectividad podría ayudar aún más-por ejemplo, si se puede determinar que el cada ruta de acceso de la conexión de algún par de conectores debe pasar a través de una plaza particular, usted puede asignar de forma inmediata que el color de la plaza.

    Este sencillo planteamiento se deduce una solución completa sin ningún tipo de recursividad en su 5×5 ejemplo: las plazas en (5, 2), (5, 3), (4, 3) y (4, 4) están obligados a ser de color naranja; (4, 5) es forzado a ser de color verde; (5, 5) también se ve forzado a ser de color verde, por el hecho de que ningún otro color podría llegar a esta plaza, y luego de vuelta otra vez; ahora la naranja camino termina en (4, 4) tiene a dónde ir, excepto para completar la senda naranja en (3, 4). También (3, 1) es forzado a ser de color rojo; (3, 2) es forzado a ser de color amarillo, que a su vez las fuerzas de (2, 1) y, a continuación, (2, 2) a ser de color rojo, que finalmente las fuerzas de el camino amarillo para terminar en (3, 3). El tubo rojo en (2, 2) fuerzas (1, 2) ser de color azul, y el rojo y el azul caminos terminan siendo totalmente determinado», obligando a cada uno de los otros» como van.

    • Se ve prometedor que otras respuestas, trataré de ur enfoque
    • Si utiliza un SAT solver, va a hacer todo lo que se describe en esta respuesta, y más (cosas que no se le ocurra).
    • Puede ser difícil decirle a un SAT solver sobre la necesidad de evitar bucles de la tubería. Para la eliminación de subtours de la TSP esto suele ser manejado por la generación de estas restricciones sobre la marcha, siempre y cuando sean necesario, ya que hay un número exponencial de ellos, por lo que la especificación de todos ellos en la salida iba a ser un non-starter. (Que utiliza una ILP solver, pero la situación es similar.)
    • Así, a) son bucles posible en el juego en absoluto? b) Son desestimado? Este no es el camino más corto del concurso. Es encajar todas las piezas. Si usted simplemente no puede tener bucles/cruces, a continuación, no permita que las piezas correspondientes.
    • Me gusta SAT solvers demasiado, pero j_random_hacker quiere propagar una más complicado de restricción que puede ser fácilmente expresada con el solver que yo he utilizado.
    • Estoy de acuerdo en que potencialmente puede hacer más la propagación de lo que SAT solvers hacer (la gente se enteró de que algo más complicado que la unidad de propagación de no pagar), y, en particular, usted puede hacer esto en un dominio dependiente de la forma como se sugiere. Pero no es simple, y posiblemente el más rápido. Creo que lo que básicamente quiero decir es esto: la Reducción al SAT es fácil y la primera cosa que me gustaría probar. Además no está claro si se puede implementar algo más rápido en una cantidad de tiempo razonable. Pero si usted tiene la diversión de cosas de programación, por supuesto, ir en.
    • En la versión en línea del juego que he encontrado, no se puede crear de pie libre de bucles. No estoy seguro de lo que quieres decir por «entonces no permita que las piezas correspondientes» — ¿cómo lo harían?
    • Ah, me faltaba el pie. De hecho, esto hace que el SAT de codificación mucho más complicado. Siento la necesidad de implementar.

  3. 3

    He encontrado un post en el blog sobre Innecesariamente Complejo que completamente se explica cómo utilizar SAT para resolver este problema.

    El código es de código abierto, así que usted puede mirar (y entender) en acción.

    Voy a dar una cita de aquí que describe las reglas que usted necesita para implementar en el SAT:

    • Cada celda se le asigna un solo color.

    • El color de cada extremo de la célula se conoce y se especifica.

    • Cada extremo de la célula tiene exactamente un vecino que coincida con su color.
    • El flujo a través de cada extremo de la célula coincide exactamente con uno de los seis tipos de dirección.
    • Los vecinos de una celda especificada a través de su dirección de tipo debe coincidir con su color.
    • Los vecinos de una celda no se especifica a través de su dirección de tipo no debe coincidir con su color.

    Gracias @Matt Zucker para la creación de este!

  4. 0

    Me gusta soluciones que son similares a los del pensamiento humano. Usted puede (muy fácilmente) obtener la respuesta de un Sudoku por fuerza bruta, pero es más útil para obtener una ruta que podría haber seguido para resolver el rompecabezas.

    He observado en la mayoría de los consejos que suelen
    1.Para más puntos, usted necesita seguir el camino a lo largo del borde.
    2.Para el punto más cercano a cada uno de los otros, seguir camino directo si es que hay uno.
    La correcta es esta observación y puede ser utilizado para resolver de manera eficiente?

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

    Me gustaría reemplazar su primera regla por éste : si ambos sumideros están a lo largo del borde, usted necesita seguir el camino a lo largo del borde. (Se podría construir un contra-ejemplo, pero es verdad que la mayoría de las veces). Después de realizar una ruta a lo largo del borde, los bloques a lo largo del borde debe ser considerada como parte de la orilla, por lo que su algoritmo intentará seguir el nuevo borde hecha por el anterior tubo. Espero que esta frase tiene sentido…

    De curso, antes de usar los «la mayoría de las veces» reglas, debe seguir absolutos reglas (ver las dos deducciones de j_random_hacker del post).

    Otra cosa es tratar de eliminar las tablas que no puede conducir a una solución. Vamos a llamar a una pendiente de la tubería (que se inicia a partir de un fregadero, pero aún no alcanza el otro lavabo) una serpiente, y la última plaza de la inconclusa de la tubería será llamado a la serpiente en la cabeza. Si usted no puede encontrar una ruta de cuadrados en blanco entre las dos cabezas del mismo color, significa que la junta no puede conducir a una solución y deben ser descartados (o los que usted necesita para dar marcha atrás, en función de su aplicación).

    El libre flujo de juego (y otros juegos similares) aceptar como válida la solución de una junta en la que hay dos líneas del mismo color, de lado a lado, pero creo que siempre existe una solución sin lado-por-lado de las líneas. Eso significaría que en cualquier plaza que no es un disipador tendría exactamente dos vecinos del mismo color, y se hunde tendría exactamente uno. Si la regla pasa a ser siempre verdadera (creo que lo es, pero no puedo probarlo), que sería una restricción adicional para disminuir el número de posibilidades. He resuelto algunas de Flujo Libre del rompecabezas con side-by-side líneas, pero la mayoría de las veces he encontrado otra solución sin ellos. No he visto al lado de las líneas de Flujo Libre del sitio web de soluciones.

  5. 0

    Un par de reglas que conducen a una especie de algoritmo que resuelva los niveles de flujo, basado en el IOS vertions de los Grandes Juegos de Pato, esta empresa parece producir las versiones canónicas. El resto de esta respuesta no asume ninguna paredes, puentes o deformaciones.

    Incluso si su asombrosamente buena, la enorme 15×18 plaza de las tablas son un buen ejemplo de cómo sólo va en ella, en formas que parecen probable es que usted consigue pegado justo antes de que el final una y otra vez y prácticamente tener que empezar de nuevo desde cero. Este es probablemente que ver con la ya mencionada de tiempo exponencial de la complejidad en el caso general. Pero esto no significa que un simple stratergy no es abrumadoramente eficaz para la mayoría de las placas.

    1. Bloques nunca se queda vacío, por lo tanto huérfanos bloques significa que hemos hecho algo mal.

    2. Cardinalmente las células adyacentes del mismo color debe estar conectado. Esto descarta 2×2 bloques del mismo color y en la malla hexagonal triángulos de 3 células vecinas.

    3. Usted puede a menudo hacer perminent progreso, al establecer que un color se va o se excluye de un cierto plaza.

    4. Debido a los puntos 1 y 2, en la malla hexagonal en las tablas que se hexagonal en forma de un tubo que va a lo largo de un borde es generalmente va pegado a lo largo de todo el camino de ronda a la salida, de manera efectiva, moviendo el borde exterior y hacer que el consejo más pequeños, por lo que el proceso puede ser repetido. Es previsible, ¿qué clase de vecinos condiciones de garantía y de qué tipo pueden romper este ciclo para ambos tipos de cuadrícula.

    La mayoría, si no todos 3ª parte de las variantes que he encontrado falta de 1 a 4, pero dadas estas restricciones válida de generación de tablas puede ser una tarea difícil.


    Respuesta:

    Punto 3 sugiere un valor se almacena para cada celda de la que es capaz de ser un color, o un conjunto de falsas/indeterminado valores que hay uno para cada color.

    Un solucionador puede utilizar repetidamente en los puntos 1 y 2, junto con los datos almacenados para el punto 3 en pequeños barrios de caminos alrededor de los extremos de los tubos a los cada vez más colores o establecer el indeterminado valores falsos.

Dejar respuesta

Please enter your comment!
Please enter your name here