Solitario de rayas VIII: Record con 110 rayas

Usando el primer acotador, tras 2,1 días de CPU, y buceando hasta el nivel 134 del árbol binario, se ha encontrado este bicho con 110 rayas:

Se exploraron 10.201.449.392 vértices, se llamó al acotador 1.886.323.606 veces, y se podaron 1.459.117.650 ramas. La posición de esta figura en el árbol es 1111111111 1111111111 1111111111 0111111011 1110110111...; es decir, apenas se ha avanzado, tras dos días de CPU sigue en el bit 44 (42 efectivos), luego a este ritmo puede tardar unos 25.300 millones de años en acabar. Antes parecía que iba a bastar con la edad del universo, pero esto está empeorando.

Solitario de rayas VII: El primer acotador

Tengo que empezar admitiendo que medio he hecho trampas al poner este título; en realidad, ya he probado el primer acotador, así que ahora ya sé que habrá (al menos) un segundo acotador.

La idea es simple; este acotador funcionará en dos etapas:

1. añadir todos los puntos que se pueda.
2. averiguar el número máximo de rectas que pueden cubrir los puntos.

Ese "todos los puntos que se pueda" se complica un poquito. En realidad, el criterio que usa este acotador no es para añadir puntos, sino para añadir rayas; lo que pasa es que en cuanto decida añadir una raya, se va a olvidar de ella y va a añadir sus puntos. Éste es el criterio exacto:

1. Las rayas añadidas no pueden "pisar" las rayas que había puestas antes de llamar al acotador (sí pueden pisar las rayas puestas por el acotador)
2. Si la raya que se va a añadir tenía exactamente cuatro puntos marcados anteriormente, ninguno de estos puntos puede satisfacer:
   1. haber sido añadido por el acotador;
   2. tener todos sus enlaces usados en la dirección de la raya (en cualquiera de los dos sentidos);
   3. y tener al menos uno de esos enlaces pisado por la raya.

Como siempre, un ejemplo dejará claro qué quiere decir esto. Imaginemos que tenemos que acotar el número de rayas que se pueden añadir a esta figura:

Podríamos añadir una raya que cogiese el punto de la derecha, o otra que cogiese el de la izquierda, pero no ambas rayas. Bueno, pues este acotador en realidad no recuerda si ha añadido una raya o no, lo que ve es que podría añadir cualquiera de ellas, y va a añadir los dos puntos.

Hay que aclarar una cosa; si vemos sólo los puntos, ahora parecería que podríamos añadir dos rayas más, y luego otras dos, y luego otras dos... pero claro, esto haría que añadiésemos infinitos puntos, y no sería muy útil que nuestro acotador dijera siempre "como mucho puedes añadir infinitas rayas". Así que el acotador tiene que recordar cuándo no debe continuar añadiendo puntos. El criterio retorcido de arriba impide esto (si fuésemos a añadir una nueva raya, nos encontraríamos con que tendría 4 puntos marcados previamente y los puntos ahora en los extremos habrían sido añadidos por el acotador, tendrían su único enlace usado en la misma dirección de la nueva raya, y este enlace sería pisado por la nueva raya).

Entonces viene la segunda etapa del acotador. Tenemos seis puntos en fila; ¿cuántas rayas puede haber ahí? Obviamente, sólo una. Para poder poner dos rayas tendría que haber 9 puntos en fila.

Y ya hemos acabado; la cota es uno.

Lo bonito de este algoritmo es que hemos acotado el número de rayas que podemos añadir sin haber decidido qué rayas añadir. Lo malo es que a veces esta estimación va a ser muy mala. Veamos un ejemplo en que el acotador nos cuela una raya de propina; empezamos con esta figura:

El primer punto que añadiremos será S; de hecho, podemos hacerlo de dos formas, uniendo P-R o Y-N. Supongamos que unimos los puntos P-R, y por tanto el acotador recuerda (por el criterio) que no puede continuar añadiendo puntos en esa dirección, así que, de momento, U no se puede añadir.

