Backtracking: Volviendo atrás
Volviendo hacia atrás en el blog algunas semanas -haciendo backtracking-, comentaba el uso de la recursividad en la programación y lo interesante que resultaba definir algo contenido en la misma definición.
El Backtracking es una técnica de programación de la que se puede partir de la definición de Recursividad (vease definición de recursividad) con la diferencia que, en el backtracking, al existir varios caminos diferentes a elegir, una vez llegado al final y no cumplirse la condición establecida, volvemos atrás para seguir buscando caminos diferentes o alternativos y posiblemente correctos.
La idea del backtracking, si aún no la has entendido, se ve bastante bien en estos ejemplos del Laberinto y las n-Damas (en Java).
Finalmente, como lo prometido es deuda, subo la práctica comentada en el anterior artículo sobre recursividad que resuelve sudokus planteados por medio de la técnica del backtracking. Recordar que no es la mejor técnica ni mucho menos para resolver Sudokus, sino prácticamente usar la fuerza bruta para resolverlos con la posibilidad de volver atrás y buscar más caminos.
El programa está realizado para Free Pascal y permite:
- Insertar números uno a uno (comprobando si es posible insertar el número según las reglas)
- Cargar y salvar en un fichero de tipo propio los sudokus creados
- Intentar resolver el sudoku mediante backtracking indicandote si tiene varias, única o ninguna solución y calculando el tiempo que tarda en resolverlo.
- Borrar el sudoku actual del panel
- Insertar un sudoku predefinido por coordenadas (ojo! este no comprueba si los números son válidos).
Hay bastante cosas que son mejorables, como por ejemplo quitar algunas variables globales o la inclusión de eliminar algunos números insertando un cero (por ejemplo), pero eso lo dejo para el que quiera modificarlo, asi como el que se anime y lo «traduzca» a otro lenguaje de programación estaré encantado en incorporarlo al artículo.
Programa para resolver sudokus en Free Pascal con algunos ficheros de ejemplo.