/sudoku en C++ (otra vez)
Ya había hablado de Sudoku, y hay muchos sitios para resolver Sudoku en C++ usando la técnica de backtracking, pero este sitio me gustó porque explica un poco más en detalle en lo que consiste ese tipo de algoritmos: una búsqueda en profundidad en el árbol de soluciones posibles (estados del juego), y así analizádolas va desarrollando la solución definitiva.
Si bien lo ataca vagamente, vale como una unión de conceptos interesantes.
2 comentarios:
Hola Ro! Bueno, hace un tiempo que voy, cada tanto siguiendo este site. Vos sabés que a ppio de año encaré este problema de hacer un algoritmo que resolviera un sudoku. Comencé con una función recursiva haciendo una especie de "fuerza bruta":
En cada casilla libre, ponía el primer número del 0-9 que me fuera permitido; y procedía así hasta que me quedaba "trabado". Cuando esto pasaba, volvía al anterior, lo incrementaba, y volvía a lo mismo. Inmediatamente saltaron dos problemas: 1) Era repugnatemente lento ese algoritmo. 2) Era muy probable que se tildara la máquina por problema de memoria.
Conclusión: abandoné pero abiendo "diseñado" un nuevo algoritmo. Es medio complicado de explicar y no se si fuinciona, pero aún no lo he probado. Como justo comencé el cursado y las obligaciones de siempre, abandoné y no me puse a leer ni nada; pero ahora que lo veo acá, me acuerdo y me han dado ganas de retomar un poco.
Bueno, nos vemos!! Saludos!!!
Nacho Rigoni
Hola Nacho, welcome :). Mirá, pensé en atacar la solución por backtracking porque a diferencia de fza bruta, tenes funciones parciales o predicados de poda que te indican si un juego de valores (tupla) te conduce o no a una solución. De es modo evitas recorrer todas, quizás fue lo que te sucedió, quedaste varado donde no la había. Y otro de los motivos, es porque la solución del Sudoku es un cuadrado latino, aunque el Sudoku tiene otras restricciones añadidas.
Muchas algoritmos basados en backtracking no tienen un buen orden. Nonetheless, es la mejor solución a veces.
Había pensado en resolverlo sin apelar a esa técnica para comparar ordenes, tiempos, recursos de memoria, etc.
La idea en papel (sin probar): generar un sudoku para descarar numeros. Ingresar los números de la tabla seguidos con posiciones aleatorias, por ej, empezar con el 1 en el primer cuadrado 3x3 en una de las nueve posiciones posibles, y seguir con el nro siguiente. Así con los demás cuadrados 3x3 hasta que lleguemos al último.
Luego pasar al siguiente número y hacer lo mismo. Claro que este método debe tener en cuenta las reglas del Sudoku a la hora de revisar los números que hay en la matriz, aunque podemos ignorar la comprobación de 3x3, ya que el número que estamos introduciendo en la tabla de 3x3 no estará repetido.
Es conveniente que haya alguna forma de saber qué posiciones de las 9 posibles se ha probado (estructura auxiliar), más que nada para evitar el usar demasiados
ciclos de procesador.
Veremos si me da, sobre todo pensando en cual técnica es mejor para móviles.
Saludos
Publicar un comentario