Una vez hemos añadido S, resulta que podemos añadir T, uniendo Z-S.

Y sorpresa, ahora el criterio nos deja añadir U, porque resulta que ahora no todos los enlaces usados de S están en la misma dirección. Es decir; mientras conocíamos una única forma de llegar a S, el criterio nos impedía continuar en esa dirección; pero una vez hemos llegado a S en dos direcciones (desde N y R), como no se puede saber cual es "la primera", tenemos que dejar continuar en las dos direcciones.

Total, estamos en que el acotador ha descubierto que puede llegar a los puntos S, T y U. Esto es correcto, salvo por el detalle de que por las incompatibilidades entre rayas, se puede añadir o bien T o bien U, pero no ambos. Da igual, este acotador no recuerda incompatibilidades entre rayas. Así que a continuación decide que también puede añadir X; lo único que hay que hacer es añadir la raya T-X. Lo cual es falso...

Y entonces el acotador llega a su segunda etapa; estos son los puntos alcanzables:

que pueden albergar como mucho tres rayas; una horizontal (que se podría escoger de dos formas), una vertical, y una diagonal (que se podría escoger de dos formas). De forma que el acotador dirá que se pueden añadir como mucho 3 rayas cuando, en realidad, el máximo son dos rayas.

¿Es esto muy malo? Bueno, ya sabemos que un acotador rápido no puede ser muy preciso, así que si este acotado nos clavase sólo una raya de más estaríamos muy contentos. El problema es que una vez que empieza a añadir rayas incorrectamente se desboca y acaba añadiendo infinitas rayas incorrectas. Veamos un ejemplo "real"; empezamos con esta figura:

         *        *         
         |\      /|         
         | \    / |         
      *--#--#--#--#         
         |   \/   |         
         |   /\   |         
         #  *  *  #         
         | /    \ |         
         |/      \|         
         #        #         
        /|        |\        
       / |        | \       
#  #  #  #        #  #  #  #
                            
                            
#                          #
                            
                            
#                          #
                            
                            
#  #  #  #        #  #  #  #
                            
                            
         #        #         
                            
                            
         #        #         
                            
                            
         #  #  #  #         

(Perdón por volver a los gráficos en ASCII, pero es que la salida del acotador no la preparado para matlab...)

Vale, el acotador hace una primera pasada y encuentra que podría añadir 37 puntos:

            B        B            
            |\      /|            
            | \    / |            
         B--#--#--#--#            
            | / \/ \ |            
            |/  /\  \|            
         @--#--B--B--#--@         
           /| /    \ |\           
          / |/      \| \          
   @     B  #        #  B     @   
   |    /  /|        |\  \    |   
   |   /  / |        | \  \   |   
@--#--#--#--#--B--B--#--#--#--#--B
   | /                      \ | / 
   |/                        \|/  
   #                          #   
  /|                         /|\  
 / |                        / | \ 
@  #        @        B--B--B--#--B
   |\       |        |    /  /|   
   | \      |        |   /  / |   
@--#--#--#--#--B--B--#--#--#--#--@
   |   \    |     |  | /  /   |   
   |    \   |     |  |/  /    |   
   @     B--#--B--B--#--B--B--B--@
          \ |     | /| /          
           \|     |/ |/           
            #     B  #            
            |\   /| /|            
            | \ / |/ |            
         @--#--#--#--#--@         
            | / \/|  |            
            |/  /\|  |            
         @--B--B--B--B--@         

Pero claro, una vez ha añadido estos puntos, podría usarlos para añadir nuevas rectas; en la segunda pasada, el acotador cree que puede añadir estos 132 puntos:

            B  B  @  B  B               
            |\/|\  \/|\/|               
            |/\| \ /\|/\|               
            B--#--#--#--#  @            
           /|  |\/ \/|\/|\ |            
          / |  |/\ /\|/\| \|            
   B--B--B--B--#--B--B--#--B--B  B  B  @
    \ | /   |\/|\/ \/|\/|\/|\/| /| /| / 
     \|/    |/\|/\ /\|/\|/\|/\|/ |/ |/  
