sudoku, algorítmos genéticos, la estrategia backtracking, programación lineal y R

/* Habiendo leído El curioso incidente del perro a medianoche le tomé cierto buen gusto a los títulos largos :-) */

Hace unas semanas, Mahoo me regaló un pequeño libro con un montón de sudokus para resolver. Si bien conocía el juego, nunca me atrajo particularmente. En esos días, yo estaba buscando algún tema original para uno de los trabajos prácticos de Inteligencia Artificial. La consigna se refería al uso de algoritmos genéticos para la resolución de algún problema. Lo importante no era el programa, sino el análisis de su comportamiento: estudiando, por ejemplo, qué método de cruzamiento se aplica mejor o qué función de aptitud es más representativa.

Viendo como Mahoo se entretenía con alguno de ellos (práctica en la que también se iniciaba) se me ocurrió que un resolver de sudokus podría ser una linda propuesta para mi TP.

Los algoritmos genéticos intentan emular a la naturaleza, a base de prueba y error, favoreciendo a las soluciones más aptas y castigando a las que no lo son tanto. Suponiendo que el cruzamiento de las buenas-soluciones generan aún-mejores-soluciones. Se trata de la búsqueda probabilística, muy parecida a meter muchas soluciones en un cubilete gigante y agitarlas hasta encontrar algo útil.

Al tratarse de un problema determinístico, la solución dista muchísimo de ser óptima. De hecho, ni siquiera se asegura que vaya a haber una solución. Pero me pareció algo simpático de intentar.

El resultado, escrito en mi rústico Python, puede ser bajado de aquí (incluye instrucciones para correrlo en Windows). No, no esperen que funcione bien, advertidos están. Es uno de los peores métodos posibles para este tipo de problemas. Sólo llega a una solución cuando la cantidad de incógnitas es (muy) limitada. Se plantean soluciones a base de llenar de random cada uno de los casilleros vacíos y chequeando cuantos valores se repiten en cada fila, columna y región. Cuando este chequeo da 0, se llega a una solución. Bastante cavernícola como notarán.

Es natural pensar en cuál sería la forma correcta de llegar a una solución. Recordé las clases de Investigación Operativa y la utilización del método simplex para la solución a problemas con restricciones. De hecho, es una solución que muchos proponen. No se si alguno de ustedes lo ha intentado. Yo sí, durante las clases aburridas me senté a pensar como sería el conjunto de ecuaciones y me encontré con una demencial y frustrante cantidad de ecuaciones. Acá hay una linda explicación, la que resumo, haciendo énfasis en las complicaciones:
Se necesitan variables binarias de la forma xijk donde 1 significa que el símbolo k (de 1 a 9) va en la celda (i,j) de la solución. 0 significa que no está. Esto genera un total de 729 variables (93) lo que, como mínimo, asusta. Veamos las ecuaciones:

(1) Para que cada celda (i,j) tenga un símbolo y éste sea único. Se necesitan 81 ecuaciones como éstas (una por cada celda).
(2) Para que en la fila i cada símbolo esté una vez y que en todas las columnas sea distinto. Se necesitan 81 ecuaciones como éstas(una por cada columna y cada símbolo posible).
(3) Para que en la columna j cada símbolo esté una vez y que en todas las filas sea distinto. Se necesitan 81 ecuaciones como éstas(una por cada fila y cada símbolo posible).
(4) Para que en cada región cada símbolo esté una y solo una vez. Se necesitan 81 ecuaciones como éstas (una por cada región y cada símbolo posible).
(5) Representa el enunciado, es decir, el problema a resolver. Por ejemplo, x115=1 significa que en la celda (1,1) hay un 5. Dependiendo cuantos casilleros vengan asignados es la cantidad de igualdades como estas que se necesitan; típicamente, ~30.
(6) Restringe las variables al conjunto binario.

¡En total son más de 350 ecuaciones! Hay propuestas con menos ecuaciones, pero siempre serán muchísimas. Evidentemente, ésta tampoco es la solución óptima (aunque es mucho mejor que los algoritmos genéticos). Y su problema radica en que, desde algún punto de vista, el método simplex no se ajusta al problema. Gráficamente, las ecuaciones representan semiplanos en un hiperespacio multidimencional (de 9 dimensiones?) cuya intersección es, en caso que haya una única solución, un único punto. /* Puede que le esté pifiando en esta conclusión final y cualquier ratificación o rectificación es bienvenida */

