Cómo escribir un programa que resuelva un Sudoku usando backtraking y sets

Answer 1

Sudoku se puede resolver utilizando el algoritmo de seguimiento recursivo.

¿Qué es el algoritmo de retroceso?

En los algoritmos de retroceso, intenta construir una solución paso a paso. Si en algún paso queda claro que la ruta actual en la que se encuentra no puede conducir a una solución, regrese al paso anterior (retroceso) y elija una ruta diferente. Brevemente, una vez que agota todas sus opciones en un cierto paso, retrocede.

Piensa en un laberinto o un laberinto: ¿cómo encuentras el camino desde una entrada a una salida? Una vez que llegue a un callejón sin salida, debe retroceder. ¿Pero retroceder a dónde? al punto de elección anterior. El retroceso también se conoce como búsqueda en profundidad .

Enfoque para resolver el sudoku usando el algoritmo de retroceso recursivo

1. Como todos los demás problemas de Backtracking, podemos resolver Sudoku uno por uno asignando números a celdas vacías.
2. Antes de asignar un número, debemos confirmar que el mismo número no está presente en la fila actual, la columna actual y la subcuadrícula 3X3 actual.
3. Si el número no está presente en la fila, columna o subcuadrícula respectiva, podemos asignar el número y verificar de forma recursiva si esta asignación conduce a una solución o no.
4. Si la asignación no conduce a una solución, entonces intentamos el siguiente número para la celda vacía actual. Y si ninguno de los números (1 a 9) conduce a la solución, devolvemos falso y volvemos a la celda anterior e intentamos el siguiente número posible allí.

Referencia:

Solucionador de Sudoku usando Backcurcking Recursivo | Code Pumpkin: contiene una explicación clara y la implementación del programa Java. Vale la pena leer..!!

Answer 2

No estoy seguro de qué son exactamente los backtracking y los sets (o qué crees que son), pero así es como escribiría ese programa:

1. cree una matriz de nueve elementos con índices numéricos donde cada valor sea otra matriz de nueve elementos. (también conocido como una matriz bidimensional). Estos representan las filas y columnas del rompecabezas sodoku.
2. Para cada uno de los valores de matriz más internos, cree un objeto, el objeto tiene una propiedad llamada valor y nueve propiedades llamadas possibleValue1, possibleValue2, etc.
3. Fase 1, Rellenar valores iniciales: para cada objeto (que representa un cuadrado en el tablero) determine si el valor ya está establecido, si es así, establezca la propiedad “valor” de ese objeto en cualquier valor numérico para ese cuadrado. Si el valor no está establecido, establezca los valores de todos los parámetros posiblesValue en true.
4. Fase 2, opciones de eliminación: para cada objeto (nuevamente) verifique si la propiedad “value” está establecida, si es así, luego repita sobre cualquier otro objeto que comparta la misma clave en ambas dimensiones de la matriz bidimensional y establezca el posibleValue que coincide con el valor del objeto de cuadro en falso. (en inglés, esto significa que si el cuadro está configurado en 3, elimine la posible opción de 3 de cualquier otro cuadro en la misma fila o columna.
5. Fase 3, Determinar valores: para cada objeto (nuevamente) verifique cuántas opciones posibles están establecidas en verdadero. si solo uno está establecido en verdadero, establezca el valor de ese cuadro en verdadero.
6. repita los pasos 4 y 5 una y otra vez. Además, durante cada iteración debe llevar un recuento de cuántos valores se establecieron. al final de la iteración, si no se establecieron valores, sabrá que tiene una situación en la que múltiples respuestas podrían ser verdaderas. si este es el caso, establezca un indicador que diga “elija uno” que indicará que la próxima vez que necesite “Determinar valores” y no detecte solo 1 opción, debe elegir una de las opciones disponibles y luego salga inmediatamente de la iteración y regrese al paso Eliminar opciones.
7. y, por último, debe mantener un registro en ejecución de cuántos cuadros no están configurados en un valor, cuando ese número llega a cero, el programa sale y muestra resultados

Answer 3

Hice el programa de solución de sudoku en Java. La lógica es simple, comprobando el valor en fila, en columna y en el cuadro. Para realizar un seguimiento de los valores, debe usar el bucle anidado, obviamente. Puedes consultar el programa en mi blog quora. Traté de hacerlo simple, pero si tiene algún problema con la lógica, no dude en enviarme un mensaje.