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
editarEl 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.
Estructuras de datos necesarias
editarEn cada iteración del algoritmo, necesitaremos saber el estado de la solución parcial al completo, para ello necesitamos:
- La solución parcial hasta el momento.
- Información sobre la casilla en la que nos encontramos (fila y columna);
NODO = Registro
fila, columna : Nat;
Sol : Vector [1..9, 1..9] de 0..9;
FRegistro;
- La cola para gestionar los nodos vivos será:
Vivos: cola de NODO;
Árbol de exploración
editarEl árbol de exploración generado tendrá las siguientes características:
- Altura = m + 1, siendo m el número de casillas vacías inicialmente.
- N.º máximo de Hijos de cada nodo = 9, un hijo por cada posible valor de la celda i j.
Implementación en Pseudocódigo
editarFun sudoku_RyP ( sol[1..9, 1..9] de 0..9)
Var
Vivos: cola de NODO;
X,Y: NODO;
inicial[1..9, 1..9] de Bool;
FVar;
Vivos := cola_vacia(); //Preparamos la raíz del árbol de exploración
X.fila := 1;
X.columna := 1;
X.sol := sol;
pedir_vez (Vivos, X);
Para (i := 1) Hasta 9 Hacer //Inicialización de la matriz de iniciales
Para (j := 1) Hasta 9 Hacer
Si (Sol[i, j] != 0) Entonces
Inicial[i, j] := Falso;
En Otro Caso
Inicial[i, j] := Cierto;
FSi;
FPara;
FPara;
Mientras ( cola_vacia(Vivos) = Falso ) Hacer
X := atender (Vivos);
Si (inicial [X.fila, X.columna] = Falso) Entonces
Para (k := 1) Hasta 9 Hacer
X.sol[X.fila, X.columna] := k;
Si (es_factible (X.fila, X.columna, X.sol)) Entonces
Casos
X.fila = 9 ^ X.columna = 9 -> mostrarPorPantalla( X.sol);
X.fila < 9 ^ X.columna = 9 -> Y.sol := X.sol;
Y.fila := X.fila + 1;
Y.columna := 1;
pedir_vez(Vivos, Y);
X.fila <= 9 ^ X.columna < 9 -> Y.sol := X.sol;
Y.fila := X.fila;
Y.columna := Y.columna + 1;
pedir_vez(Vivos, Y);
FCasos;
FSi;
FPara;
En Otro Caso //inicial[X.fila, X.columna] = Cierto
Casos
X.fila = 9 ^ X.columna = 9 -> mostrarPorPantalla( X.sol);
X.fila < 9 ^ X.columna = 9 -> Y.sol := X.sol;
Y.fila := X.fila + 1;
Y.columna := 1;
pedir_vez(Vivos, Y);
X.fila <= 9 ^ X.columna < 9 -> Y.sol := X.sol;
Y.fila := X.fila;
Y.columna := Y.columna + 1;
pedir_vez(Vivos, Y);
FCasos;
FSi;
FMientras;
FFun;
Funciones Auxiliares
editarFunción auxiliar que comprueba la factibilidad de una solución parcial.
Fun es_factible (i, j : Nat; sol[1..9, 1..9] de 0..9) DEV Bool
Var
valido : Bool;
k, l : Nat;
FVar;
valido := Cierto;
k := 1;
Mientras (k <= 9 ^ valido) Hacer //Comprobamos la fila
Si ( sol[i, j] = sol[i, k] ^ k != j ) Hacer
valido := Falso;
FSi;
FMientras;
k := 1;
Mientras (k <= 9 ^ valido) Hacer //Comprobamos la columna
Si ( sol[i, j] = sol[k, j] ^ k != i ){
Valido := Falso;
FSi;
FMientras;
k := correspondencia3x3(i);
l := correspondencia3x3(j); //Comprobamos el subgrupo de 3x3
Mientras ( k < correspondencia3x3(i) + 3 ^ valido ) Hacer
Mientras ( l < correspondencia3x3(j) + 3 ^ valido) Hacer
Si ( sol[i, j] = sol[k, l] ^ i != k ^ j != l) Entonces
valido := Falso;
FSi;
FMientras;
FMientras;
Devolver valido;
FFun;
Función auxiliar que se utiliza para averiguar la celda inicial desde la que haremos la comprobación de factibilidad de una celda determinada en su correspondiente subgrupo de 3x3 celdas.
Fun correspondencia3x3 (i: Nat) DEV Nat
Var
k : Nat;
resultado: Nat;
FVar;
Si ( i MOD 3 = 0) Entonces
k := (i DIV 3);
En Otro Caso
k := ( i DIV 3) + 1;
FSi;
Casos
k = 1 -> resultado := 1;
k = 2 -> resultado := 4;
k = 3 -> resultado := 7;
FCasos;
Devolver resultado;
FFun;
Véase también
editar
Datos: Q6135151
