¿Cuál es el algoritmo eficiente para resolver rompecabezas Jigshaw?

Question

Ayer solo estaba jugando Jigshaw Puzzle y de alguna manera me pregunté cuál sería el algoritmo para resolverlo.

Como humano, pasos que he seguido donde:

1. independiente todas las piezas en 3 partes, borde plano único, doble borde plana y ningún borde en absoluto.
2. piezas de borde plana separados, ya que sería esquinas de imagen
3. piezas de borde individual por separado, ya que formarían 4 bordes extremos de imágenes
4. Por último, las piezas sin bordes formarían interna de la imagen.
5. Haga coincidir las piezas de color e imagen para unir las piezas.

Me preguntaba cuál sería el algoritmo eficiente para resolver este rompecabezas de manera eficiente y qué estructura de datos proporcionaría una solución óptima y eficiente.

Gracias.

Answer 1

Resolver problemas como este puede ser engañosamente complicado, especialmente si no se imponen restricciones en el tamaño y la complejidad del rompecabezas.

Aquí están mis pensamientos sobre un enfoque para escribir un programa para resolver un rompecabezas como este.

Hay cuatro piezas clave de información que se pueden utilizar de forma individual y en conjunto como pistas para resolver un rompecabezas:

1. La información de la forma de cada una de las piezas (cómo aparecen sus bordes)
2. El información de color de cada una de las piezas (las adyacentes generalmente tendrán transiciones suaves)
3. La información de orientación de cada pieza (donde pueden encontrarse los bordes planos y de esquina)
4. El tamaño total y el número de piezas proporcionan las dimensiones generales o f el rompecabezas

Entonces, ¿qué tipo de información se suministrará el programa? Supongamos que cada pieza del rompecabezas es una pequeña imagen rectangular con información de transparencia utilizada para identificar la parte del rompecabezas que representa bordes no rectangulares .

A partir de esto, es relativamente fácil identificar las cuatro esquinas (en una sierra de calar típica). Estos tendrían exactamente dos bordes que tienen contornos planos (ver el mapa de contorno a continuación).

A continuación, construiría información sobre la forma de cada uno de los cuatro bordes de una pieza del rompecabezas. Esta información se puede usar para construir un adjacency matrix que indique qué piezas encajan juntas.

Ahora podemos podar esta matriz de adyacencia para identificar solo aquellas piezas que tienen transiciones de color suaves en su configuración adyacente. Esto es algo complicado porque requiere un nivel de concordancia difusa, ya que no todos los límites de píxel a píxel necesariamente tendrán una transición de color uniforme.

Usando las cuatro piezas de esquina originalmente identificadas, ahora deberíamos poder reconstruir las dimensiones y las posiciones de todas las piezas del rompecabezas.

Una estructura de datos conveniente para representar formas de borde puede ser un mapa de contorno, esencialmente un conjunto de enteros que representan los deltas incrementales en distancia desde el lado opuesto de la imagen hasta el último píxel no transparente en cada uno de los cuatro lados la pieza del rompecabezas. Las piezas que coinciden deben tener mapas de contorno de imagen especular.

Answer 2

Suponiendo que no vamos a entrar en ninguna materia visión artificial, sería muy pequeñas variaciones en la búsqueda de la totalidad del espacio del problema, es decir, tratar cada pieza hasta que uno se ajusta y se repite. La principal optimización sería no intentar la misma pieza en el mismo lugar si sabes que no encaja. Las piezas laterales/esquineras son relativamente pocas y probablemente no se podrían considerar en ninguna optimización importante.

La estructura de datos probablemente sea algo así como una matriz hash, donde puede comprobar rápidamente si ya ha probado una pieza en una posición.

Una optimización fácil que incluye visión artificial sería probar piezas en cada posición después de clasificar las piezas por lo cerca que el color promedio coincide con las posiciones adyacentes.

Esto por encima de mi cabeza, por supuesto.

Answer 3

Asegúrese de escanear las partes macho/hembra de una pieza; esto reducirá la búsqueda a la mitad.

Answer 4

No creo que la forma humana sea tan útil para una implementación: una computadora puede ver todas las piezas muchas veces por segundo y no veo una victoria (grande) clasificando las piezas en esquina, borde y piezas interiores, especialmente porque solo hay tres categorías y tienen tamaños muy diferentes.

Dado un conjunto de imágenes de todas las piezas, trataría de derivar un descriptor simple para cada pieza o borde. El descriptor debe contener información sobre la forma aproximada y el color de la pieza, respectivamente, los cuatro bordes. Dado un rompecabezas con 1000 piezas, hay 4000 bordes y siempre dos deben ser iguales (ignorando el borde del rompecabezas). En consecuencia, el descriptor debe ser capaz de distinguir 2000 bordes que requieren al menos 11 bits.

La división de una sola pieza en un patrón de tablero de verificación de 3 x 3 con nueve campos dará tres colores por filo - con ocho bits por canal ya tenemos 72 bits. Primero tendí a sugerir reducir la resolución del color, pero parece que esta no es una buena idea, por ejemplo, un cielo azul podría beneficiarse de una resolución de color alta. Tenga en cuenta que el cálculo de los colores probablemente requiera separar la pieza del fondo e intentar alinear los bordes con los ejes horizontal y vertical.

En áreas muy uniformes como cielos azules, la información de color probablemente no sea suficiente para encontrar coincidencias buenas y se requerirá información geométrica adicional. Intentaré describir la forma del borde por su curvature o una medida derivada. Tal vez muestreado de diez a veinte puntos por borde. Probablemente esto también dependa de la separación de fondo y la alineación de los bordes.

Finalmente, la computadora puede hacer la parte fácil: compare todos los pares de descriptores de borde y encuentre las mejores coincidencias. Este proceso probablemente debería controlarse para volverse más local en lugar de la mejor coincidencia simple primero, porque cuando hayas encontrado una esquina (¿palabra correcta en inglés? Quiero decir tres en forma de L.) tienes dos bordes que limitan la pieza para encontrar y uno puede realizar un seguimiento temprano si no se puede encontrar una buena coincidencia (lo que indica un error anterior o un acertijo difícil).

Answer 5

Pasando por encima de esto, pensé en una solución interesante que la soluciona al aumentar los costos en una serie de pasos.

1. independiente todas las piezas del rompecabezas en grupos de dos. Prueba para ver si encajan. Si no, pruebe con una pieza diferente que no haya visto antes. Si lo hace, coloque el conjunto en una pila correcta. Repita hasta que todos los conjuntos de dos hayan encontrado una coincidencia.

2. De la pila correcta combine el conjunto de dos para hacer un conjunto con conjuntos de dos, es decir {{1,2}, {5,6}}. Vea si al menos una pieza del rompecabezas de un conjunto de dos se ajusta con al menos otra pieza del otro conjunto de dos. Si no, pruebe con un conjunto diferente de dos que no haya visto antes. Si lo hace, combine los dos conjuntos en un conjunto de cuatro en la orientación correcta con la pieza que encontró para encajar y poner el conjunto combinado en una pila correcta. Repita hasta que se hayan encontrado todos los conjuntos de cuatro.

3. Repita los pasos hasta el problema final donde el conjunto n/2 se combina con el conjunto n/2.

No es positivo el tiempo de cálculo para esto.