Simplex está pensado para restricciones de máximos y mínimos donde el objetivo es maximizar o minimizar y las variables binarias intentan ampliar el método para restricciones de este tipo. Da soluciones múltiples en forma de un polígono, donde a una o más se las llama óptima, porque maximiza o minimiza la función objetivo. Es claro que el problema del sudoku no usa sus ventajas y abusa de sus debilidades.

Curiosamente, cuando comenté este problema a un reciente conocido, surgió que también él tuvo que hacer un trabajo práctico que resolvía sudokus. En este caso, el TP giraba entorno a la gestión de la pila para recorrer árboles. Particularmente, árboles empleados en la estrategia de backtracking. Así pues, éste es su programita, sencillo, simpático y rápido. Gracias Nacho :).

Los métodos basados en búsqueda combinatoria sobre árboles parecen ser particularmente buenas para el problema del sudoku. En la wikipedia figuran dos interesantes formas: backtracking y ramificación y poda.

Para terminar, una última casualidad: Por razones que no vienen al caso ahora y que seguramente provocarán un nuevo post en el futuro estoy aprendiendo un lenguaje para el procesamiento de señales llamado R. Estoy trabajando mucho con una biblioteca llamada sound. Buscándola en el repositorio de bibliotecas, me encuentro con una llamada sudoku. No resistí la tentación de probarla :). Un ejemplo de su uso:

> install.packages("sudoku")
> # es necesario instalar tcltk si se quiere la parte gráfica
> install.packages("tcltk")
> library(sudoku)
> library(tcltk)
> library(tkrplot)
> miSudoku <- generateSudoku(Nblank=50, print.it=TRUE)
  +-------+-------+-------+
  |   6   |   7   |   8 2 |
  | 4 8   |     1 | 7     |
  |       | 8 2   | 5     |
  +-------+-------+-------+
  |       | 1     | 9 7   |
  |       |     2 |   5 1 |
  | 5 1 6 |   9 7 |       |
  +-------+-------+-------+
  |       |   4 8 |       |
  | 6 5   | 7   9 | 8     |
  |       |       |   9 7 |
  +-------+-------+-------+
> # la variable miSudoku es una matriz
> miSudoku
       [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
 [1,]    0    6    0    0    7    0    0    8    2
 [2,]    4    8    0    0    0    1    7    0    0
 [3,]    0    0    0    8    2    0    5    0    0
 [4,]    0    0    0    1    0    0    9    7    0
 [5,]    0    0    0    0    0    2    0    5    1
 [6,]    5    1    6    0    9    7    0    0    0
 [7,]    0    0    0    0    4    8    0    0    0
 [8,]    6    5    0    7    0    9    8    0    0
 [9,]    0    0    0    0    0    0    0    9    7
> #La biblioteca incluye una función para para solucionarlo
> solveSudoku(miSudoku)
       [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
 [1,]    1    6    5    9    7    3    4    8    2
 [2,]    4    8    2    5    6    1    7    3    9
 [3,]    3    7    9    8    2    4    5    1    6
 [4,]    2    4    8    1    5    6    9    7    3
 [5,]    7    9    3    4    8    2    6    5    1
 [6,]    5    1    6    3    9    7    2    4    8
 [7,]    9    3    7    2    4    8    1    6    5
 [8,]    6    5    1    7    3    9    8    2    4
 [9,]    8    2    4    6    1    5    3    9    7
> # Incluso trae soporte gráfico para resolverlo en una ventanita :)
> playSudoku()

Así fue como, un simple regalo, un TP universitario y un montón de simpáticas casualidades tuvieron su punto de conexión. Y que divertido que resultó ser :). Ahora tengo que escribir el informe sobre los algoritmos genéticos en el sudoku. La semana que viene espero publicarlo aquí.

UPDATE August 6th: El informe y los archivos relacionados ya está publicados.

new/old challenges

Desde hace unos meses, he sumado dos elementos al unitario conjunto de hobbies en mi vida (me refiero a los hobbies extra-computacionales), que estaba compuesto, únicamente, por eventuales apariciones de mi vulgar fotografía. Si bien gusto de leer, no lo considero tanto un hobby, sino algo necesario, con lo que lo excluyo del conjunto. Estos dos nuevos elementos son: el juego del go y el baile de la danza rioplatense. Ambos, en una evidente condición de neófito pero sin duda muy disfrutables, me ayudan a despejarme en los cada vez menos disponibles espacios de ocio.

La razón de esta reducción de idle time es provocada por:
a) La vida universitaria, la pila de materias que estoy cursando para recibirme rápido y la cantidad de trabajos prácticos que implican estas materias.
b) El cursado de un posgrado en Criptografía y Seguridad Teleinformática que empecé recientemente.
c) Algunos trabajos que estoy empezando a hacer para una empresa de seguridad local, llamada Shellcode y en la que espero divertirme mucho. (Esto se suma a mi actual trabajo, no lo reemplaza).
d) Retomar el mucho trabajo pendiente que tengo en Debian.