@     B--B--B--#--B--B--#--B--B--B--B--B
 \   /|\ |\/|\/|\/|\/|\/|\/|\/|\/| /| / 
  \ / | \|/\|/\|/\|/\|/\|/\|/\|/\|/ |/  
@--B--#--#--#--#--B--B--#--#--#--#--B--B
  / \ |\/|\/|\/|\/|\/|\/|\/|\/|\/|\/| / 
 /   \|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/  
B--B--#--B--B--B--B--B--B--B--B--#--B--B
 \ |\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/| /|
  \|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/ |
B--B--#--B--B--B--B--B--B--B--B--#--B--B
 \ |\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|
  \|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|
B--B--#--#--#--#--B--B--#--#--#--#--B--B
 \/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|
 /\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|
B--B--B--B--B--#--B--B--#--B--B--B--B--B
|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|
|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|
B--B--B--B--B--#--B--B--#--B--B--B--B--B
| /|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\ |
|/ |/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\| \|
B--B--B--B--B--#--#--#--#--B--B--B--B--B
| /| /|\/|\/|\/|\/|\/|\/|\/|\/|\/|\ |\ |
|/ |/ |/\|/\|/\|/\|/\|/\|/\|/\|/\| \| \|
B--B--B--B--B--B--B--B--B--B--B--B--B--B
| /| /| /|\/|\/|\/|\/|\/|\/|\/|\ |\ |\ |
|/ |/ |/ |/\|/\|/\|/\|/\|/\|/\| \| \| \|
B--B--B--B--B--B--B--B--B--B--B--B--B--B

La razón por la que esto tiene forma cuadrada es que el acotador busca nuevas rectas dentro de un cuadrado, que va ampliando según sea necesario. Como hace la búsqueda de arriba abajo y de izquierda a derecha, las nuevas rayas aparecen "barridas" hacia abajo a la izquierda. En las siguientes pasadas el cuadrado se va ampliando y las rayas acaban invadiendo todo el plano, así que cuando el acotador cree que puede añadir más de 200 rayas nuevas abandona y en vez de devolver una cota sobre el número de rayas devuelve un -1, que viene a decir "NPI".

Bueno, el que el acotador no acote ocasionalmente no es un problema demasiado grave; simplemente exploraremos ramas del árbol que quizás nos podríamos haber ahorrado. El problema sería que no consiguiese acotar con mucha frecuencia.

¿Pero cómo funciona en la práctica? Continuará...

Solitario de rayas VI: Acotadores

La única esperanza de resolver el problema en un tiempo razonable es que no es necesario explorar todo el árbol, sino que a veces podremos podar algunas de sus ramas.

Por usar un poco de jerga; el algoritmo del que hemos hablado hasta ahora para recorrer todo el árbol (ver primero qué pasa si incluímos una raya, y ver luego qué pasa si la excluímos) es un ejemplo de Backtracking (Wikipedia lo traduce como "Vuelta atrás" pero a mí no me acaba de gustar esta traducción), y ahora queremos cambiarlo a Ramificación y poda, también llamado Ramificación y acotación, o Branch and bound.

Aunque en la Wikipedia lo explican de forma general y abstracta, la idea es sencilla: si tenemos un récord con 200 rayas, estamos en un vértice con 50 rayas, y sabemos que como mucho podremos añadir 50 rayas más, entonces no tenemos que explorar la rama que empieza en ese vértice, porque hagamos lo que hagamos no batiremos el récord. Si podamos muchas ramas y son grandes, podemos ahorrarnos cantidades enormes de trabajo.

El problema está, obviamente, en estimar el número máximo de rayas que se podrán añadir; en la jerga, "acotar el número de rayas".

