La semana pasada compré una revista y en esta encontré un concurso que consistía en rellenar un Sudoku hexadecimal (16x16) y enviar el resultado para participar. Con los Sudokus normales (0-9 digitos) suelo tardar 1 o 2 horas en resolverlo o incluso dejarlo sin acabar por lo que no puedo imaginarme cuanto tardaría con este. Sin embargo, la idea de participar en el concurso me pareció atractiva. Así que la solución que opte es hacer un programa que me lo resolviese :). Pues bién, implementar el algoritmo puede costar unos 10 minutos. (He aquí una prueba de eficiencia que demuestra que hay que intentar automatizar todo lo posible en cualquier proyecto de software y evitar hacer las cosas manualmente.)
Algoritmos de búsqueda
Resolver este tipo de problemas mediante un algoritmo es relativamente fácil ya que se puede utilizar multitud de algoritmos de inteligencia artificial como los de busqueda o backtracking. Al hablar de inteligencia artificial parece que estamos hablando de algo complejo por la fama que se le ha dado en el cine. Sin embargo, si no hablo de inteligencia artificial y digo que es hacer que el ordenador pruebe cosas hasta que sale ya parece algo más fácil. Y de hecho tiene más de artificial que de inteligencia :).
La problemática de este tipo de soluciones es la velocidad en resolución en ciertos casos. Al intentar probar todas las posibles combinaciones hay que tener mucho cuidado de que el algoritmo no intente realizar operaciones redundantes o de una gran cantidad de combinaciones para así llegar antes al resultado. Una forma de representar todas las combinaciones es con un árbol o un grafo. En este se dibujar un posible estado (posición del tablero) y una flecha por cada movimiento que se puede realizar de manera que si estás en un estado (nodo) y realizas un movimiento (flecha) llegas a otro estado (nodo). Lo interesante es recorrer ese nodo de manera adecuada y eficiente.
La representación del tablero y variables de optimización
En el caso del Sudoku hexadecimal, hemos representado el tablero en un array de 16x16 y para optimizar hemos creado tres matrices de booleanos de 16x16. Estas matrices sirven para marcar si en una misma fila, columna o recuadro ya hemos puesto ese número y así evitar pasar por estados imposibles del tablero y así ser más eficiente en la busqueda. De esta manera cuando ponemos un número en el tablero, marcamos la correspondiente fila, columna y cuadro para que no lo intente poner en un futuro. Si con ese número no ha funcionado y vamos a probar con otro, liberamos las casillas antes marcadas.
Algoritmos recursivos
Desde el punto de vista de algorítmica, hemos implementado un algoritmo recursivo. Yo personalmente no soy un fan de los algoritmos recursivos, pero tampoco les tengo manía. Tiene sus cosas buenas y malas. Recuerdo que cuando daba clases, la gente entiendía antes un algoritmo no recursivo que un algoritmo recursivo. En un algoritmo no recursivo se vé cuando algo se repite ya que lo estás indicando explícitamente. Un algoritmo recursivo hay que darse cuenta que has hecho una llamada a tí mismo (o de manera indirecta) para darte cuenta que eso se repite. Sin embargo, una vez comprendidos te das cuenta que para recorridos de árboles y gráfos se realizan con menos código.
Pues nada, os dejo el programa para que os lo descargueis. Tiene una matriz Sudoku inicial con valores 0-15 e indicando con -1 las casillas a recorrer. Tras ejecutar el algoritmo recursivo de resolución de Sudokus mostrará la solución. El algoritmo muestra todas las soluciones posibles. En el caso de la revista claramente solo hay una posible solución.
Finalmente un reto fácil para que participeis.
Si os apetece, os puedo proponer un reto de nivel fácil. ¿Como se hace un Sudoku? ¿Quien decide que letras se ponen? Pues bién, no hay un señor que se dedique a poner letras al azar y que salga lo que salga. Para que un Sudoku tenga una única posible solución solo se puede hacer a través de un algoritmo. Hacerlo a ojo sería muy dificil. La propuesta que os hago esta vez para que implementeis es crear un generador de Sudokus hexadecimales que genere el tablero totalmente al azar (tanto de números como de casillas libres) y que al resolverlo solo haya una solución posible (y cada Sudoku tiene combinatoria diferente, no vale utilizar un mismo Sudoku alternando los números o rotarlos 90º). El primero que me lo envié lo publicaremos aquí ... y se me ocurre que se puede preparar una especie de muro o zona con las personas o nicks que primero envían cada reto :)
Algoritmos de búsqueda
Resolver este tipo de problemas mediante un algoritmo es relativamente fácil ya que se puede utilizar multitud de algoritmos de inteligencia artificial como los de busqueda o backtracking. Al hablar de inteligencia artificial parece que estamos hablando de algo complejo por la fama que se le ha dado en el cine. Sin embargo, si no hablo de inteligencia artificial y digo que es hacer que el ordenador pruebe cosas hasta que sale ya parece algo más fácil. Y de hecho tiene más de artificial que de inteligencia :).
La problemática de este tipo de soluciones es la velocidad en resolución en ciertos casos. Al intentar probar todas las posibles combinaciones hay que tener mucho cuidado de que el algoritmo no intente realizar operaciones redundantes o de una gran cantidad de combinaciones para así llegar antes al resultado. Una forma de representar todas las combinaciones es con un árbol o un grafo. En este se dibujar un posible estado (posición del tablero) y una flecha por cada movimiento que se puede realizar de manera que si estás en un estado (nodo) y realizas un movimiento (flecha) llegas a otro estado (nodo). Lo interesante es recorrer ese nodo de manera adecuada y eficiente.
En el caso del Sudoku hexadecimal, hemos representado el tablero en un array de 16x16 y para optimizar hemos creado tres matrices de booleanos de 16x16. Estas matrices sirven para marcar si en una misma fila, columna o recuadro ya hemos puesto ese número y así evitar pasar por estados imposibles del tablero y así ser más eficiente en la busqueda. De esta manera cuando ponemos un número en el tablero, marcamos la correspondiente fila, columna y cuadro para que no lo intente poner en un futuro. Si con ese número no ha funcionado y vamos a probar con otro, liberamos las casillas antes marcadas.
Algoritmos recursivos
Desde el punto de vista de algorítmica, hemos implementado un algoritmo recursivo. Yo personalmente no soy un fan de los algoritmos recursivos, pero tampoco les tengo manía. Tiene sus cosas buenas y malas. Recuerdo que cuando daba clases, la gente entiendía antes un algoritmo no recursivo que un algoritmo recursivo. En un algoritmo no recursivo se vé cuando algo se repite ya que lo estás indicando explícitamente. Un algoritmo recursivo hay que darse cuenta que has hecho una llamada a tí mismo (o de manera indirecta) para darte cuenta que eso se repite. Sin embargo, una vez comprendidos te das cuenta que para recorridos de árboles y gráfos se realizan con menos código.
Pues nada, os dejo el programa para que os lo descargueis. Tiene una matriz Sudoku inicial con valores 0-15 e indicando con -1 las casillas a recorrer. Tras ejecutar el algoritmo recursivo de resolución de Sudokus mostrará la solución. El algoritmo muestra todas las soluciones posibles. En el caso de la revista claramente solo hay una posible solución.
Finalmente un reto fácil para que participeis.
Si os apetece, os puedo proponer un reto de nivel fácil. ¿Como se hace un Sudoku? ¿Quien decide que letras se ponen? Pues bién, no hay un señor que se dedique a poner letras al azar y que salga lo que salga. Para que un Sudoku tenga una única posible solución solo se puede hacer a través de un algoritmo. Hacerlo a ojo sería muy dificil. La propuesta que os hago esta vez para que implementeis es crear un generador de Sudokus hexadecimales que genere el tablero totalmente al azar (tanto de números como de casillas libres) y que al resolverlo solo haya una solución posible (y cada Sudoku tiene combinatoria diferente, no vale utilizar un mismo Sudoku alternando los números o rotarlos 90º). El primero que me lo envié lo publicaremos aquí ... y se me ocurre que se puede preparar una especie de muro o zona con las personas o nicks que primero envían cada reto :)
Aquí podeis descargar el código fuente.
ACTUALIZACION: Sobre el reto, se me olvidaba comentar ... a
Para complementar un poco el tema :)
ResponderEliminarhttp://es.debugmodeon.com/articulo/resolviendo-sudokus-i-conocer-el-problema
Con algunos comentarios interesantes.
Hola, implemente algo en java para resolver sudokus, tal vez les sirva tambien
ResponderEliminarhttp://usandojava.blogspot.com/2012/09/resolviendo-sudokus-paso-paso-usando.html