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!