algorithm - solucionador - slide puzzle solver 3x3

Resolviendo Nonogramas(Picross)

Question

Hola, es viernes por la tarde, vamos a tener un problema de rompecabezas / algoritmo divertido para resolver.

Uno de mis juegos favoritos de Nintendo DS es Picross DS . El juego es bastante simple, involucra resolver rompecabezas llamados Nonograms . Puedes probar un sencillo clon de Picross en línea aquí: Picross de TylerK .

Los nonogramas son una cuadrícula, con secuencias de números definidas para cada fila y columna de la cuadrícula. Los números definen bloques de cuadrados "rellenados" para esa fila / columna, pero las áreas sin rellenar a ambos lados de los bloques no están definidas. Por ejemplo, si tiene una fila que se ve así:

http://steam-punk.net/images/picross1.jpg

Las posibles soluciones para esa fila incluirían:

http://steam-punk.net/images/picross2.jpg http://steam-punk.net/images/picross3.jpg

etc.

El "4 5" simplemente le dice que, en algún lugar de la fila, hay 4 bloques secuenciales rellenados, seguidos de 5 bloques secuenciales rellenos. Esos serán los únicos bloques rellenados, y la cantidad de espacio antes / después de ellos son no definida.

Un rompecabezas se completa cuando todas las filas y columnas cumplen con sus definiciones, sin ninguna contradicción.

Juego de conceptos extremadamente simple, pero puede llevar bastante tiempo resolver algunos de ellos manualmente. Los rompecabezas de Picross DS aumentan gradualmente de tamaño hasta 25x20 rejillas, lo que generalmente me tomaría alrededor de media hora para resolverlo.

Sin embargo, siempre se me ocurre que sería un juego bastante fácil escribir un programa para resolver. Nunca lo logré, pero quizás algunas personas aquí disfrutarán del desafío. Si se publica un número decente de soluciones, las compararé en un gran rompecabezas entre sí, similar a lo que Paolo Bergantino hizo aquí con su pregunta de Boggle . Hay un poco de información en la página de Wikipedia de Nonogram sobre los métodos para atacar un rompecabezas, si quieres hacer referencia a eso.

Aquí hay una definición fácil de analizar de Puzzle # 1 de Picross de TylerK, para que tengas algo para alimentar un programa. La línea 1 es dimensiones del rompecabezas (probablemente innecesaria), la línea 2 es definiciones de la fila, la línea 3 es definiciones de la columna. Esto es solo lo primero que se me ocurrió, por lo que si alguien puede pensar en un mejor formato de entrada, no dude en comentar o editar esta publicación para incluirla.

15 15
15,4 5,2 4,1 3,2,2,2 4 3,2 6 2,2 1 6 2,2 1 1 4 2,1 1,1 3 2 1,2 2 1 2 1,3 3 2 1,9
4 4,3 1 2 3,2 1 2 2,2 1 1,1 4 2,1 3,1 8,1 3 1 1,1 4 2 1,1 4,2 4 3,3 3 3,4 1,10 3,10

Answer 1

¿El problema real es si alguien puede crear un algoritmo que resuelva dicho rompecabezas más rápido que un humano? Esto es fácil para rompecabezas relativamente fáciles como el de referencia, pero si el rompecabezas crece, la mayoría de los algoritmos aquí se ralentizarán rápidamente. Aquí está el rompecabezas que intenté resolver. El problema es que la 4ª fila, por ejemplo, tiene 2220075 combinaciones posibles, creo. Si el algoritmo de Charlie acepta temporalmente una fila incorrecta para la fila 3, pasará por todas estas combinaciones para la fila 4. Y esto no es para mencionar el caso en el que el algoritmo se contradice en la fila 35 por un error que cometió en la fila 2.

Mi algoritmo era similar al de John. Falló al ejecutarse en modo x86 en mi escritorio de 64 bits. Cuando lo cambié al modo de 64 bits y lo dejé correr durante la noche, mi computadora estaba completamente inutilizable por la mañana. El proceso reservaba 8 Gigs of memory (8 Gigs Physical en el escritorio) y la computadora no respondía debido al frenético intercambio. Y ni siquiera había resuelto todas las filas posibles. Sin mencionar que ni siquiera había tocado las posibles combinaciones de columnas.

