
Este semestre, en la Facultad de Ciencias de la UNAM, estoy dando el curso de
Lenguajes Funcionales y Lógicos, el cual es una asignatura optativa de la carrera en Ciencias de la Computación (la cual otorga un título como de Ingeniero en Computación, pero más enfocado al espíritu de la ciencia que de la ingeniería).
Pues bien, empecé el curso con Prolog, lenguaje que significa
PROgramming in
LOGic, y que tiene gran utilidad cuando el problema a resolver tiene que ver con simbologías y con lenguaje natural, por ejemplo. Así, en una clase discutimos las necesidades para escribir un programa que generara los acertijos llamados sudokus. Por un par de días pensé cómo debía codificarse el asunto y cuando pensé que ya tenía la solución, me senté a escribirla. He aquí mi código (para un prolog estándar):
/* Generador de Sudokus */
/* Por La_Morsa */
/* Marzo 2010 */
/* Versión 1.0 */
delete(X, [X|T], T).
delete(X, [H|T], [H|S]):-
delete(X, T, S).
resultados(A,B,C,D,E,F,G,H,I) :-
write(A,B,C,D,E,F,G,H,I),nl.
/*permutaciones */
perm([], []).
perm([H|T], R):-
perm(T, X), delete(H, R, X).
suma(A,B,C,D,E,F,G,H,I,R) :-
A+B+C+D+E+F+G+H+I = R.
escribe(A,B,C,D,E,F,G,H,I) :-
write(A),
write(B),
write(C),
write(D),
write(E),
write(F),
write(G),
write(H),
write(I),
nl.
sudoku :-
/* hallamos primero las permutaciones
de los nueve renglones */
perm([1,2,3,4,5,6,7,8,9],[A1, A2, A3, A4, A5, A6, A7, A8, A9]),
perm([1,2,3,4,5,6,7,8,9],[B1, B2, B3, B4, B5, B6, B7, B8, B9]),
perm([1,2,3,4,5,6,7,8,9],[C1, C2, C3, C4, C5, C6, C7, C8, C9]),
perm([1,2,3,4,5,6,7,8,9],[D1, D2, D3, D4, D5, D6, D7, D8, D9]),
perm([1,2,3,4,5,6,7,8,9],[E1, E2, E3, E4, E5, E6, E7, E8, E9]),
perm([1,2,3,4,5,6,7,8,9],[F1, F2, F3, F4, F5, F6, F7, F8, F9]),
perm([1,2,3,4,5,6,7,8,9],[G1, G2, G3, G4, G5, G6, G7, G8, G9]),
perm([1,2,3,4,5,6,7,8,9],[H1, H2, H3, H4, H5, H6, H7, H8, H9]),
perm([1,2,3,4,5,6,7,8,9],[I1, I2, I3, I4, I5, I6, I7, I8, I9]),
/* ahora damos la restricción:
la suma de cada columna debe dar 45 */
suma(A1,B1,C1,D1,E1,F1,G1,H1,I1, 45),
suma(A2,B2,C2,D2,E2,F2,G2,H2,I2, 45),
suma(A3,B3,C3,D3,E3,F3,G3,H3,I3, 45),
suma(A4,B4,C4,D4,E4,F4,G4,H4,I4, 45),
suma(A5,B5,C5,D5,E5,F5,G5,H5,I5, 45),
suma(A6,B6,C6,D6,E6,F6,G6,H6,I6, 45),
suma(A7,B7,C7,D7,E7,F7,G7,H7,I7, 45),
suma(A8,B8,C8,D8,E8,F8,G8,H8,I8, 45),
suma(A9,B9,C9,D9,E9,F9,G9,H9,I9, 45),
/* ponemos ahora la restricción de las cajas:
cada caja debe sumar 45 */
suma(A1,A2,A3,B1,B2,B3,C1,C2,C3, 45),
suma(A4,A5,A6,B4,B5,B6,C4,C5,C6, 45),
suma(A7,A8,A9,B7,B8,B9,C7,C8,C9, 45),
suma(D1,D2,D3,E1,E2,E3,F1,F2,F3, 45),
suma(D4,D5,D6,E4,E5,E6,F4,F5,F6, 45),
suma(D7,D8,D9,E7,E8,E9,F7,F8,F9, 45),
suma(G1,G2,G3,H1,H2,H3,I1,I2,I3, 45),
suma(G4,G5,G6,H4,H5,H6,I4,I5,I6, 45),
suma(G7,G8,G9,H7,H8,H9,I7,I8,I9, 45),
nl,nl,nl,
/* escribe los resultados */
escribe(A1,B1,C1,D1,E1,F1,G1,H1,I1),
escribe(A2,B2,C2,D2,E2,F2,G2,H2,I2),
escribe(A3,B3,C3,D3,E3,F3,G3,H3,I3),
escribe(A4,B4,C4,D4,E4,F4,G4,H4,I4),
escribe(A5,B5,C5,D5,E5,F5,G5,H5,I5),
escribe(A6,B6,C6,D6,E6,F6,G6,H6,I6),
escribe(A7,B7,C7,D7,E7,F7,G7,H7,I7),
escribe(A8,B8,C8,D8,E8,F8,G8,H8,I8),
escribe(A9,B9,C9,D9,E9,F9,G9,H9,I9),
nl,nl,nl.
La teoría del código es ésta:
Para crear un sudoku tengo que poner, en una cuadrícula de 9x9, en cada línea, 9 números diferentes (del 1 al 9, para ser preciso). Para ello, utilizo el procedimiento
perm (las permutaciones, hallado ya escrito en Internet), y genero una permutación de los 9 elementos. Actúo de igual manera para el renglón 2, 3, hasta el 9, de la cuadrícula del sudoku. Es claro que para cada renglón, la suma de sus elementos siempre dará 45.
Ahora bien, ahora debo exigirle al software que los números que ponga en cada renglón, en la
suma de sus columnas, dé también 45. Con ello bastaría -pensaba- para que el sistema buscara todas las soluciones sin problemas. No obstante, podría haber combinaciones de números, no necesariamente todos diferentes, que dieran 45, por lo cual agregué la restricción de que cada caja de 3x3 tuviese también que sumar 45.
Intenté ejecutar este programa en turbo prolog (agregando las secciones de
domains, predicates, clauses y goal), pero el sistema me marcó un error parecido a: "
too many structures in a predicate error", lo cual obviamente no tiene solución. Intenté entonces en SwiProlog, pero el sistema se quedó "pensando" y después de un largo rato me harté y cancelé la ejecución del mismo.
¿Qué está pasando? La realidad es que Prolog en teoría podría resolverlo en un tiempo finito, pero la cantidad de cálculos que tiene que hacer parece que sobrepasa todas las expectativas. Por ejemplo, permutar 9 objetos diferentes implica 9!, lo cual es 362880.
Cuando el programa corre, pone la primera permutación de 9! para cada renglón, la cual da:
123456789
123456789
123456789
123456789
123456789
123456789
123456789
123456789
123456789
Obviamente, al pasar a hacer la primera suma, la de cada columna,
suma(A1,B1,C1,D1,E1,F1,G1,H1,I1, 45)
fallará e intentará vía backtrack, la siguiente permutación de la última línea, lo cual podría darle algo así como esto:
123456789
123456789
123456789
123456789
123456789
123456789
123456789
123456789
213456789
como puede verse, la primera suma de nuevo no podrá hacerse, por lo que el sistema buscará todas las permutaciones, pero ninguna dará el resultado necesario. Así, hará backtrack sobre la permutación de la octava línea, con resultados parecidos, y así hacia atrás sucesivamente. Eventualmente encontrará permutaciones que cumplan con eso, pero tendrá que verificar también la suma de las cajas de 3x3. Cuando eso falle, hará de nuevo backtrack y así estará por un buen rato. de nuevo, en algún momento, esperaría, el sistema podría hallar la solución adecuada, pero para ello el programa habrá tenido que hacer un sinnúmero de permutaciones inválidas hasta hallar alguna adecuada.
Mis cálculos estiman que el sistema tendría que hacer, en total, para resolver el problema completamente, con todas las posibles soluciones, alrededor de
1.09 x 10^50
iteraciones, lo cual resulta una cantidad inmanejable para la computadora casera.
Estrictamente hablando, el programa presentado crea todos los posibles sudokus que pueden generarse.
De acuerdo a un artículo de Tom Davis [1], no se sabe aún cuál es la cantidad mínima de números dados para que el sudoku tenga solución, aunque hay ejemplos que parecen indicar que 17 números es el mínimo indispensable. Hallo además que un par de matemáticos del Reino Unido y Alemania [2], indican que han revisado la cantidad de posibles sudokus:
5,472,730,538
¡El número de posibles sudokus es verdaderamente inmenso! (más de cinco mil millones).
El código que escribí en Prolog es sin duda la aproximación más purista en este lenguaje para resolver el problema de generar pasatiempos como el sudoku. Desafortunadamente las computadoras caseras no pueden resolverlo por falta de recursos, probablemente en particular en lo que se refiere a memoria y a implementación del lenguaje usado. Buscaré que la UNAM me permita usar la supercomputadora que poseé, a ver si puede entonces el sistema hallar al menos una solución en tiempo finito. Seguiremos informando.
----------
[1]
http://www.geometer.org/mathcircles/sudoku.pdf[2]
http://www.afjarvis.staff.shef.ac.uk/sudoku/