En muchos problemas hay alguna forma relativamente sencilla de acotar algo; con frecuencia simplemente se calcula una fórmula matemática. En nuestro caso no tenemos tanta suerte; tendremos que usar un programa (una función en realidad) algo complicadillo al que llamaremos acotador.

Un acotador ideal tendría estas dos cualidades:

1. rapidez
2. precisión (la cota proporcionada debería estar muy cerca del máximo)

Desgraciadamente, las dos cosas son mutuamente excluyentes. Un extremo: como sabemos que ninguna figura tendrá más de 966 rayas, podríamos escribir un acotador velocísimo que, sin mirar siquiera a la figura, dijese que como mucho se le pueden añadir 966 rayas, y sería correcto, pero nada preciso, y absolutamente inútil, porque nunca serviría para podar una rama. El otro extremo sería escribir un acotador muy preciso que explorase toda la rama y devolviese el máximo exacto de rayas que se pueden añadir, pero entonces sería absurdamente lento; mucho más lento que usar el programa sin acotador. De hecho, no tiene sentido usar un acotador que dé la respuesta exacta y que sea rápido, porque entonces lo usaríamos directamente para resolver el problema. La gracia está en encontrar un punto medio, una forma fácil de encontrar una cota que pode mucho.

En nuestro caso, las llamadas al acotador costarán bastante tiempo, así que, para empezar, lo usaremos sólo cuando el número de rayas incluidas sea mayor que 20 y múltiplo de cinco. Lo más probable es que en el futuro decidamos cambiar esta condición.

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.

Solitario de rayas IV: Record de 17 puntos

Hace una semana que no escribo ninguna entrada, así que lo mismo empieza a parecer que he abandonado el problema. ¡En absoluto! Es simplemente que me he entretenido jugando en vez de escribir. Como prueba exhibo este espécimen capturado por uno de mis programas exploradores, que en una inmersión de 12 horas descendió a las profundidades abisales de un árbol binario de 121 niveles buscando un ejemplar cuya distancia entre cuernos superase el record anterior de 16 puntos.

Solitario de rayas III: Qué ocurrió en los bits 31 y 38

He escrito unas funcioncitas para matlab que me ayudarán a hacer los gráficos; usar paint es muy sencillo y te saca de un apuro, pero hasta ahora no he conseguido hacer dos dibujos parecidos.

He mirado qué es lo que ocurrió en los bits 31 y 38, y resulta que no ocurrió nada de particular, sino simplemente lo que ya sabe cualquiera que haya hecho unos cuantos solitarios. Con cierta frecuencia llegas a un cuello de botella, donde parece que te vas a quedar sin poder poner más rayas, pero, si consigues salir del atasco, entonces puedes añadir un montón de rayas sin apenas pensar.

Tras poner la raya número 30, las cosas están así:

Estamos en uno de los cuellos de botella; poner rayas arriba fue muy fácil, pero ahora quedan pocas opciones, y si ponemos la primera raya que vemos (la verde de trazo grueso) metemos la pata, porque a continuación sólo será posible añadir cuatro rayas más (en verde con trazo delgado).

Usar esa raya es un error; lo que habría que hacer es añadir la otra raya horizontal, cosa que nos permite "cerrar un puente" (las dos rayas verdes gruesas). Enseguida podemos poner otras cuatro rayas verdes. ¿Significa esto que hemos salido del atolladero? No del todo; la quinta raya (azul claro grueso) vuelve a ser un error, después de añadirla sólo podemos añadir dos rayas más.

Es una mala idea añadir esa diagonal, porque la queremos un poco más abajo. Así que si no la ponemos y en su lugar añadimos la horizontal del fondo, entonces sí que volvemos a tener todas las opciones que queramos, y podemos añadir sin pensar las siguientes 28 rayas que veamos.