Empiezo nuevos desafíos. Continúo los pendiente. Y eso está bueno :).

mathematical beauty

Dado que esta semana tengo varios exámenes y que mi procrastinación me impidió estudiar, dediqué el fin de semana a la lectura.

Leí La Matematica como una de las Bellas Artes de Pablo Amster. Un libro entretenido, corto e interesante, que por momentos peca de subestimar al lector cuando no profundiza en algunos temas por tratarse "de cosas demasiado complejas". Si bien se trata de un texto de divulgación (aka. "estimular al lector antes que espantarlo" (sic)) en algunos de sus párrafos los fundamentos y explicaciones tienen sabor a poco.

Si sos de esas personas que, como yo, describen al Círculo de Euler como algo simpático, este libro puede interesarte. Mucha anécdota, mucha rareza y mucha clasificación filosófica. Cientoveintitantas páginas bastante entretenidas que invitan a pensar sobre lo lindo de la matemática y la belleza de los teoremas.

perdiendo identidad

Hace unos días Marcela descubre que alguien me llama Flavio Bello. Entre los ponentes del Foro Mundial figuro como Luciano Rodriguez. Y como si ya nada pudiera sorprender, el taxista que me va a buscar al aeropuerto de Caracas realizan una simpática innovación: Lusiano Bellot. Y yo que creía que era un problema exclusivo de los asiáticos y europeos germanos.

A partir de ahora voy a empezar a presentarme como 0x894BB479, a sus ordenes.

GNUtn rulez!

Creo que es la primera vez que menciono a GNUtn en mi blog. Tal vez sea porque hasta anteayer no le encontraba mucho sentido. GNUtn (a.k.a. Grupo de Nerds Utenianos) es un grupo que fundamos, si la memoria no me falla, junto con Roberto y Nutz hace un par de años. Hoy tiene unos 60 subscriptos en la lista de e-mail. El objetivo, fomentar el uso y la ideología del Software Libre. Siempre tuvimos el desafío de darle ese toque filosófico que sobrepase lo técnico. Y, por primera vez, creo que lo estamos logrando.

Ayer tuvimos una metting presencial en el café frente a la facultad. Grandes conclusiones, grandes proyecto.

O tal vez sea yo, que hoy me levanté optimista.

I wish to live at DebConf for ever

Estoy despierto, posteando esto, en la última madrugada de la última noche que pasaré en Helsinki. Mañana, como a las 11pm, sale el bus hacia San Petersburgo. Como siempre, el cielo no termina de estar oscuro. Tiene ganas pero no puede. Casi como las sensaciones encontradas que tengo. Sigo de aventura por otros destinos, pero hay pocas cosas que me gusten más que DebConf.

Muchas cosas pasaron estos días. Creo que en lineas generales cumplí las expectativas fotográficas de los dos pedidos que me hicieron:
- Mi madre quería más paisajes => Visité y conocí muchos lugares de donde tengo muchas fotos.
- Santiago quería más cacharros electrónicos raros => En el Museo de Tecnología encontré muchas cosas raras.
Espero haber satisfecho ambos pedidos. El jueves por la tarde fui al Museo. Y el Viernes todo el día en el centro del Helsinki. Trataré de usar las fotos como guía de sucesos.

DebConf no es en Helsinki propiamente dicho, sino en Otaniemi, un barrio de la ciudad de Espoo, a unos 10km del centro. Por unos módicos 3,40 euros, el colectivo 102T te deja en Kamppi, después de unos 20 minutos de viaje. Estabamos en Kamppi cuando se cortó la luz. Raro, pero seguramente se debía a que estaban haciendo unas construcciones para extender la terminal.