List<List<int>> rows =
                new List<List<int>>()
                {
                    new List<int> { 8,29,4 },
                    new List<int> { 6,4,25,4,3 },
                    new List<int> { 5,3,2,3,9,4,2,1,3 },
                    new List<int> { 4,2,2,2,2,1,2,2 },
                    new List<int> { 4,1,1,9,10,2,2,1 },
                    new List<int> { 3,2,6,5,5,1,1 },
                    new List<int> { 3,1,5,5,1,1 },
                    new List<int> { 3,1,4,4,1,1 },
                    new List<int> { 3,1,4,4,1,1 },
                    new List<int> { 3,1,3,3,1,1 },
                    new List<int> { 3,1,3,6,2 },
                    new List<int> { 3,1,2,3,2,4,2 },
                    new List<int> { 4,3,1,8,7,1,2,3 },
                    new List<int> { 4,2,1,12,11,1,2,4 },
                    new List<int> { 5,1,2,7,2,2,6,1,1,4 },
                    new List<int> { 4,1,1,1,6,2,2,6,1,2,1,3 },
                    new List<int> { 4,1,1,2,4,3,4,3,1,1,1,1,3 },
                    new List<int> { 4,1,1,2,1,4,1,2,3,2,1,2,2 },
                    new List<int> { 3,1,1,1,2,5,6,1,1,1,3,2 },
                    new List<int> { 3,2,1,1,2,1,5,4,4,2,1,2,1,2 },
                    new List<int> { 3,2,2,1,1,4,2,2,3,1,1,2,1,1,2 },
                    new List<int> { 3,1,3,2,1,1,4,1,5,3,2,1,3,1,2 },
                    new List<int> { 3,1,2,1,2,1,3,7,4,1,4,2,2 },
                    new List<int> { 2,1,4,1,1,1,2,6,2,2,2,3,2,1 },
                    new List<int> { 2,2,4,1,2,1,2,5,2,1,1,3,2,1 },
                    new List<int> { 2,2,1,4,1,1,3,3,2,1,4,4,1 },
                    new List<int> { 2,3,3,2,1,3,3,7,4,1 },
                    new List<int> { 2,3,2,4,5,8,1,2,1 },
                    new List<int> { 1,1,3,11,6,7,1,3,1 },
                    new List<int> { 1,1,2,2,13,10,2,3,2 },
                    new List<int> { 1,2,3,1,6,1,1,7,1,5,2 },
                    new List<int> { 1,1,3,2,6,1,1,1,1,4,1,4,2 },
                    new List<int> { 1,1,6,7,2,4,2,5,6,1 },
                    new List<int> { 1,1,2,3,1,4,2,2,11,2,1 },
                    new List<int> { 1,1,1,1,2,1,5,10,1,1,1 },
                    new List<int> { 1,1,1,1,4,7,4,10,1,1,1 },
                    new List<int> { 1,2,1,1,28,1,1,3 },
                    new List<int> { 1,2,1,2,27,2,1,3 },
                    new List<int> { 1,1,1,1,26,1,1,1,1 },
                    new List<int> { 2,3,1,28,2,1,2,1 }
                };
            List<List<int>> cols =
                new List<List<int>>()
                {
                    new List<int> { 40 },
                    new List<int> { 28,1 },
                    new List<int> { 23,8 },
                    new List<int> { 5,6,7,4 },
                    new List<int> { 3,6,1,9,3,1 },
                    new List<int> { 2,3,2,5,4,2,2 },
                    new List<int> { 1,2,4,1,2,5,2 },
                    new List<int> { 1,1,4,9,2,3,2 },
                    new List<int> { 2,4,2,6,1,4,3 },
                    new List<int> { 1,4,1,3,4,1,6 },
                    new List<int> { 1,4,3,2,3,5,5 },
                    new List<int> { 2,4,1,2,3,4,1,3 },
                    new List<int> { 1,2,3,4,2,2,4,4,1 },
                    new List<int> { 1,1,2,3,2,1,4,2,4 },
                    new List<int> { 2,3,5,3,3,5,4 },
                    new List<int> { 3,1,6,1,2,5,5 },
                    new List<int> { 3,2,6,2,15 },
                    new List<int> { 3,1,8,2,13 },
                    new List<int> { 2,2,4,5,15 },
                    new List<int> { 2,2,2,2,22 },
                    new List<int> { 2,1,1,1,12,6 },
                    new List<int> { 2,1,10,4,5 },
                    new List<int> { 3,1,3,1,2,4 },
                    new List<int> { 3,1,1,4,3,1,4 },
                    new List<int> { 3,2,2,3,2,2,5 },
                    new List<int> { 3,1,1,5,1,1,5 },
                    new List<int> { 3,1,1,5,1,1,5 },
                    new List<int> { 3,1,1,5,1,1,5 },
                    new List<int> { 3,2,5,2,1,1,4 },
                    new List<int> { 3,1,1,3,2,2,4 },
                    new List<int> { 3,1,6,4,5 },
                    new List<int> { 2,2,12,2,6 },
                    new List<int> { 2,2,1,1,22 },
                    new List<int> { 2,1,2,2,5,15 },
                    new List<int> { 3,1,4,3,2,14 },
                    new List<int> { 3,1,7,2,1,13 },
                    new List<int> { 3,2,6,1,1,6,8 },
                    new List<int> { 3,2,5,2,2,4,7 },
                    new List<int> { 2,1,2,4,1,1,1,4,1,4,2 },
                    new List<int> { 1,1,4,4,3,1,4,5,1 },
                    new List<int> { 1,1,5,1,1,2,1,2,2,3,2 },
                    new List<int> { 1,5,2,2,1,5,5,3 },
                    new List<int> { 1,6,2,1,4,2,6,1 },
                    new List<int> { 1,6,2,6,5,2 },
                    new List<int> { 1,5,3,1,9,2 },
                    new List<int> { 2,2,4,2,6,3 },
                    new List<int> { 1,2,2,2,9,2,1 },
                    new List<int> { 3,5,5,8,4 },
                    new List<int> { 4,13,9 },
                    new List<int> { 27,2 }
                };