Yo esperaba que estos cuellos de botella fuesen más frecuentes, porque ayudarán a que podamos eliminar muchas opciones. Pero en el primer intento de poner 64 rayas hemos pasado sólo por dos (o uno, según se mire). Explorar sin restricciones no es bueno. Por ejemplo, si el record tuviese 180 rayas, y tuviésemos suerte y lo encontrásemos en el segundo día de búsqueda, y los quedásemos unas horas explorando por el bit 140, la cuenta del otro día nos diría que tardaríamos 48 horas por 2¹⁴⁰, es decir, 3·10³⁹ años.

Solitario de rayas II: Midiendo a Goliat

No me acordaba yo de lo obsesivo que puede llegar a ser este problema. No llega al extremo del Tetris, que hacía que fueses viendo fichas cayendo mientras caminabas por la calle, pero después de unas horas haciendo solitarios, cuando miro al teclado del ordenador empiezo a trazar mentalmente rayas uniendo las letras. Es especialmente hipnótico el barrer con la mirada un solitario casi acabado, cuando no tienes que aplicar ninguna estrategia, ni tienes que decidir qué rayas pones antes que otras, sino que simplemente debes buscar huecos donde añadir una nueva raya.

Ayer acabé mi primer programa y lo puse en marcha. El pobrecito era mera carne de cañón, estaba destinado a estrellarse sin posibilidad de victoria contra un enemigo muy superior numéricamente.

La noticia buena es que, a pesar de sus limitaciones, este programita ha sido capaz de encontrar una solución con 98 rayas en 11 horas:

               *                        
               |\                       
               | \                      
      *--*--*--*--*  *  *               
      |\ |\/|\/|  |\/|\/|\              
      | \|/\|/\|  |/\|/\| \             
   *  *  *--#--#--#--#--*--*--*--*      
    \ |\/|\/|\/|\/|\/|\ |\ |\   /|      
     \|/\|/\|/\|/\|/\| \| \| \ / |      
      *  *--#--*--*--#--*--*--*--*      
     /|\/|\/|\/|\/|\/|\ |\/|\/ \/|      
    / |/\|/\|/\|/\|/\| \|/\|/\ /\|      
   *  *  *--#--*--*--#--*--*--*--*      
  /|\/|\/|\/|\/ \/|\/|\/|\/|\/|\/|\     
 / |/\|/\|/\|/\ /\|/\|/\|/\|/\|/\| \    
*--#--#--#--#  *  *--#--#--#--#  *  *   
 \ |\/|\ |\/ \/ \/| / \/|\/|\/|\/|  |   
  \|/\| \|/\ /\ /\|/  /\|/\|/\|/\|  |   
   #--*--*--*--*--*--*--*--*--#--*--*--*
   |\ |\/|\/ \/|\/|\/ \/|\/|\/|  |\ |   
   | \|/\|/\ /\|/\|/\ /\|/\|/\|  | \|   
*--#--*--*--*--*--*--*--*--*--#--*--*   
 \ |\/|\ |\/|\ |\/|\/|\/|\/|\/|\/| /|\  
  \|/\| \|/\| \|/\|/\|/\|/\|/\|/\|/ | \ 
   #--#--#--#--*--*--#--#--#--#--*--*--*
  / \ |\ |\ |\/|\/|\/|\/|\/|\/|\/|\/| / 
 /   \| \| \|/\|/\|/\|/\|/\|/\|/\|/\|/  
*     *--*--#--*--*--#--*--*--*  *  *   
       \ |\/|\/|\/|\/|\/|\/|\/|\/| /    
        \|/\|/\|/\|/\|/\|/\|/\|/\|/     
         *--#--*--*--#--*--*--*--*      
         |\/|\/ \/|\/|\/|\/| /| /       
         |/\|/\ /\|/\|/\|/\|/ |/        
         *--#--#--#--#--*--*--*--*      
         | /  /   |\  \ |\/|\/|         
         |/  /    | \  \|/\|/\|         
         *  *     *--*--*--*--*         
         | /      |   \ |\ |            
         |/       |    \| \|            
         *        *     *  *            
                           |            
                           |            
                           *            

