Tuesday, March 09, 2010

Postscriptum: Errores en mi código del sudoku


Hace un par de artículos en este blog (dar click aquí), puse mi código en prolog para resolver sudokus. Hablé de la problemática en lo que se refiere a recursos de máquina. Básicamente mi programa hace uso extensivo (y extenuante) del backtrack, por lo cual para un sudoku de 9x9, la máquina puede tardar mucho tiempo y además, puede quedarse sin memoria, por lo cual, en términos reales, no me queda claro que el sistema pueda ser resuelto con la PC.

Ya algunos lectores de este blog han dado alternativas a la que yo propuse, que es usar la supercomputadora de la UNAM para estos menesteres. Ya he hecho algunas indagaciones y espero pronto tener tiempo de máquina en Cómputo Académico, para lidiar con estos problemas masivos de datos.

En el mientras, decidí probar mi programa con un minisudoku de 4x4. Asumiendo que en lugar de tener 9! de permutaciones por línea, tengo solamente 4!, es decir 24 en total, el problema pareciese poderse resolver relativamente de forma rápida. He aquí el código original para 4x4:


/* Generador de Sudokus */
/* Por La_Morsa */
/* minisudoku 4x4 */
/* 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) :-
write(A,B,C,D),nl.

/*permutaciones */
perm([], []).

perm([H|T], R):-
perm(T, X), delete(H, R, X).

suma(A,B,C,DR) :-
A+B+C+D = R.

escribe(A,B,C,D) :-
write(A),
write(B),
write(C),
write(D),
nl.

sudoku :-
/* hallamos primero las permutaciones
de los cuatro renglones */
perm([1,2,3,4],[A1, A2, A3, A4]),
perm([1,2,3,4],[B1, B2, B3, B4]),
perm([1,2,3,4],[C1, C2, C3, C4]),
perm([1,2,3,4],[D1, D2, D3, D4]),

/* ahora damos la restricción:
la suma de cada columna debe dar 10 */
suma(A1,B1,C1,D1, 10),
suma(A2,B2,C2,D2, 10),
suma(A3,B3,C3,D3, 10),
suma(A4,B4,C4,D4, 10),
nl,nl,nl,

/* escribe los resultados */
escribe(A1,B1,C1,D1),
escribe(A2,B2,C2,D2),
escribe(A3,B3,C3,D3),
escribe(A4,B4,C4,D4),
nl,nl,nl.

si ejecutamos este programa, hallaremos que sí, efectivamente el sistema da varias respuestas, pero algunas son equivocadas. Por ejemplo:

1234
1234
4321
4321

lo cual no es una solución como se esperaba. Evidentemente el error es simple: hace falta agregar la restricción para que en cada caja también los valores sumen 10. Así entonces, poniendo esta restricción tenemos que el sistema ya da los resultados correctos:

/* ponemos ahora la restricción de las cajas:
cada caja debe sumar 10 */
suma(A1,A2,B1,B2, 10),
suma(A3,A4,B3,B4, 10),
suma(C1,C2,D1,D2, 10),
suma(C3,C4,D3,D4, 10),

Ahora sí, el programa corre bien y da todas las posibles soluciones de sudokus de 4x4.

3 comments:

Chochos said...

Hace poco vi la adaptación de Tim Burton de Alicia, y el gato de Cheshire me puso a pensar nuevamente en esto de los Sudokus (de manera muy indirecta). Concretamente en la validación, pero tal vez se pueda usar esta idea para la generación de sudokus válidos.

Qué tal si en vez de generar el sudoku en términos de renglones y columnas, se genera en términos de cada número? Es decir, colocar primero los nueve 1's todos en posiciones válidas, luego los nueve 2's en posiciones válidas, etc... de esa manera creo que evitas desde el principio las combinaciones inválidas, puesto que solamente vas a ir colocando números en posiciones válidas.

Si alguien que lea esto le da curiosidad la relación aparentemente inexistente entre este algoritmo para generar/validar sudokus y el gato de Cheshire... Lewis Carroll era (entre otras cosas) matemático, y escondió algunos conceptos en las historias de Alicia. El gato de Cheshire en particular, representa la abstracción que se necesita para comprender bien las matemáticas; la famosa frase de Alicia "había visto un gato sin sonrisa pero jamás una sonrisa sin gato" enfrasca la separación de conceptos que generalmente tenemos siempre asociados mentalmente. Así es que me llegó la idea de que en vez de pensar en términos de renglones y columnas que se deben llenar con números, puede convenir más pensar en términos de cada número e ir colocando cada ocurrencia de cada número en una posición distinta.

En fin estimado Morsa, ahí le dejo esa idea para que la mastique un rato.

Francisco said...

Las rotaciones de 90 grados se cuentan como sudokus diferentes?

Morsa said...

Sí, las rotaciones de 90 grados son sudokus diferentes.

saludos
Manuel