Emparejar pentominós en un cubo de 5x5x5

Question

Tengo este rompecabezas de madera compuesto por 25 formas de Y pentominoes donde el objetivo es ensamblarlas en un cubo de 5x5x5. Después de pasar bastantes horas intentando resolver el rompecabezas sin éxito, finalmente me di por vencido y escribí un programa para probar todas las combinaciones posibles utilizando el backtracking. El análisis de los resultados reveló que, por cada solución encontrada, el ordenador realizaba -de media- 50 millones de colocaciones y retiradas de piezas. Evidentemente, esto está más allá de mis capacidades como humano, incluso si puedo ver con unos pocos pasos de antelación que una solución parcial lleva a un "callejón sin salida".

Así que mi pregunta es la siguiente: dado que el rompecabezas es tan simétrico, ¿hay alguna manera de podar significativamente el árbol de búsqueda (tal vez incluso haciendo posible que yo resuelva el rompecabezas por mi cuenta)?

(perdón por la mala calidad)

Answer 1

Consiga Herramientas de fresado . Se tarda menos de un minuto en configurar este problema, y luego unos minutos en generar 1264 soluciones. No estoy seguro de si eso son todas las soluciones, el solucionador me dice que ahora se necesitan 22 minutos para comprobar completamente el espacio de soluciones. (EDIT -- Tiempo total de resolución = 24,8 minutos)

Un problema algo más interesante es el de 25 N pentominos en un cubo. Hay 4 soluciones, encontradas en 2,6 minutos. Muchos otros rompecabezas interesantes están recopilados en Se jugarán rompecabezas

Answer 2

En el WhereCampPDX de este año, varios representantes de OpenStreetMap afirmaron que el uso de los datos de OSM para las rutas es bastante común en Europa. Sin embargo, es más raro en los Estados Unidos porque el mapa no suele ser lo suficientemente bueno. Puedes consultar un servicio de enrutamiento basado en OSM en

http://openrouteservice.org/

Answer 3

Aunque hablas de podar el árbol de búsqueda a través de la simetría, por lo general la mejor manera que he visto de abordar estos problemas es dividiendo las celdas en clases o capas; por ejemplo, muchos de los problemas clásicos de poliominós que no son de baldosas pueden resolverse con coloraciones adecuadas, y las restricciones proporcionadas por las coloraciones pueden ayudar a reducir el espacio de búsqueda inmensamente (por ejemplo, el resultado del cubo Soma de que la pieza 'T' debe tener su columna vertebral en una arista del cubo). Lo que salta a la vista es la capa "intermedia" de celdas, las 26 celdas que no están ni en la cara más externa del cubo ni en la celda central. Cualquier pieza que ocupe el centro debe ocupar también al menos (y de hecho, exactamente) tres de estas celdas, y cualquier pieza que no esté totalmente en una capa exterior ocupa al menos una, con muchas colocaciones que obligan a ocupar varias celdas; intuitivamente, parece que podrían ser un bien escaso y que es una restricción que merece la pena investigar. La sección sobre el cubo Soma en el último volumen de Formas de ganar sus juegos matemáticos tiene una discusión sobre este tipo de coloraciones, y podría ser un buen lugar para empezar.

Answer 4

Me he dado cuenta en un 80% de que esta respuesta puede tener demasiadas partes para ponerla en práctica, así que también voy a dejar una más corta.

Si se prioriza el llenado de algunas celdas sobre otras, al menos se puede podar el árbol de búsqueda del ordenador. Sugiero llenar el cubo central, seguido por los centros de las seis caras, seguido por las ocho esquinas, terminando con todo lo demás.

Aquí, déjame numerar los cuadrados de un pentominó en Y:
1
23
4
5
Al comenzar con la Y llenando el cubo central, el espacio de búsqueda puede reducirse en un factor de 12 manteniendo constante la orientación de esta pieza. Nótese que sólo las celdas 2, 3 y 4 pueden ocupar el centro del cubo. Si 2 o 4 es la celda central, entonces quedarán cinco centros de caras por llenar; si es 3, entonces quedarán los seis.

Para los cinco o seis centros, la Y que ocupa cada centro puede colocarse de una de las 36 maneras siguientes, sin tener en cuenta el solapamiento:

-La "columna vertebral" (los cubos 1245) puede apuntar en cualquiera de las cuatro direcciones
-De nuevo, sólo 2, 3 o 4 pueden llenar estos cubos
-La Y completa puede estar en la cara de tres maneras para cada cubo: en cualquiera de las caras de la Y para los tres, además de a lo largo de la columna vertebral para el 2 y el 4 o a lo largo de la cara opuesta más lejana para el 3

Ahora las ocho esquinas. Sólo 1 y 5 pueden ocupar estos cubos, así que para cada una de estas esquinas podemos trabajar en colocaciones parciales sólo para las espinas a lo largo de los bordes. Ahora, cada esquina es adyacente a tres aristas de tres cuadrados, aunque algunas de las doce aristas están ciertamente ocupadas en parte por las Y colocadas en la fase anterior. Las esquinas que hay que rellenar tienen que ser priorizadas por el menor número de aristas disponibles.

-Si, en cualquier punto, una esquina sin rellenar tiene 0 aristas libres, entonces hay que avanzar a la última "colocación temporal de aristas" o a toda la configuración cara-centro
-Cuando se coloca una pieza de esquina a lo largo de una arista y la otra esquina que comparte esa arista aún no se ha llenado, esa otra esquina debe volver a ser priorizada por tener una arista libre menos
-Si alguna esquina sin rellenar sólo tiene un borde libre, se coloca un lomo a lo largo de esa esquina y borde
-Y si ninguna esquina sin rellenar tiene menos de dos aristas libres, escoge y anota una "colocación temporal de aristas" para arreglar si lleva a una contradicción. (Garantizo que al menos dos esquinas no tendrán más de dos aristas. Si la primera colocación es incorrecta, la segunda colocación debe ser utilizada pero no anotada como temporal).

Esto da ocho colocaciones parciales y seis o siete colocaciones totales. Esto deja once o diez Y's para colocar dentro de un volumen de 63 o 58, respectivamente, que incluye al menos 26 cubos que no se llenan en absoluto independientemente de cómo se coloquen exactamente las Y's de las esquinas (cada una sigue teniendo hasta cuatro posibilidades para la colocación del cubo 3), un espacio de búsqueda mucho más pequeño.

Answer 5

Para una ruta de solución más sencilla, sugiero de nuevo rellenar primero el cubo central para reducir las simetrías, pero asegúrate de que el cubo 1 o 5 está en la capa superior (o inferior, dependiendo de cuál quieras rellenar primero). A continuación, puede llenar la primera capa (posiblemente dando prioridad a las esquinas), seguido por las capas posteriores.