En Math Stack Exchange, hice una pregunta sobre la región más pequeña que puede contener todos los n-ominos gratuitos .
Me gustaría agregar esta secuencia a la Enciclopedia en línea de secuencias enteras una vez que tenga más términos.
Ejemplo
Una región de nueve celdas es el subconjunto más pequeño del plano que puede contener los doce 5 ominoes libres , como se ilustra a continuación. (Un poliomino libre es uno que se puede girar y voltear).
(Una región de doce celdas es el subconjunto más pequeño del plano que puede contener los 35 6 ominoes libres ).
El reto
Calcule los límites superiores en las regiones más pequeñas del plano que pueden contener todos los n-ominoes en función de n.
Tal mesa comienza:
n | size
--+-------
1 | 1*
2 | 2*
3 | 4*
4 | 6*
5 | 9*
6 | 12*
7 | 37
8 | 50
9 | 65
*These values are the smallest possible.
Presentación de ejemplo
1-omino: 1
#
2-omino: 2
##
3-omino: 4
###
#
4-omino: 6
####
##
5-omino: 9
#
#####
###
6-omino: 12
####
######
##
7-omino: <= 37
#######
######
######
######
######
######
Tanteo
Ejecute su programa todo el tiempo que desee y publique su lista de límites superiores junto con las formas que logran cada uno.
El ganador será el participante cuya tabla sea lexicográficamente la más temprana (con "infinito" adjunto a las presentaciones más cortas). Si dos participantes presentan los mismos resultados, entonces la presentación anterior gana.
Por ejemplo, si las presentaciones son
Aliyah: [1,2,4,6,12,30,50]
Brian: [1,2,4,6,12,37,49,65]
Clare: [1,2,4,6,12,30]
entonces Aliyah gana. Ella vence a Brian porque 30 <37, y ella vence a Clare porque 50 <infinito.
fuente
Respuestas:
C # y SAT: 1, 2, 4, 6, 9, 12, 17, 20, 26, 31, 37, 43
Si limitamos el cuadro delimitador, hay una expresión bastante obvia del problema en términos de SAT : cada traducción de cada orientación de cada poliomino libre es una gran conjunción; para cada poliomino formamos una disyunción sobre sus conjunciones; y luego requerimos que cada disyunción sea verdadera y que el número total de celdas solía ser limitado.
Para limitar el número de celdas, mi versión inicial creó un sumador completo; luego usé la ordenación bitónica para el conteo unario (similar a esta respuesta anterior pero generalizado); finalmente me decidí por el enfoque descrito por Bailleux y Boufkhad en la codificación Eficiente CNF de las restricciones de cardinalidad booleana .
Quería hacer que la publicación fuera autónoma, así que desenterré una implementación en C # de un solucionador SAT con una licencia BSD que era de última generación hace unos 15 años, reemplacé su implementación de la lista NIH con
System.Collections.Generic.List<T>
(ganando un factor de 2 en velocidad), jugaron desde 50kB hasta 31kB para ajustarse al límite posterior de 64kB, y luego hicieron un trabajo agresivo para reducir el uso de memoria. Este código obviamente se puede adaptar para generar un archivo DIMACS que luego se puede pasar a solucionadores más modernos.Soluciones encontradas
Para encontrar 43 para n = 12 tomó un poco más de 7,5 horas.
Código Polyomino
Código solucionador SAT
Óptima
El código anterior sigue reduciendo el tamaño objetivo hasta que encuentra una restricción insatisfactoria, por lo que garantiza que el resultado sea óptimo (bajo el supuesto del cuadro delimitador) hasta e incluyendo . Sin embargo, se queda sin memoria (3 GB para un proceso de 32 bits o 4 GB para un proceso de 64 bits) con después de producir una región con un peso 43.n=11 n=12
Para ejecutar la búsqueda de hasta su finalización, encontré que era necesario reducir considerablemente la memoria, cláusulas binarias de mayúsculas especiales y no mantener listas de vigilancia vacías. Sin embargo, al cambiar el orden en el que se consideran las cláusulas, cambia los resultados, por lo que presento el cambio como un parche y dejo la lista de soluciones anteriores sin tocar.n=12
Distintas soluciones
Contar soluciones a un problema SAT es sencillo, aunque a veces lento: encuentra una solución, agrega una nueva cláusula que lo descarta directamente y vuelve a ejecutar. Aquí es fácil generar la clase de soluciones de equivalencia bajo las simetrías del rectángulo, por lo que el siguiente código es suficiente para generar todas las soluciones distintas.
Esto puede ser útil para que las personas generen o prueben hipótesis sobre la estructura "típica" que puede guiar las búsquedas de más alto .n
fuente
En aras de comenzar el proceso, aquí hay una respuesta rápida (pero no muy óptima).
Modelo:
Tome un triángulo con longitud n - 1, pegue un cuadrado adicional en la esquina y corte el cuadrado inferior.
Prueba de que todos los n-ominos encajan:
Tenga en cuenta que cualquier n-omino puede caber en un rectángulo con largo + ancho como máximo n + 1.
Si un n-omino cabe en un rectángulo con largo + ancho como máximo n, cabe muy bien en el triángulo (que es la unión de todos esos rectángulos). Si utiliza el cuadrado de corte, su transposición se ajustará al triángulo.
De lo contrario, tenemos una cadena con como máximo una rama. Siempre podemos colocar un extremo de la cadena en el cuadrado adicional (demuestre esto con el trabajo de caso), y el resto cabe en un rectángulo con longitud + ancho como máximo n, reduciéndose al caso anterior.
El único caso en el que lo anterior no funciona es el caso en el que usamos tanto el cuadrado extra como el cuadrado de corte. Solo hay uno de estos n-omino (la L larga), y ese cabe dentro del triángulo transpuesto.
Código (Python 2):
Mesa:
fuente
C #, puntaje: 1, 2, 4, 6, 9, 12, 17, 20, 26, 31, 38, 44
El formato de salida del programa es un poco más compacto.
Esto utiliza un enfoque aleatorio sembrado, y he optimizado las semillas. Ejecuto una restricción de cuadro delimitador que es plausible y consistente con los datos conocidos para valores pequeños de n. Si esa restricción es realmente válida, entonces
1, 1, 2, 2, 2, 6, 63, 6
.Demostración en línea
fuente
Colocación codiciosa en orden aleatorio
Las regiones encontradas se dan a continuación, así como el programa de óxido que las generó. Llámelo con un parámetro de línea de comando igual a la n que desea buscar. Lo he ejecutado hasta n = 10 hasta ahora. Tenga en cuenta que aún no está optimizado para la velocidad, lo haré más tarde y probablemente acelere mucho las cosas.
El algoritmo es sencillo, barajo los polyominoes en un orden aleatorio (sembrado), luego los coloco uno a la vez en la posición con la superposición máxima posible con la región hasta el momento. Hago esto 100 veces y obtengo la mejor región resultante.
Regiones
Programa
Nota: requiere todas las noches, pero solo cambia la siembra para deshacerte de eso, si te importa.
fuente