Friday, July 31, 2009

Cuadrados mágicos

Existen todo género de herramientas de programación en este mundo del cómputo personal. En Windows es donde quizás hemos visto las mejores aplicaciones en este sentido. Las herramientas visuales son francamente excepcionales y hay que ser objetivos: Linux aún no cuenta con herramientas de un poder parecido. Sin embargo, no todo está perdido. La empresa Borland, creadora de Delphi, C++Builder y Jbuilder ha sacado Kylix (Delphi para Linux), el cual pretende incorporar esta estupenda herramienta en el mundo Linux. Desafortunadamente, por el momento, la versión 3 de Kylix es menos poderosa que Delphi 3 para Windows, pero esperemos que esto cambie en el futuro.

Pero claro está, las mejores herramientas de programación tienen sentido sólo si existen programadores que puedan sacar jugo de las mismas. Para eso se necesita entrenar y capacitar a las siguientes generaciones que finalmente, son quienes seguirán escribiendo los programas que en el futuro se necesiten. Y es claro algo: hay que capacitar en la ciencia de la computación y no meramente en la herramienta de programación de moda. Lo importante es que los principios fundamentales de la programación (comunes a todos los lenguajes), se conozcan y se difundan. Así, cuando el programador necesite aplicarse en algún lenguaje particular, aunque le parezca desconocido, a la larga notará estos elementos comunes y en un par de semanas podrá escribir todo género de aplicaciones.

Curiosamente, ciertos lenguajes de programación han pasado desapercibidos hoy día. Tenemos a Prolog, que en su momento fue la gran promesa del proyecto quinta generación de los japoneses (actualmente cancelado), el cual suponía que el software moderno tendría los elementos más importantes de la llamada inteligencia artificial. Los japoneses intentaron crear toda una generación de computadoras basadas en Prolog para que las aplicaciones que corrieran tuviesen mucho más “inteligencia” que las que actualmente conocemos.

El problema de Prolog, inventado en 1972 por Colmeraur, es que –a pesar de sus grandes ventajas para cierto tipo de aplicaciones– es muy ineficiente para una buena cantidad de tareas que hacemos normalmente en la computadora. Y no es que no pueda escribirse un buen editor de textos o una estupenda hoja de cálculo en Prolog, sino que no es el lenguaje más indicado para ello.

Prolog se basa en inferencias lógicas. A manera de ejemplo, si me presentan a alguien que se llama Jorge Flores y yo encuentro un parecido con un amigo mío llamado Luis Flores, quizás mi cerebro haga automáticamente una inferencia y me nazca preguntarle a Jorge: “¿no tienes un hermano llamado Luis?”. Ese tipo de inferencias las puede hacer Prolog. La herramienta, a diferencia de los lenguajes imperativos (Pascal, C++), prefiere describir el problema a programar el algoritmo (la receta de cocina, pues), que resuelva la dificultad. Prolog resuelve todo a través de un motor de inferencias, también reconocido como algoritmo de Robinson (en honor al autor, que publicó por primera vez el mecanismo en 1968). De esta manera y abreviando el asunto (quizás demasiado), en Prolog describimos el problema y el lenguaje nos da las soluciones a través de dos mecanismos: la recursión y el backtrack.

La recursión es simplemente llamarse a sí mismo. En términos de programación significa que una rutina se llame a sí misma hasta que cierta condición impida que se cicle eternamente. El backtrack es, para decirlo en palabras simples, el regresar sobre nuestros pasos si resulta que la solución hallada no cumple con nuestras expectativas. Un ejemplo simple de backtrack puede verse en el recorrer un laberinto. Caminamos dentro de éste hasta que topamos con pared. Si esto ocurre, entonces retrocedemos sobre nuestros pasos hasta encontrar la primera bifurcación posible. Seguimos este procedimiento hasta hallar la salida.

Como ejemplo consideremos la creación de un cuadrado mágico de orden 3 (impar). Un cuadrado mágico es una malla cuadriculada en donde la suma de las líneas verticales, horizontales y diagonales mayores suman todas las misma cantidad. Hay cuadrados mágicos de orden par y de orden impar. Crear cuadrados mágicos de orden impar es muy fácil siguiendo un algoritmo muy conocido. Sin embargo, aquí intentaremos –en lugar de describir este algoritmo– de escribir un programa en Prolog que resuelva el problema y encuentre todas las soluciones (en caso de haberlas). El código que soluciona el problema de un cuadrado de 3x3.

Todo consiste en describir las condiciones iniciales y las de frontera. Luego entonces, le decimos a Prolog que nos dé las soluciones a través de probar todas las posibilidades exhaustivamente. Otro detalle notable es que el programa en Prolog ocupa muy poco espacio. Intente hacer esto en otro lenguaje y notará cómo crece su código. He aquí la versión en Turbo Prolog 2.0 de Borland:



/* Este programa hace un cuadrado mágico de 3x3 */
/* Utilizando como característica principal el */
/* backtrack que viene integrado en Prolog. */
/* */
/* Dicho de otra manera, el programa no usa el */
/* algoritmo conocido para hallar los cuadrados */
/* mágicos de orden impar. En su lugar, describe */
/* las condiciones iniciales y de frontera que */
/* deben cubrirse en este tipo de cuadrados y */
/* entonces Prolog descubre todas las soluciones */
/* */
/* Programó: La_Morsa */

