¿Cómo programo un solucionador de Sudoku? ¿Cuál es la lógica detrás de esto?

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

He implementado una versión básica del solucionador de Sudoku. Aunque puedes resolver Sudoku retrocediendo, implementé varias lógicas

Paso 1: encuentre todos los valores posibles para todas las celdas sin resolver.
Paso 2: para cada celda sin resolver, si solo tiene un valor posible, márquelo como resuelto.
Paso 2.1: elimine el valor resuelto previamente de los posibles valores de las siguientes celdas.
*) Todas las celdas sin resolver en el cuadrado actual.
*) Todas las celdas sin resolver en la fila actual.
*) Todas las celdas sin resolver en la columna actual.
Paso 3: para cada fila, si es posible un valor en una sola celda, márquelo como resuelto.
(Por ejemplo, si la primera fila, la quinta celda tiene valores posibles 1,7,9. Pero en la 1ra fila, el valor 7 solo es posible en la quinta celda, luego coloque 7 en la 1ra fila, 5ta celda y márquelo como resuelto).
Setp 3.1: Haz el paso 2.1.
Paso 4 : Realice el paso 3 para la columna seguido del paso 2.1.
Paso 5 : Realice el paso 3 para el cuadrado seguido del paso 2.1.
Paso 6: Para cada fila, cualquier n (donde n <9) celdas, encuentre la unión de los posibles valores de n celdas, digamos U. Si el tamaño de U = n, elimine esos valores de todas las otras celdas no resueltas en la fila actual.
(Por ejemplo, si la primera fila, la quinta celda tiene valores posibles 6, 7 y 8, y la sexta celda tiene un valor posible solo 6 y 7 y 9, la celda tiene 6, 7 y 8. Entonces U = {6, 7, 8}. El tamaño de U es 3 yn = 3 (porque se seleccionaron 3 celdas 5, 6 y 9). Tamaño de U = n, por lo tanto, elimine 6, 7 y 8 del valor posible de todas las celdas sin resolver en la fila actual).
Paso 7: Realice el paso 6 para la columna.
Paso 8: Haz el paso 6 para la celda.
Paso 9: Si se produjo algún cambio (como resuelto o cambio ocurrido en posibles valores de cualquier celda), vaya al Paso 2 .
Paso 10: llenó el máximo de pasos posibles.

Así es como lo resolví, aquí está el enlace Solucionador de Sudoku

Answer 3

Bueno, puedo proporcionarle el enlace a la misma (resuelto usando el seguimiento): -> Backtracking | Set 7 (Sudoku) – GeeksforGeeks (puede preguntar más si hay dudas)

Answer 4

Programa para resolver sudoku- java

Programa Java para resolver el problema de Sudoko