Para ir al museo debíamos tomar otro colectivo más. Así que después de otros 20 minutos llegamos. Entrada: 1,50 euros para estudiantes, una ganga. La visita estuvo muy interesante. El único problema que muchas de las descripciones estaban en suomi o en sueco. ¡Pero se puede tocar todo! Lo mejor: Todo un piso de la evolución de los conmutadores telefónicos. ¡Y funcionando! Uno tenía un teléfono en una punta y marcaba el número de la otra punta. Se podía ver los relés haciendo el circuito. Fue genial.
En el lugar nos encontramos con otra gente de la DebConf que había ido por su cuenta. Obviamente la sección de informática fue una de las que nos entretuvo durante más tiempo.

Esa misma noche tuvimos la Cena Formal. ¿Qué es la cena formal? En cada DebConf hay una cena distinta a las demás, donde el DPL hace un pequeño discurso sobre lo grande que es Debian. En este caso la Cena Forma fue muy parecida a cualquier otra cena, de no ser por estas diferencias:
- Había entrada y postre.
- Había velitas en las mesas.
El plato principal era una especie de guiso con carne de reno. Reno se dice porro en suomi. Lo que explica porque Papá Noél se ríe tanto. Muchos otros chistes se hicieron respecto a esta traducción.

El viernes nos levantamos temprano y fuimos a pasear por el centro. Fuimos a la zona del puerto y la plaza principal. Vimos como la Banda de Colimbas fineses interpretar marchas y otras canciones (una sonaba a "what a wonderful world", pero no estoy seguro). Paseamos por las calles y shoppings. Fuimos al museo de Diseño (bastante pedorro, dicho sea de paso) y a muchas iglesias. Destacable la última de las iglesias visitadas: Temppeliaukio Church, que está cavada en la roca.

El sábado, Leandro y Marcela fueron a Tálin, Estonia. Yo elegí quedarme porque había trabajado muy poco en los últimos días. Debo reconocer que por momentos me arrepentí de haber tomado tan conflictiva decisión, pero como premio a mi esfuerzo Davfs2 ahora está en la versión 0.2.4. No creo que llegue a empaquetarlo antes de que termine DebConf, tal como era uno de mis objetivos. Pero aprendí muchísimo.

Upa, siempre me agarra el día cuando tipeo de noche :P. Hoy domingo es el último día. La pasé genial. Quisiera vivir en una DebConf eterna. Claro está que no se puede :P. Rusia espera.

DayTrip @ DebConf

Lo más fresco que tengo en la memoria, sencillamente porque acabó de volver, es el DayTrip. Resulta que hay un día en cada DebConf en que todos los geeks salimos a pasear. El de DebConf4 me lo perdí ya ni me acuerdo porque, pero esta vez hice el esfuerzo por ir. Si bien no fue algo fascinante, hace bien estar lejos del e-mail y los códigos por un rato. Así que me levanté relativamente temprano (la primera vez que llego al desayuno) y nos tomamos un barquito. El destino: Suomenlinna Fortress Island.

La isla (en realidad son unas 2 o 3) en cuestión tiene, como todo lugar que quiera ser visitado, una historia. Historia que un guía turístico contaba en un inglés defectuoso, algo vacía de emoción y aventura. Así que junto con Leandro y Marcela decidimos ir a hacer la nuestra, lejos de los datos fríos del humilde historiador. Y creo que fue una pegada.
Paseamos por la costa, vimos ruinas de fuertes, sacamos fotos de cada palmo del lugar, interactuamos con locales y nos reímos de sus costumbres. Todo lo que un turista debe hacer cuando esta "turistiando".
Al mediodía hubo picnic light, tal como lo decía la planificación. Fue ahí cuando me dí cuenta que valió la pena llegar al desayuno. Alcanzó para algún otro paseo antes de embarcar la vuelta.
La vuelta fue una de las cosas que más disfruté. Dos razones:
- Me tocó "techito". Son esos asientos que están al descubierto, arriba de la embarcación.
- A la ida me quedé dormido y me desperté en destino.
Si bien el sol se encargó de que ahora tenga tirante y colorada la cara/nariz, me gustaron mucho los paisajes y la brisa fresca. Como siempre, las fotos de rigor.

En otro desorden de cosas: Como lo nombré me veo en la obligación de dedicarle algunas líneas: Llegó Leandro (aka Rezlaj). ¿Qué quién es? Próximo compañero de aventuras en el resto del itinerario por el viejo continente. Con él sumamos tres, y será el encargado de manejar sobre los caminos europeos. Eso y siempre la licencia de conductor que se olvidó llegue por correo a tiempo. Para complicarla aún más, sus valijas quedaron en Roma. Pormenores aparte (ya ideo un plan para su solución), Leandro ya está aca, como uno debianero más (aunque programe .NET :P).

