Amigos de lo Ajeno

Introducción

El sudoku, también conocido como “Number Place”, es un juego lógico, cuyo objetivo es relativamente simple: tomando como base los números que ya vienen dados emplazar en cada una de sus casillas, un número que no se encuentre ya ni en su misma columna ni en su misma fila, ni en su mismo cuadrante o sector.

Hay distintos modelos de sudokus, pero el más extendido, es el que consta de 9 filas y 9 columnas, con 9 casillas en cada uno de sus 9 cuadrantes, así, en cada una de sus filas columnas y cuadrantes hay que colocar los números del 1 al 9. Un ejemplo podría ser el siguiente:

Presentación de la solució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 Alfil y el peón, los recorridos del rey y las n-Damas .

Subo mi propio programa 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.

Proceso de resolución

El tablero del Sudoku a resolver viene dado por una matriz “Sol [1..9,1..9] de 0..9” donde Sol[i, j] representa el valor que toma dicha celda, correspondiéndose el valor 0 con una casilla vacía. Se utilizará una matriz auxiliar “inicial[1..9, 1..9] de Bool” donde inicial[i, j] representa una celda con valor inicial que no se puede modificar y se corresponde con la celda “Sol[i, j]”.

A la hora de ramificar el árbol de exploración, solo lo haremos si la solución parcial que estamos atendiendo es k-prometedora, esto es, si a partir de dicha solución parcial podremos seguir construyendo soluciones parciales. Para atender a este punto, utilizaremos una función auxiliar denominada “es_factible”.

El árbol de exploración generado tendrá las siguientes características:

• Altura = m + 1: Siendo m el número de casillas vacías inicialmente.
• Nº de Hijos de cada nodo = 9: Un hijo por cada posible valor de la celda ij

Descarga

El programa que he realizado recoge todos los ficheros de texto que están en la carpeta debug del proyecto y los procesa generando un fichero solución por cada sudoku y un fichero resumen general con los tiempos tardados en resolver cada uno de ellos. Dejo el código fuente y una memoria en pdf.