Lacosox Sudoku Solver Adictive Edition

17 junio, 2008 at 13:10

En la sección inferior de un diario salía un cuadro… “Entretenidos problemas de SUDOKU”,  habían 2, uno que decía “Nivel Fácil” y “Nivel Difícil”..

Como a mi me gusta complicarme la vida evidentemente comencé con el “Nivel Difícil”, al poco andar ya no podía seguir llenando casillas sin estar seguro de lo que ponía, las dudas comenzaron… y mi capacidad para resolver este tipo de problemas se estaba poniendo en duda….  asi que tomé una desición bastante simple, para evitarme terminar siendo un fracasado preferí hacer el “Nivel Fácil”… a las pocas horas me dí cuenta que era una farza, el nivel fácil no tenía nada de fácil… estaba lleno de trampas y practicamente era imposible de resolver sin usar algún tipo de torpedo…

Fue entonces cuando en un momento de descanzo recordé que tenía un computador a menos de 2 metros de donde estaba sentado,  ¡Por fin podría resolver los problemas!… pero existe un problema.. no tenía conexión a internet que me permitiera buscar algún software para resolver sudokus, no me quedaba que escribir un programa yo mismo…  ¿o aceptar la derrota?, jamás!… (detalle completo después del corte)

 

Para resolver el problema existen varias alternativas, entre ellas:

  • Utilizar fuerza bruta y verificar todas las posibildades hasta encontrar la solución.
  • Seguir un árbol de posibilidades, validando las ramas antes de ejecutarlas. Utilizando la lógica “que pasa si pongo 1 en esta casilla”
  • Utilizar una lógica más humana, utilizando la lógica “¿que número puedo poner en esta casilla?”

La primera alternativa es muy flaite. La tercera alternativa resulta ser una solución más elegante, pero implica algunas horas extra de programación. Apliquemos la segunda alternativa y veamos los tiempos de reacción….

Seguir una lógica de un árbol de posibilidades es bastante simple de implementar, la idea es verificar todos los posibles caminos, que tenemos y cuando encontremos un problema, volveremos al paso donde realizamos la última decisión, con el fin único de tomar otro camino. Tal cual se hace cuando se resuelve un laberinto.

Luego de implementada la lógica era la hora de testear el problema que el diario me planteaba.

sc1

Problema resulto en tan solo 58 milisegundos, es por eso que amo estas máquinas 😀 . El total de iteraciones equivale a la cantidad conbinaciones que intentó antes de encontrar la solución, algo así como 307 posibilidades de caminos erroneos y 1 camino correcto para completar el laberinto.

El programa se detiene al encontrar la primera solución, por lo tanto no se está seguro si en realidad existan más soluciones para el mismo problema. Aunque por lo general con una solución basta.

El programa está escrito en lenguaje Java, y debe ejecutarse en modo texto indicando como parámetro el problema a resolver, simplemete indique las casillas de izquierda a derecha y de arriba hacia abajo, indicado un 0 para las casillas en blanco.

Queda el código fuente disponible para todos quienes quieran estudiarlo, modificarlo, perfeccionarlo y hacerse millonarios con él.

Solo se recomienda que no se utilce mucho, se han notificado casos en que usuarios se vuelven “adictos” a resolver Sudokus con esta herramienta, probablemente al ver que los resultados los entrega tan rápidamente.

ACTUALIZACIÓN: Ahora puedes revisar el código fuente en GitHub o, si aún lo quieres, bajarlo directamente.

LacosoxSudokuSolverAdictiveEdition.tar
Título: LacosoxSudokuSolverAdictiveEdition.tar (0 click)
Leyenda:
Filename: lacosoxsudokusolveradictiveedition-tar.gz
Size: 10 KB