Sudoku ramificación y poda

El famoso juego del Sudoku consiste en rellenar un cubo de 9 x 9 celdas dispuestas en 9 subgrupos de 3 x 3 celdas, con números del 1 al 9, atendiendo a la restricción de que no se debe repetir el mismo número en la misma fila, columna o subgrupo de 9.

Un Sudoku dispone de varias celdas con un valor inicial, de modo que debemos empezar a resolver el problema a partir de esta solución parcial sin modificar ninguna de las celdas iniciales.

Estrategia de resolución usando Ramificación y poda

El juego del Sudoku no es un problema de optimación, con lo cual no recorreremos el árbol de búsqueda guiándonos con una función de coste.

A diferencia de los algoritmos de Vuelta Atrás, con Ramificación y Poda podemos hacer un recorrido por niveles del árbol de exploración, gestionando los nodos vivos con una cola.

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á en este apartado 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”, detallada en el ejemplo del Sudoku con Vuelta Atrás.

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.

Other Languages