predicates

numero(integer) /* los números que pueden usarse */
ecuacion(integer,integer,integer,integer) /* descripción de cada suma */
cuadrado_magico /* meta a resolver */

clauses

/* condiciones iniciales */
numero(1).
numero(2).
numero(3).
numero(4).
numero(5).
numero(6).
numero(7).
numero(8).
numero(9).

ecuacion(X,Y,Z,R) :- R = X + Y + Z. /* la suma siempre debe dar R */

cuadrado_magico :-
numero(A), numero(B), numero(C),
numero(D), numero(E), numero(F),
numero(G), numero(H), numero(I),
/* vienen las condiciones para los números: */
/* no debe haber números repetidos... */
/* condiciones de frontera, pues */
A<>B,A<>C,A<>D,A<>E,A<>F,A<>G,A<>H,A<>I,
B<>C,B<>D,B<>E,B<>F,B<>G,B<>H,B<>I,
C<>D,C<>E,C<>F,C<>G,C<>H,C<>I,
D<>E,D<>F,D<>G,D<>H,D<>I,
E<>F,E<>G,E<>H,E<>I,
F<>G,F<>H,F<>I,
G<>H,G<>I,
H<>I,
/* escribe en pantalla la combinación de números a probar */
write(A,” “,B,” “,C,” “,D,” “,E,” “,F,” “,G,” “,H,” “,I),nl,
/* condiciones necesarias para que sea cuadrado mágico */
ecuacion(A,B,C,R),
ecuacion(D,E,F,R),
ecuacion(G,H,I,R),
ecuacion(A,D,G,R),
ecuacion(B,E,H,R),
ecuacion(C,F,I,R),
ecuacion(A,E,I,R),
ecuacion(G,E,C,R),
nl,write(“Solución”),nl,
write(A,” “,B,” “,C),nl,
write(D,” “,E,” “,F),nl,
write(G,” “,H,” “,I),nl,
write(“Presiona cualquier tecla para continuar...”),
readchar(_), /* presiona una tecla para continuar */
fail. /* dame todas las soluciones */

goal
cuadrado_magico. /*meta a resolver */



Si le incomoda o francamente le da flojera entender cómo es que el programa funciona, no se preocupe, corra el ejecutable. Si está en Windows encontrará que todo acontece en una ventana de DOS. Es increíble que tan pocas líneas de código generen tanto procesamiento.

6 comments:

Joel said...

Depende en qué programes, en amblas plataformas (Win y Linux) existen excelentes IDE. Por citar un ejemplo, para programar en Java los mejores son excatamente los mismos para ambas plataformas: Eclipse y Netbeans así que no hay lugar para diferencias.

Por otro lado cuantitativamente hablando es cuando yo creo que hay mucha más variedad para el sistema operativo del señor Puertas, sin mencionar que sus herramientas para .NET son exclusivas de Windows.

Saludos.

Ernesto said...

Hola Manuel!

Permíteme por favor recomendarte este libro:
http://www.amazon.com/Godel-Escher-Bach-Eterno-Spanish/dp/8483830248

Creo que es el libro más interesante que tenido en mis manos.
Aún hay un capítulo que no he podido digerir.

Este libro trata sobre: Recursión, linguística, música, física, matemáticas, computación, filosofía, genética, biología. teología, inteligencia artificial.

Morsa said...

Lo leí hace años, pero no es un libro fácil de digerir. El autor se la pasa dejándote tarea y si no te aplicas no le puedes sacar todo el jugo que tiene.

saludos
Manuel

Ernesto said...

Never mind!

Lo descubrí cundo hurgaba en la biblioteca de la universidad para pasar el rato. La versión de CONACYT.
Varios años después en el 2001, le platicaba a un amigo sobre este libro y se compró la versión en inglés en Amazon.

Yo me encontré una versión de pasta dura en Samborns y lo compré con vales de despensa. Costó como 600 pesos en 2002. Fue un robo en descampado.

En 2006 compré dos ejemplares para regalarlo a dos amigos muy queridos.

Fue el primer libro de Hofstadter y le valió un premio Pulitzer.

El prolog ¿Lo aprendiste al hacer tu maestría? Siempre que lo he visto, ha sido relacionado con problemas de inteligencia artificial.

Saludos,
Ernesto

Morsa said...

Prolog lo usamos en la maestría y ahí tomé un buen curso, pero usábamos el prolog de Edinburgo, que funcionaba en las estaciones Sun que tenían en el laboratorio. Cuando regresé encontré turbo prolog que es interesante aunque tiene algunas dificultades al ser compilado (prolog se interpreta en general, lo cual le da ciertas posibilidades interesantes para la creación de hechos en tiempo de ejecución). Sin embargo, la implementación de Borland, que después regresó a los daneses que escribieron el compilador, resulta bastante flexible y se pueden hacer sistemas complejos sin duda.

saludos
Manuel

Alfonso V said...

Para resolver cuadrado mágico 3x3 y otros "Juegos de lógica" de forma online.
Un saludo