En cuanto a la anchura, lo mejor que ha encontrado tenía 16 puntos de lado a lado; me parece poco, tendré que echarle un ojo al programa a ver si tiene algún error.

La noticia mala es que durante veinte horas ha explorado 5.500 millones de figuras, y esto ha resultado ser una fracción ridículamente insignificante del problema. Echemos unas cuentas.

Para entender lo que significan los datos que pondré después, tendré que explicar lo que significan las ristras de unos y ceros. Lo que hace este programa para analizar una figura es dividirla en dos casos:

1. buscar una raya que pueda ser añadida
2. añadir esta raya (esto se representa con un 1) y analizar la figura obtenida
3. quitar la raya (esto es un 0) y analizar la figura, recordando no volver a añadir nunca más esa raya
4. acabar; volver al análisis anterior, de donde venimos.

A cada caso analizado, el programa escribe una secuencia de unos y ceros, indicando dónde está en este procedimiento; por ejemplo, la cadena "101..." quiere decir que todavía está analizando el caso en que pone la primera raya, no pone la segunda, pone la tercera,...

Un ejemplo; empezamos con estos puntos marcados:

Obviamente sólo podemos añadir cuatro rayas, que supongamos que el programa va encontrando en este orden: rojo, verde, azul, marrón.

Sólo hay 9 posibilidades, porque si decidimos poner la línea roja, entonces no podremos poner la marrón, y si decidimos poner la verde, no podremos poner la azul. Estas nueve posibilidades son exploradas mientras se recorre este árbol:

Bueno, pues esta tabla resume la búsqueda hasta ahora.

Récord	Tiempo	Posición en el árbol
67 rayas	1 seg	1111111111111111111111111 1111101111110111111111111 111111111111100111111
75 rayas	4 seg	1111111111111111111111111 1111101111110111111111111 1110111011101111100111111 1111111
77 rayas	20 seg	1111111111111111111111111 1111101111110111111111111 0011110110001100110111111 1100110111111111
82 rayas	2,5 min	1111111111111111111111111 1111101111110111111111101 0011111010111011111011101 11111111111111
anchura 16	1,5 horas	1111111111111111111111111 1111101111110111111110100 1111011111111110111110011 101111111011101110111
98 rayas	11 horas	1111111111111111111111111 1111101111110111111011100 1100110111001101111101110 1101111111111111111110111 11111011111111
-	20 horas	1111111111111111111111111 1111101111110111111010001 1011001000110110100010110 11110101101110

Una cosa que me llama mucho la atención son esos dos bits que aparecen puestos a 0, el 31 y el 38, los marcados en verde. ¿Qué narices habrá pasado ahí para que el ordenador se haya podido dar cuenta de que esas dos rayas no deben incluirse? Han estado ahí desde el primer segundo. Tengo curiosidad, esto habrá que investigarlo.

Pero el caso es que seguimos trabajando en el bit número 44; todas las secuencias empiezan con la misma ristra de 44 unos y ceros (marcada en rojo). Vale que como hay dos bits inútiles podemos decir que estamos trabajando en el bit efectivo número 42, pero de todas formas esto sugiere que en 20 horas hemos hecho la 2^-42-ava parte del trabajo. En otras palabras, este programa podría acabar dentro de unas 20*2⁴² horas, es decir, dentro de 10.000 millones de años. Tampoco es para tanto; si hubiésemos empezado a calcular cuando el Big Bang, ya habríamos acabado (sería una forma como otra cualquiera de darle un propósito al universo).

¿Nos habremos metido con un problema demasiado grande? Al escribir esto me estoy rascando la barbilla con aire preocupado. Bueno, parece claro que nos lo vamos a tener que currar, pero nos quedan unos cuantos trucos en la manga. Por ejemplo, considerando que debido a las simetrías del problema encontraremos casi todas las soluciones por octuplicado, debería ser fácil rebajar el tiempo a unos 1.250 millones de años. Pero lo que tenemos que hacer con nuestro árbol es podarlo a lo bestia. Próximamente en este blog: branch and bound.