Los derechos de autor van a Tampere Guild of Information Technology / Kaisapais / Una cervecería finlandesa.

Answer 2

Determinar si una solución de Nonogram existe / es única es NP-duro. Ver http://en.wikipedia.org/wiki/Nonogram#cite_note-0

Answer 3

En lugar de intentar colocar la "primera" fila, reducirá su búsqueda sustancialmente si intenta obtener información de la fila o columna "más restringida", que puede tener varios valores forzados. Una indicación rápida es sumar todos los valores en una fila / columna y agregar #_of_values ​​- 1, luego buscar la fila / columna con el mayor valor de este tipo (o la menor diferencia entre este valor y el número de filas o columnas, si las filas y columnas difieren). Por lo tanto, si tiene un rompecabezas de 25x25 y una de las filas es "5 1 1 6 1 1 3", esa fila tiene un valor de 24, lo que significa que está muy restringida: la posición relativa de todos menos uno de los cuadrados en blanco en esa fila se conoce, y el último cuadrado en blanco puede estar en cualquiera de las 8 posiciones relativas diferentes. Entonces, para cada grupo de cuadrados rellenos, solo hay dos posibilidades: el cuadrado en blanco adicional está a la izquierda de este grupo, o el cuadrado en blanco adicional está a la derecha de este grupo. Entonces, por ejemplo, cinco de los cuadrados rellenos en ese grupo de 6 ya son conocidos.

Una vez que tiene algunos valores forzados de una dirección, eso restringe aún más a cualquiera de los grupos de la otra dirección que se interseca con la información conocida. Por lo tanto, es probable que el mejor enfoque sea trabajar entre columnas y filas a medida que se conozca más información, que es prácticamente la forma en que necesita resolverlo a mano.

Answer 4

Este parece ser un caso bastante obvio para una primera búsqueda profunda con retroceso, como con el problema de "n queens". El tipo de parte linda es que, además de colocar filas / columnas, puedes desplazar los bloques.

