Estrategia de resolución usando
Backtracking
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”.
La función “es_factible” comprueba para una celda determinada, que no se repita su valor en la misma fila, columna o subgrupo de 3x3, atendiendo así a la restricción que comentábamos en la descripción detallada del problema.
Dado que un
Sudoku Puede tener varias soluciones, implementaremos el algoritmo en consecuencia.
Árbol de exploración
El árbol de exploración generado tendrá las siguientes características:
-
- 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 i j.
