Activa las notificaciones para estar al tanto de lo más nuevo en tecnología.

Programación lúdica: 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...

cuadro-magico00
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 parecía estar perdido cuando Borland (ya desaparecida como empresa), creadora de Delphi, C++Builder y Jbuilder, decidió hacer una versión llamada Kylix (Delphi para Linux), el cual pretendía incorporar esta estupenda herramienta en el mundo Linux. Desafortunadamente la versión 3 de Kylix es menos poderosa que incluso Delphi 3 para Windows y después de esto no se trabajó más en Kylix. De hecho, fue abandonado a su suerte.

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 3×3.

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 3×3 */
/* 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 */

Es importante decir que este programa en principio es no determinístico, es decir, no necesariamente sabemos a priori que hallará la solución al problema. Desde luego sabemos que el problema como fue planteado tiene solución pero el sistema no lo sabe y prueba todas las combinaciones posibles al mejor estilo de Prolog.

A quien le interese el programa le puedo mandar el ejecutable (que corre en modo consola) y el código fuente (que es el que puse aquí en el artículo). Turbo Prolog 2.0 califica como Abandonware, es decir, software que se ha abandonado porque ya está Visual Prolog (del mismo fabricante) y la versión para MsDOS es obsoleta. Sin embargo puede descargarse de este sitio, previo registro gratuito. Si alguien quiere programar en esta antigua herramienta de Borland le sugiero use DosBox, el cual puede descargarse de aquí.

Por último, se plantea el siguiente reto: hágase un programa que resuelva cuadrados mágicos de 3×3, 4×4 y 5×5 y que dé todas las soluciones. El que lo haga de forma más rápida, es decir, encuentre más rápido que otros programas las soluciones, se lleva una taza de La Morsa. Sólo aplica a la República Mexicana. Si alguien del extranjero quiere participar, podrá llevarse un USB de 8 GB al menos, el cual se le mandará por correo.

___
(*) La imagen que ilustra este artículo es de un cuadro de Durero. De acuerdo a la Wikipedia: “El cuadrado mágico de Alberto Durero, tallado en su obra Melancolía I está considerado el primero de las artes europeas. En el cuadrado de orden cuatro se obtiene la constante mágica (34) en filas, columnas, diagonales principales, y en las cuatro submatrices de orden 2 en las que puede dividirse el cuadrado, sumando los números de las esquinas, los cuatro números centrales, los dos números centrales de las filas (o columnas) primera y última, etc. y siendo las dos cifras centrales de la última fila 1514 el año de ejecución de la obra“.

Comentarios