Está bien, aquí hay un esquema.

1. Comience con un tablero vacío, coloque la primera fila

2. Ahora, con ese tablero, coloque una segunda fila, compárela contra las restricciones de la columna. Si pasa, intente recursivamente la siguiente fila contra ese estado; si no pasa, intente la siguiente ubicación posible de esa fila.

3. Si en algún momento te quedas sin las posibles ubicaciones de una fila que satisfacen las restricciones, entonces el enigma no tiene solución. De lo contrario, cuando te quedes sin rowns, habrás resuelto el problema.

Es conveniente que estas filas se puedan tratar como números binarios, por lo que hay un orden natural para las posibilidades.

Answer 5

Esto es lo que encontré:

Todos los problemas NP completos tienen la misma sensación. Siempre es fácil resolver el siguiente 80% de los casos restantes. Por ejemplo, los nanogramos se descomponen en una sola línea. Uno puede escribir una rutina, solve_one_line(old_state, line_definition, new_state) para actualizar lo que se conoce sobre una sola línea, y luego continuar iterando sobre filas y columnas. Luego falla en algunos casos, por lo que escribe algo para resolver el 80% de esos casos. Luego agrega números aleatorios y resuelve todos los casos que haya encontrado, pero es posible construir uno incorrecto.

Otros juegos que siguen este patrón son MineSweeper y Soduku .

Pensar en paralelo es difícil . Por ejemplo, podría darse cuenta de que la rutina solve_one_line anterior no afectará a otra fila si se ejecuta en una fila u otra columna si se ejecuta en una columna.

Ahora tienes:

  all_until_completion(rows):
      solve_one_line(...)
  all_until_completion(cols):
      solve_one_line(...)

Esto le permite ejecutar 20 núcleos (en un 20x20) sin bloqueo de datos ni nada. Entonces piensas en ejecutar en una tarjeta gráfica con cada celda un procesador. Entonces te das cuenta de cuánto tiempo ha pasado.

Una vez me sentí viejo mirando libros de texto de informática moderna donde la notación O (n) se reemplazó por la notación O (n, p) porque a nadie le importaría evaluar un algoritmo para un solo procesador. La solución de 8 reinas es un excelente algoritmo recursivo rápido con un uso de memoria eficiente y de falla rápida, y solo se ejecuta en un procesador.

Los problemas son buenas excusas para jugar . Moler más de lo mismo se vuelve aburrido. Mire a través de una lista de tecnologías con las cuales podría desear tener más experiencia: pruebas basadas en el comportamiento; inyección de dependencia; programación funcional pura; redes neuronales; algoritmos genéticos; rápido, descuidado y fuera de control; GPGPU; LOC; aprendizaje basado en ejemplos; crowdsourcing; etc. Elija uno y trate de usarlo de alguna manera para resolver el problema. A veces el objetivo no es resolver el problema, sino vagar por un territorio desconocido.

Contribuye con algo. * Esto puede ser un simple como un escrito. Mejor podría ser un depósito de cientos de nanogramos para que otros puedan jugar. [Déjame saber si existe un repositorio, de lo contrario haré uno]. Comience a contribuir tan pronto como tenga algo que encuentre limpio. Presta atención a las palabras klingon: Quizás hoy sea un buen día para morir; Yo digo que lo enviemos.

Entonces escriba soluciones paralelas y extrañas a los problemas de NP y compártalas. ¡Y ten un buen dia!

Answer 6

Hace unos meses escribí un solucionador para nonogramas en C ++. Solo busque todas las posiciones permitidas para celdas sombreadas y en blanco. Y en cada paso de la solución se ve si cada posición está bien. Así que aquí está el resultado para el nonograma de Chad Birch con el tiempo: http://i.stack.imgur.com/aW95s.png .

Y también probé mi solucionador para el nongram de Mikko Rantanen: http://i.stack.imgur.com/o1J6I.png .

Answer 7

No tengo suficiente tiempo ahora para desarrollar una solución, pero así es como lo abordaría.

"function1" determina las combinaciones posibles para una fila o columna dadas las restricciones de los números en la parte superior o lateral, y los cuadrados que ya están rellenados y los que se han vaciado.

