Hace tiempo ya, empecé con este asunto de los sudokus y la programación. La realidad es que este pasatiempo mental da muchas posibilidades para la ciencia de la computación. Por ejemplo, aquí esbozamos un sistema en Prolog para generar sudokus legales. El problema realmente es que puede llevar muchísimo tiempo que el sistema dé con una solución, pues Prolog está pensado para ser exhaustivo, para hallar todas las posibles soluciones. Si tomamos en cuenta que cada línea, columna y caja (3x3) debe tener 9 números diferentes, podemos usar un algoritmo primero para poner las 9 cifras diferentes en los casilleros y entonces hacer los cálculos que se necesitan. Sin embargo, para un sudoku real, de 9x9, es decir, 81 casillas, tenemos que calcular las permutaciones de 9 objetos, en 9 columnas. Ya escribí al respecto aquí.
Hoy me di a la tarea de escribir un programa en Prolog que resolviese sudokus. Se le da al sistema el sudoku con los números que son interrogantes y el sistema empieza a buscar todas las posibles soluciones. Por ejemplo, tomé este primer sudoku, uno muy sencillo:
Generé entonces mi programa en Prolog para resolver este sudoku en particular:
predicates
sudoku
suma(integer, integer, integer, integer, integer,
integer, integer, integer, integer, integer)
num(integer)
clauses
num(1).
num(2).
num(3).
num(4).
num(5).
num(6).
num(7).
num(8).
num(9).
suma(A,B,C,D,E,F,G,H,I,R) :-
A+B+C+D+E+F+G+H+I = R.
sudoku :- num(A1), num(B1), num(C1), num(D1),
num(A2), num(B2), num(C2), num(D2),
num(E2), num(F2), num(G2), num(H2),
num(A3), num(B3), num(C3), num(D3),
num(E3),
num(A4), num(B4), num(C4), num(D4),
num(A5), num(B5), num(C5), num(D5),
num(A6), num(B6), num(C6), num(D6),
num(A7), num(B7), num(C7), num(D7),
num(E7),
num(A8), num(B8), num(C8), num(D8),
num(E8),
num(F8), num(G8), num(H8),
num(A9), num(B9), num(C9), num(D9),
/* horizontales */
suma(5,A1,4,3,B1,6,C1,7,D1,45),
suma(A2,B2,1,C2,D2,E2,F2,G2,H2,45),
suma(A3,7,6,B3,C3,2,9,D3,E3,45),
suma(A4,8,B4,7,C4,5,6,D4,1,45),
suma(7,6,A5,B5,3,C5,D5,8,9,45),
suma(9,A6,3,8,B6,4,C6,2,D6,45),
suma(A7,B7,8,1,C7,D7,2,9,E7,45),
suma(A8,B8,C8,D8,E8,F8,3,G8,H8,45),
suma(A9,3,B9,4,C9,7,1,D9,6,45),
/* verticales */
suma(5,A2,A3,A4,7,9,A7,A8,A9,45),
suma(A1,B2,7,8,6,A6,B7,B8,3,45),
suma(4,1,6,B4,A5,3,8,C8,B9,45),
suma(3,C2,B3,7,B5,8,1,D8,4,45),
suma(B1,D2,C3,C4,3,B6,C7,E8,C9,45),
suma(6,E2,2,5,C5,4,D7,F8,7,45),
suma(C1,F2,9,6,D5,C6,2,3,1,45),
suma(7,G2,D3,D4,8,2,9,G8,D9,45),
suma(D1,H2,E3,1,9,D6,E7,H8,6,45),
/* cajas */
suma(5,A1,4,A2,B2,1,A3,7,6,45),
suma(3,B1,6,C2,D2,E2,B3,C3,2,45),
suma(C1,7,D1,F2,G2,H2,9,D3,E3,45),
suma(A4,8,B4,7,6,A5,9,A6,3,45),
suma(7,C4,5,B5,3,C5,8,B6,4,45),
suma(6,D4,1,D5,8,9,C6,2,D6,45),
suma(A7,B7,8,A8,B8,C8,A9,3,B9,45),
suma(1,C7,D7,D8,E8,F8,4,C9,7,45),
suma(2,9,E7,3,G8,H8,1,D9,6,45).
Evidentemente éste es el enfoque de "fuerza bruta", el cual es clásico en Prolog. Los sudokus son un ejemplo de programa que en Prolog se vuelven no deterministico, es decir, no podemos saber a priori si existe una solución al problema hasta que Prolog no busque todas las soluciones posibles.
Curiosamente, aunque Prolog se usa como un enfoque de la Inteligencia Artificial (IA) para resolver problemas de forma inteligente, valga la redundancia, el programa que presentamos aquí no exhibe ninguna inteligencia, a lo más una terquedad del algoritmo de Robinsson, para poner todos las posibles valores en las incógnitas y así poderlo resolver.
¿Podrá mi programa resolver el sudoku planteado? ¿Cuánto tiempo le llevará? No voy a contestar por el momento a esto (se analizará en el siguiente artículo). En el mientras, ¿qué cree estimado lector/a que pase? ¿Cuánto tiempo sería el estimado para resolver este sudoku al cual le faltan 44 números? Será poco tiempo? ¿será mucho tiempo? ¿Qué mejoras podrían hacerse al programa? ¿Esta técnica exhaustiva es lo correcto en este problema en particular?
Tidak ada komentar:
Posting Komentar