Tuesday, March 02, 2010

Programación Lógica y Sudokus

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/

18 comments:

Fernando C. Estrada said...

En Austria estaban utilizando la computación voluntaria por medio de la plataforma BOINC [1] para el proyecto llamado Sudoku [2], cuya finalidad era encontrar el juego de Sudoku mínimo (es decir, encontrar el mínimo número de pistas que deben darse para un juego de Sudoku con el fin de generar un rompecabezas con una solución única). Lamentablemente el proyecto y el sitio no estan disponibles desde Octubre del año pasado, se supone que su investigación concluyó pero no han dado a conocer aún los resultados.

En caso que no puedas contactar a los miembros de este proyecto para conocer sus resultados, y tengas problemas para acceder a la infraestructura del área de super cómputo en la UNAM, podrías considerar darle una oportunidad a la computación voluntaria, con lo cual ya no sería cierto que "Desafortunadamente las computadoras caseras no pueden resolverlo por falta de recursos".

Un ejemplo del uso de la computación voluntaria lo estan dando en Extremadura (España) con el proyecto EXTREMADURATHOME [3]. Con todo gusto me gustaría participar en un proyecto parecido, y que mejor que desarrollarlo en la máxima casa de estudios donde muchos investigadores podrían verse beneficiados.

Saludos y quedo a Tus órdenes.

Fernando C. Estrada
http://twitter.com/fcestrada

[1] http://boinc.berkeley.edu/
[2] http://dist2.ist.tugraz.at/sudoku/
[3] http://www.extremadurathome.org/

secretaria said...

Hola, muy interesante artículo, pero entonces ¿Cómo los programas "comerciales" resuelven sudokus?

Saludos

Jorge said...

Hola Manuel:

¡Caray! ¡Me hiciste recordar viejos
tiempos!

Como Ing. en Computación que soy (aunque ahora más dedicado a la implementación de redes y Sistemas Operativos),me puse a ver tu código.

Me hiciste recordar viejos tiempos
en que uno batallaba con los
procedimientos recursivos.

Pero esto es otra liga.

¡Ojalá te permitan usar el equipo!

Como siempre un saludo.

Jorge Alberto.

Por cierto: ¿Todavía usan las
CRAY?

Siempre fué como un sueño para mí
el poder usar una de ellas.

Ernesto said...

Y esto resuleve sudokus:

def r(a):i=a.find('0');~i or exit(a);[m
in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for
j in range(81)]or r(a[:i]+m+a[i+1:])for m in'%d'%5**18]
from sys import*;r(argv[1])


En python.

Salió de aquí:

http://stackoverflow.com/questions/201461/shortest-sudoku-solver-in-python-how-does-it-work

Sudokus!
Ernesto

Ernesto said...

Creo que podrías eliminar la restricción de que cada renglón y columna sumen 45.

Al permutar los números de 1 al 9 en un renglón o columna siempre va a sumar 45.

Hace mucho que no uso Prolog.

Saludos,
Ernesto

Ernesto said...

Ya entendí lo que estás haciendo.

Perdón.

Ernesto said...

En realidad el número posible de sudokus es muy pequeño si se compara con el número de permutaciones de números en 81 casillas.

9!x8!x8!x7!x7!x6!x6!x5!x5!x4!x4!x3!x3!x2!x2!x1!x1!x0!=

9278496603801318870491332608000000000

Morsa said...

Hola, Fernando,

Ya estoy viendo la chance de usar la supercompu de la UNAM. Nomás tenga más datos y te informo por si quieres entrarle. Creo podríamos hacer alguna investigación simpática sobre este tema.

saludos
Manuel

Ps. La invitación es abierta a todos los que quieran colaborar.

Morsa said...

Secretaria,

Voy a escribir pronto algo sobre cómo es que los generan los programas actuales.

saludos
Manuel

Morsa said...

Ernesto,

Interesante el código en Python, Me estás obligando a estudiar ahora este lenguaje... Aunque el código no crea sudokus, los resuelve, lo cual es otra cara de la moneda.

saludos
Manuel

Morsa said...

Jorge,

Pues ya empecé a mover este asunto. A ver si se puede usar la supercomputadora.

No sé a todo esto, si siguen usando la Cray, creo que sí, pero tienen otros equipos multiprocesadores, aunque creo que son escalares y nov ectoriales como lo era la Cray.

saludos
Manuel

Francisco said...

Recuerdo que el famoso y prolífico matemático Paul Erdos era muy bueno para planter problemas "intermedios", cuando el problema completo era muy difícil.

Podrías aplicar tu algoritmo y programa para resolver un sudoku de menor dimensión? No sé nada de sudokus pero me parece que el siguiente hacia abajo sería uno de 4x4 con 4 bloques de 2x2.

Es posible? Existen estos mini-sudokus?

Si resuelves este más sencillo así al menos ya estarías totalmente seguro que solamente es una cuestión de tiempo de máquina al extrapolar al 9x9.

Saludos,

Ernesto said...

Hola Manuel,

Creo que sería mejor usar Ruby en lugar de Phyton.
Por estas razones.

Corre en casi cualquier plataforma. (CRAY tal vez, Windows, Linux, Mac)
Es tan expresivo como Python.
Te permite hacer hilos múltiples de ejecución.
Inclusive mandar esos hilos a otras computadoras.
Puedes envolver C en funciones de Ruby

Creo que usar backtrack no es lo mejor, por lo inmenso del conjunto de soluciones.

Creo que es mejor ir creando soluciones de forma secuencial e ir descartando las que no sean sodokus válidos. (o crearlos de forma que sólo se creen sodokus válidos)

Morsa said...

Francisco,

Sí, existen estos mini-sudokus. Probaré más tarde con 4x4 y te daré los resultados.

saludos
Manuel

Morsa said...

Ernesto,

Quizás tengas razón en lo de Ruby. Lo que es claro es que usar backtrack no parece ser la mejor idea.

saludos
Manuel

R. Daneel Olivaw said...

Superinteresante, esto me recuerda cuestiones de calculo como los números perfectos y demás curiosidades matemáticas muy interesantes.

Chochos said...

Me encontré este artículo acerca de un generador y solucionador de sudokus, que además es software libre. Utiliza varias técnicas distintas para resolver y generarlos, tal vez te sea de utilidad, ya que puedes ver el código: http://ow.ly/1qdW0

Krazy Vivaldon said...

Manuel:
Te envié por correo "mi intento" de solución en Prolog de los Sudoku's.

Estoy trabajando en el de 9x9.

Para el de 4x4 te he enviado la solución, el cual, sin darle ningún valor previo, puede generarte sudokus

El de 6x6, dándole algunos valores previos, arroja la solución (pero cabe señalar que tarda un rato considerable). Yo creo que (dejándolo trabajar más tiempo) podría arrojar un sudoku.

Revisalos!!