Solitario de rayas I: Introducción

Hace 20 años, en mi primer curso de carrera, me estuve dedicando con unos compañeros de clase a hacer un tipo de solitario que requiere papel cuadriculado. El juego empieza marcando 36 puntos de esta forma:

El juego consiste en buscar grupos de cinco puntos alineados y consecutivos de los que al menos cuatro ya estén marcados, en direcciones horizontal, vertical y diagonal. Entonces se dibuja el segmento y se marca el punto que no estuviese marcado. Tres ejemplos dejarán esto claro:

El objetivo del juego es, simplemente, añadir el mayor número posible de rayas.

¿Hasta dónde se puede llegar? Pues bastante lejos. No consigo recordar si mi récord personal era 142 o 182 rayas, pero había bastante gente que me ganaba. He aquí un solitario con 90 rayas que acabo de hacer sin estar entrenado:

El compañero que nos enseñó el juego decía que era posible llegar hasta las 2.000 rayas, pero esto se lo debió de inventar. Para justificar esto, observemos que al principio cada punto marcado tiene ocho "enlaces libres"; es decir, podría ser conectado con ocho puntos vecinos. Cuando dibujamos un segmento y marcamos el punto en uno de sus extremos, usamos siete enlaces y añadimos un punto con siete enlaces libres.

Cuando dibujamos un segmento y marcamos un punto interior, quitamos en total seis enlaces, pero añadimos un punto con seis enlaces. Y, finalmente, cuando dibujamos un segmento que une cinco puntos ya marcados, entonces perdemos 8 enlaces libres. Es decir, mientras vamos haciendo el solitario, el número de enlaces libres que tienen los puntos marcados sólo puede disminuir; y empezarán a alejarse entre sí cuando la figura se haga mayor y mayor, de forma que tarde o temprano se hará imposible añadir nuevos segmentos.

Al empezar tenemos 36 puntos, cada uno con 8 enlaces libres, con lo cual tenemos un total de 288 enlaces libres iniciales.

Bueno, pues pensemos ahora en un octógono que tenga 13 puntos en cada lado:

Esta figura tiene 4 enlaces libres en cada esquina, y 3 en cada uno de los otros puntos en su frontera, de forma que en total tiene 296 enlaces libres, más de los que tendrá cualquier figura que podamos obtener haciendo el solitario. Quizás sea posible que alguna figura del solitario no quepa en el octógono (aunque yo apostaría a que no), pero estas figuras tendrán una razón perímetro/área mayor, y por tanto menos rayas que la mejor figura. No estoy siendo muy riguroso aquí, pero me imagino que se me entiende.

Dado que en el octógono sólo caben 966 rayas (estaría bien que alguien confirmase esta cuenta), y que la mejor solución del solitario estará dentro del octógono, la mejor solución del solitario tendrá menos de 966 rayas; de hecho, podemos apostar a que tendrá bastante menos de 966 rayas.

Así pues, he aquí los dos problemas que nos proponemos resolver:

• Encontrar la figura del solitario con el mayor número de rayas.


• Y, de paso, encontrar la figura del solitario más alargada, para ver si cabe o no dentro del octógono.

El número de posibles subconjuntos de rayas dentro del octógono es una salvajada, algo así como 2⁴⁰⁰⁰. Por decirlo de una forma suave, no vamos a poder analizarlos todos ni siquiera cuando tengamos ordenadores con cuatro procesadores. Pero el caso es que, cuando uno se pone a jugar al solitario, no tiene la impresión de tener muchas opciones para poner nuevas rayas, así que quizás no es tan absolutamente imposible encontrar la solución.

En otras palabras: no tenemos ni idea de si podremos resolver el problema. ¡Esto va a ser una aventura!