lunes, 24 de enero de 2011

Sudoku Solver

Hace unos días, se anunció que Google Goggles para Android es capaz de resolver un Sudoku, tomando una foto del mismo. Incluso hay un video que muestra como funciona:



También hace unos días, leyendo Coders at Work (buen libro, se recomienda), en la entrevista a Peter Norvig, comenta:
It’s also important to know what you’re doing. When I wrote my Sudoku solver, some bloggers commented on that. They said, “Look at the contrast—here’s Norvig’s Sudoku thing and then there’s this other guy, whose name I’ve forgotten, one of these test-driven design gurus. He starts off and he says, “Well, I’m going to do Sudoku and I’m going to have this class and first thing I’m going to do is write a bunch of tests.” But then he never got anywhere. He had five different blog posts and in each one he wrote a little bit more and wrote lots of tests but he never got anything working because he didn’t know how to solve the problem.
Así que, me dije... ¿qué tan difícil puede ser hacer un programa que resuelva un Sudoku? (no la parte de sacar la foto e interpretarla, solo el algoritmo). Resulta que no es tan difícil...

Pueden ver el código en GitHub: https://github.com/mcrispino/sudoku-solver. Ahí están también las instrucciones para bajarlo y ejecutar el programa.

El programa está escrito en Ruby, mi nuevo lenguaje favorito :) En una próxima nota explicaré alguna parte del código y por qué me gusta como se resuelven en el lenguaje.

El algoritmo es bastante sencillo. Creo que además el código es bastante simple de leer, pero acá va una explicación:

  • se parte de un tablero (clase Board), que es una matriz de 9x9, donde cada elemento es un array con todos los valores posibles, inicialmente todos los números del 1 al 9
  • para cada valor en el tablero original, se carga ese valor en el lugar correspondiente en la matriz, y se elimina de todos los lugares donde ya no puede estar (fila, columna y sub-matriz de 3x3)
  • una vez ubicados todos los números "fijos", se buscan posiciones de la matriz que hayan quedado con un array con un solo elemento (solo hay un posible valor), y para estos se repite el proceso anterior de cambiar el array por el valor y eliminarlo de los posibles valores de las posiciones donde ya no puede estar
  • esto se repite hasta que no hayan más arrays (se encontró una solución), o hasta que no queden arrays con un solo elemento
  • si quedan arrays con más de un elemento, entonces se hace una copia del tablero, se elige uno de los valores posibles, y se intenta resolver
  • si se encuentra una solución, entonces ya está
  • si no se encuentra, se hace backtracking.
Con este algoritmo, la solución se encuentra de forma instantánea. Probé también solo con el backtracking, pero nunca llegó a terminar (tampoco le tuve demasiada paciencia).

Para los que sepan Ruby, se agradecen comentarios, correcciones y sugerencias. Es una buena forma de aprender :)

3 comentarios:

  1. Esta muy bueno!!, derrepente estaría interesante uno que resuelva el Cubo de Rubik, ver si la tecnología del escaneado permite identificar los colores y aplicarle los algoritmos de resolución (se dice que cualquier configuración del cubo se resuelve en menos de 21 pasos),lo que si es que seria tedioso escanear cada una de las 6 caras del cubo y como dar la solución de forma amigable.. bueno tal vez ya exista uno que lo haga..

    saludos.

    ResponderEliminar
  2. Petros:

    Hacer un programa que te de la solución final del cubo Rubik es fácil ;) Yo me animo a hacerlo.

    No, pero en serio, sí podría estar interesante. Te tendría que dar la lista de pasos a seguir para resolverlo.

    ResponderEliminar
  3. Marcos, estaría bien interesante, y la verdad me animaría al reto, sin embargo no domino mucho la tecnología con la que desarrollaron el Sudoku Solver =(, así que si te animas a desarrollarlo, quedaría bárbaro si liberas los fuentes jeje, seguro ahí aprendemos todos =)

    Saludos.

    ResponderEliminar