Solitario de rayas V: Simetrías

He modificado el programa para que vaya escribiendo en un fichero el vértice del árbol que está explorando cada vez que explore diez millones de vértices (esto es unos dos o tres minutos). Así puedo interrumpir y rearrancar la búsqueda. Uno podría pensar que esto es necesario por si los apagones, pero no, la experiencia demuestra que el factor limitante aquí son las actualizaciones de Windows: cada semana mi ordenador se tiene que bajar una actualización de seguridad crítica doble rojo fosforito, y luego se reinicia.

El poder empezar a calcular a partir de una figura guardada en disco tiene una importante ventaja, y es que seleccionando varias figuras desde las que empezar podemos recorrer sólo las soluciones realmente diferentes del problema, en vez de recorrer todo el árbol ocho veces a causa de las simetrías.

Por "simetrías" me refiero a dos reflexiones (horizontal y vertical) y una la rotación de 90 grados (rotar 180 grados equivale a reflejar primero horizontalmente y luego verticalmente).

Es decir, estas dos figuras no son iguales entre sí porque no se puede convertir la una en la otra aplicando simetrías

pero estas ocho sí:

porque podemos convertir cualquiera de ellas en las otras aplicando simetrías.

(Por cierto, ¿habrá alguna figura no trivial que bajo una traslación vaya a parar a alguna figura simétrica? Es decir, que permanezca esencialmente invariante bajo una traslación. Es una pregunta tan inútilmente retorcida que lo mismo la pensaré; parte del problema será definir qué significa "no trivial", porque hay figuras así con hasta cuatro rayas.)

La mayoría de las figuras aparecerá por octuplicado, pero algunas figuras tienen alguna simetría (es decir, al aplicarles una de las simetrías caen exactamente sobre sí mismas) y aparecerán cuatro, dos, o incluso una única vez; por ejemplo:

Lo que interesa para ahorrar tiempo es no encontrar ocho veces las figuras que no tienen ninguna simetría; parece razonable pensar que las figuras con alguna simetría serán una minoría minúscula, y por tanto no nos preocuparemos de ellas.

¿Qué tiene todo que ver con leer de un fichero en el disco duro la posición desde la que se debe continuar la búsqueda? Bueno, imaginemos que queremos buscar algo en todas las figuras que tienen exactamente una de las ocho rayas de la izquierda (se ven sólo "cuatro rayas largas" porque las ocho se solapan a pares). Entonces arrancaríamos el programa empezando desde la posición de la izquierda, en la que la raya verde estaría incluida y las seis rayas negras estarían excluidas, es decir, en la lista de rayas que no se deben incluir:

Cualquier figura que tenga exactamente una de las ocho rayas podrá ser rotada y reflajada de una única manera para coincidir con estas condiciones. No es necesario indicar que la última raya (arriba a la derecha) no debe ser incluida, porque al tener que incluir la de la izquierda ya lo impedimos.

Esto funciona muy bien para el caso en que haya una única raya de esas ocho, ¿pero qué ocurre si hay dos o más, o ninguna? Me equivoqué al decir que debería ser fácil evitar todas las figuras duplicadas, porque los otros casos han resultado ser complicadillos, y hay que empezar a subdividirlos.

Es decir: el problema general, buscar en todas las figuras, primero lo dividimos en cinco casos, y cada uno de estos casos lo subdividimos en los subcasos que sean necesarios:

1. Las figuras que tienen exactamente una de las ocho rayas. Es el caso bonito, analizado arriba, y sólo requiere un subcaso sin simetrías.
2. Las figuras que no tienen ninguna de las ocho rayas. Tiene un subcaso muy trivial en el que no ganamos nada porque todas sus figuras siguen apareciendo por octuplicado.
3. Las figuras que tienen exactamente dos de las ocho rayas. Tiene cinco subcasos, cuatro de ellos con simetrías, mencionados más abajo.
4. Las figuras que tienen exactamente tres de las ocho rayas. Tiene tres subcasos sin simetrías.
5. Las figuras que tienen exactamente cuatro de las ocho rayas. Tiene cuatro subcasos, uno con una simetría y otro con dos.

(No es posible tener más de cuatro de esas rayas porque cada vez que incluimos una, excluimos otra.)

Por ejemplo, el caso en que haya exactamente dos de esas ocho rayas puede ser subvidivido ineficientemente en estos cinco subcasos, de los que cuatro tienen simetrías (indico en azul el eje de simetría):

Obviamente, es malo que los subcasos que vayamos a usar tengan simetrías, porque permitirán que algunas figuras encajen en ellas de varias maneras.

Una forma de arreglar esto sería dividir estos subcasos con simetrías en más sub-subcasos, pero de todas formas no nos acabamos de librar de las simetrías.

¿Es esto muy malo? He echado unas cuentas suponiendo que la probabilidad de que aparezca una línea en un par de líneas solapadas es 1/3, y la probabilidad de que no aparezca ninguna es 1/3. Esto es muy discutible, pero como he construido los casos usando las primeras líneas, que "normalmente se ponen", no parece del todo equivocado. Me sale esta tabla, donde "m" se refiere al trabajo mínimo, es decir, el número de vértices que se explorarían si se evitasen todas las epeticiones:

número de casos	trabajo total	trabajo repetido
1 caso	m * 8	m * 7
14 casos	m * 1,4321	m * 0,4321
36 casos	m * 1,1728	m * 0,1728
93 casos	m * 1,0795	m * 0,0795
235 casos	m * 1,0387	m * 0,0387
579 casos	m * 1,0192	m * 0,0192

Uf. Bueno, a pesar de sean números aproximados, sugieren que el trabajo duplicado es proporcional al logaritmo del número de casos dividido entre el número de casos.

No me veo arrancando un programa 579 veces para ahorrarme un 2% de trabajo, hay algo contradictorio en esta frase. De repente, la opción de dejar que el ordenador trabaje por octuplicado no parece tan mala. A menos que aparezcan cientos de voluntarios pidiendo ramas para buscar en paralelo, me parece que intentaré dividir el problema en 14 casos, y ya está.

Quizás las cosas no tengan que ser tan complicadas; yo he examinado los casos a partir de esas ocho rayas iniciales, pero ¿sería posible escoger otras rayas que hiciesen más fácil el análisis? Quién sabe; yo las he buscado y no las he encontrado. Por feo que parezca todo esto, me temo que es lo que hay.