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.
- ¿Cuáles son las principales diferencias, con ejemplos, entre un algoritmo de aprendizaje profundo y un algoritmo de aprendizaje de refuerzo?
- ¿Cuáles son algunos buenos tutoriales que dividen, conquistan y analizan los algoritmos más complejos jamás diseñados?
- ¿Cuáles son los mejores algoritmos para el análisis de sentimientos?
- ¿Cuál es el mejor algoritmo para encontrar una ruta más corta a través de todos los puntos de control dados?
- ¿Es seguro decir que las recomendaciones sociales siempre superarán a los algoritmos controlados por computadora?
Piensa en un laberinto o un laberinto: ¿cómo encuentras el camino desde una entrada hasta 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
- Como todos los demás problemas de Backtracking, podemos resolver Sudoku uno por uno asignando números a celdas vacías.
- 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.
- 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.
- 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 Backtracking Recursivo | Code Pumpkin: contiene una explicación clara y la implementación del programa Java. Vale la pena leer..!!