"function2" toma la salida de function1 y, lógicamente, y todos los resultados juntos, los puntos con unos podrían completarse.

"function3" toma la salida de function1 y, lógicamente, o todos los resultados juntos, los puntos con ceros podrían vaciarse.

siga aplicando function2 y function3 a todas las filas y columnas hasta que no se vacíen ni rellenen más cuadros. Si se resuelve el enigma, habrá terminado.

Si el rompecabezas no se resuelve, tome una fila o columna que tenga la menor cantidad de posibilidades y aplique la primera posibilidad. Luego aplique function2 y function3 a la nueva tabla. Si conduce a una contradicción (0 posibilidades para una fila o columna), anule la posibilidad e intente una diferente. Sigue recurriendo así hasta que se encuentre una solución.

Answer 8

Permítanme señalar 2 giros interesantes en los rompecabezas clásicos de nonogramas:

• Cuando el rompecabezas hace más que simplemente listar longitudes de celdas ocupadas. Este desafío público limitó algunas celdas de antemano a estar ocupadas: http://www.gchq.gov.uk/press_and_media/news_and_features/Pages/Directors-Christmas-puzzle-2015.aspx

• Cuando el nonograma contiene más que solo celdas vacías / ocupadas, pero utiliza parches de diferentes colores para ocupar las celdas. Por ejemplo, ver http://onlinenonograms.com ; Al resolverlos a mano, tengo la sensación de que en realidad son más fáciles de resolver que los nonogramas normales.

Un desafío particular para los diseñadores de algoritmos es que los nonogramas coloreados se benefician enormemente de considerar juntas las restricciones horizontales / verticales. Los solucionadores habituales de línea por línea están claramente en desventaja aquí.

Answer 9

Sí, el problema es NP-completo, pero eso solo significa que estás (más o menos) atascado con tiempos de ejecución en crecimiento exponencial a medida que crece el tamaño del rompecabezas. Pero en la vida real los tamaños de rompecabezas no crecen. Casi nadie se molesta en construir rompecabezas que sean más grandes que 100x100 y la gran mayoría son más pequeños que 50x50. Construir un solucionador que resuelva el 95% de los enigmas publicados en libros y revistas en una fracción de segundo no es particularmente difícil. Un sistema de búsqueda primero en profundidad bastante sencillo lo hará.

Lo que es menos obvio es que hay una pequeña fracción de rompecabezas que son bastante desagradables y causarán que los tiempos de ejecución exploten para los solucionadores más simples. La mayoría de estos son rompecabezas mal diseñados que también son difíciles o imposibles de resolver para los humanos, pero algunos son rompecabezas especialmente inteligentes que los solucionadores humanos experimentados pueden resolver fácilmente, utilizando información más profunda que la que la mayoría de los programas de inteligencia artificial pueden manejar.

He escrito un solucionador propio que resolverá la mayoría de los enigmas muy rápidamente, y he realizado una encuesta de muchos otros solucionadores con resultados comparativos que comparan su rendimiento. También tengo una discusión de una clase interesante de rompecabezas difíciles (los rompecabezas de Domino) que demuestra cómo algunos rompecabezas que no son difíciles para un ser humano inteligente resultan muy difíciles para la mayoría de los programas. Los enlaces a mi solucionador y al rompecabezas de Domino se encontrarán en la encuesta.

Creo que todavía queda mucho por mejorar y animaría a las personas con ideas nuevas a que lo intenten. Pero vale la pena señalar que se han hecho las cosas obvias y que no hay mucho uso para volver a hacerlas.

Answer 10

Steven Simpson ha escrito un solucionador no programado que está disponible gratuitamente en diferentes versiones, incluido un script de JavaScript. Discute los detalles de los algoritmos en ese sitio web (como here , básicamente, está usando una serie de alineadores de líneas que intercambian velocidad frente a integridad, junto con dividir y conquistar al adivinar cuando todos los alineadores de líneas alcanzan un punto muerto. También tiene vínculos A otros enfoques, que cubren más terreno del que tenemos aquí.