Por el resto, todo en orden. Estuve toda la semana (lo que va de ella) entre conferencias y programas. Ayer nos sacamos la foto grupal y me dí cuenta que somos una montón. Eso es bueno :D.

Si llego a recordar alguna cosa dejada en el tintero, no dudaré en volver a postear.

Baranjando en barajas

Son las 8:09, hora Madrid y estoy en Barajas en esperando mi conexión. Menudo viaje resultó ser Buenos Aires - Madrid.
Paso a comentar, tengo 63 minutos para tipear.
Este fue mi ticket, y en el se ve algo evidente para el ojo entrenado, que no es el mío. Notarán que mi asiento está ubicado en la fila 50. ¿Cuantas filas tiene en total el avión? 50. Ergo, estuve de recepcionista del baño. Me sentí como Indomables en la entrega de los Martín Fierro. El ruido del inodoro, la cola de la gente, las azafatas cuchichiando en el fondo. Todos los ingredientes para pasarla bomba. En el respaldo del asiento podía encontrarse el folleto con las precauciones y explicaciones de rigor. Entre las prohibiciones durante el despeje y el aterrizaje se encuentra, como pueden ver, el de usar computadoras portátiles que corran Windows98(TM). Así que abrí mi laptop tranquilo :D. La batería duró poco, y tuve que dedicarme a menesteres más sociales, como conversar, comer, leer, ver películas y dormir. En ese orden:

  • Conversar: Temas clásicos sobre el clima, los husos horarios y las razones del viajes ocuparon gran parte de la jornada junto a un señora de unos sesentaylargos años y una chaqueña. Ambas iban a visitar a familiares, nietas y padre respectivamente. Ambas a Barcelona.
    Otro tema que surgió, esta vez con un pelado de candado del asiento de adelante, fue la poca hospitalidad de las azafatas. Te miraban con tal cara de traste y resoplaban tanto al hacer las cosas que uno tenía miedo de pedir un vaso de agua.

  • Comer: Dos comidas, un almuerzo y un desayuno. En el primero había para elegir entre pasta y carne. Por esas cosas que tiene el estar en el último de los asientos me tocó pasta defacto. Igual lo hubiera elegido, sin saber que por pasta se entendía "pasta". Es decir, se trataba de una pasta literalmente, de esas que hace mi mamá los viernes con las sobras de la semana. Creí divisar unos fideos, pero no estoy del todo seguro. El desayuno entró en escena prematuramente a eso de la 1am hora Argentina. Entre las cosas que podían "degustarse" se hallaba una ensalada de frutas donde la naranja estaba seca, el ananá horrible y el melón verde. A este último decidí guardarlo en un bolsillo, tal vez esté algo más fermentado a la vuelta. Será cuestión de evitar el moho.
    El resto de la comida estuvo apetitosamente zafable.

  • Leer: Leí varios capítulos de Neuromante, una muy mal traducida novela cyberpunk.
  • Dormir: Bue.. no dormí en el sentido estricto de la palabra. Noté que la congestión nasal y la presurización de la cabina no se llevan bien. Ni hablemos de los ruidos que salían de adentro del baño, a cercanos centímetros de mí.
  • Ver películas: Creo que me estoy convirtiendo en un fan de Carmen Maura. En este caso disfruté de no-recuerdo-el-nombre-del-film-español. El único problema fue Solita Silveira haciendo de Argentina superada. Creí que iba a ser lo pero, pero ni bien terminó el filmico empezó una capitulo de Friends. Una desilución cuando por los auriculares salió Chandler hablando en un castizo que daban arcadas. Así que intenté volver a dormir, claro que sin éxito.

    6:13 hora local llego a Barajas, que es así como el router de borde de Europa. Barajas es para el mundo lo que el nudo subterráneo 9 de Julio es para Buenos Aires. Enorme lugar. En una gran campaña por mantener limpio el aire los madrileños inventaron algo llamado "smoking points", que son sectores pintados de negro cada unos 200 metros. de unos 10 metros cuadrados en los cuales se puede fumar. Es algo cómico ver todas la chimeneas amontonadas detrás de la linea.

    Costó conseguir enchufe de electricidad para mi agotada portátil, pero el ingenio sudaca pudo contra la barrera física del encastre. ¿InterNet? Solo con WEP, y no tengo las herramientas necesarias, así que me quedaré con las ganas.

    Upa... en 20 minutos salgo. Me fuí.