Sudoku ramificació i poda
De Viquipèdia
Taula de continguts |
[edita] Descripció detallada del problema
- El famós joc del 'Sudoku consisteix en omplir un quadre de 9x9 cel·les organtizades en 9 subgrups de 3x3 cel·les, amb nombres de l'1 al 9, atenint-se a la restricció de que no es pot repetir el mateix nombre en la mateixa fila, columna o subgrup de 9.
- Un Sudoku disposa de vàries cel·les amb un valor inicial, així que hem de començar a resoldre el problema a partir d'aquesta solució parcial sense modificar cap de les cel·les inicials.
[edita] Estratègia de resolució amb Ramificació i poda
- El joc del Sudoku no és un problema d'optimització, per tant no recorrerem l'àrbre de cerca guiant-nos amb una funció de costos.
- A diferència dels algoritmes de Tornar Enrere, amb Ramificació i Poda podem fer un recorregut per nivells de l'àrbre d'exploració, gestionant els nòdes vius amb una cua.
- El tauler del Sudoku per resoldre vé donat per una matriu "Sol [1..9,1..9] de 0..9" on Sol[i,j] representa el valor que pren l'esmentada cel·la, on el valor zero es correspon amb una casella buida.
- S'utilitzarà en aquest apartat una matriu auxiliar "inicial[1..9,1..9] de Bool" on inicial[i,j] representa una cel·la amb valor inicial que no es pot modificar i es correspon amb la cel·la "Sol[i,j]".
- A l'hora de ramificar l'[Arbre (teoria de gràfs)|arbre] d'exploració, només ho fem si la solució parcial que estem atenent és k-prometedora, això vol dir, si a partir d'aquesta solució parcial podrem seguir construïnt solucions parcials. Per atendre aquest punt, utilitzarem la funció auxiliar denominada es_factible, detallada en l'exemple del Sudoku amb Tornar Enrere.
- La funció es_factible comproba per una cel·la determinada, que no es repeteixi el seu valor en la mateixa fila, columna o subgrup de 3x3, atenent-se així a la restrició que comentàvem en la descripció del probelma.
- Donat que un Sudoku pot tindre varies solucions, implementarem l'algorisme en conseqüència.
[edita] Estructures de dades necessàries
- Encada iteració de l'algorisme necessitarem saber l'estat de la solució parcial, per tant necessitarem:
- La solucio parcial fins al moment.
- Informació en quant a la casella en la que ens trobem (fila i columna);
NODE = Registre
fila, columna : Nat; Sol : Vector [1..9, 1..9] de 0..9; FRegistre;
- La cua per gestionar els nòdes vius serà:
Vius: cua de NÒDE;
[edita] Arbre d'exploració
- L'arbre d'exploració tindrà les següents característiques:
- Alçada = m+1, sent m el nombre de caselles buides inicialment.
- Nombre màxim de fills de cada nòde = 9, un fill per cada possible valor de la cel·la i,j.
[edita] Implementació en Pseudocodi
Fun sudoku_RiP ( sol[1..9, 1..9] de 0..9) Var Vius: cua de NODE; X,Y: NODE; inicial[1..9, 1..9] de Bool; FVar; Vius := cua_buida(); //Preparem l'arrel de l'arbre d'exploració X.fila := 1; X.columna := 1; X.sol := sol; demanar_veg (Vius, X); Per (i := 1) Fins 9 Fer //Inicializació de la matriu amb els inicials Per (j := 1) Fins 9 Fer Si (Sol[i, j] != 0) Llavors Inicial[i, j] := Fals; En altre cas Inicial[i, j] := Cert; FSi; FPer; FPer; Mentre ( cua_buida(Vius) = Fals ) Fer X := atendre (Vius); Si (inicial [X.fila, X.columna] = Fals) Llavors Per (k := 1) Fins 9 Fer X.sol[X.fila, X.columna] := k; Si (es_factible (X.fila, X.columna, X.sol)) Llavors Casos X.fila = 9 ^ X.columna = 9 -> mostrarPerPantalla( X.sol); X.fila < 9 ^ X.columna = 9 -> Y.sol := X.sol; Y.fila := X.fila + 1; Y.columna := 1; demanar_veg(Vius, Y); X.fila <= 9 ^ X.columna < 9 -> Y.sol := X.sol; Y.fila := X.fila; Y.columna := Y.columna + 1; demanar_veg(Vius, Y); FCasos; FSi; FPer; En Altre Cas //inicial[X.fila, X.columna] = Cert Casos X.fila = 9 ^ X.columna = 9 -> mostrarPerPantalla( X.sol); X.fila < 9 ^ X.columna = 9 -> Y.sol := X.sol; Y.fila := X.fila + 1; Y.columna := 1; demanar_veg(Vius, Y); X.fila <= 9 ^ X.columna < 9 -> Y.sol := X.sol; Y.fila := X.fila; Y.columna := Y.columna + 1; demanar_veg(Vius, Y); FCasos; FSi; FMentres; FFun;
[edita] Funcions Auxiliars
- Funció auxiliar que comprova la factibilitat d'una solució parcial.
Fun es_factible (i, j : Nat; sol[1..9, 1..9] de 0..9) DEV Bool Var valid : Bool; k, l : Nat; FVar; valid := Cert; k := 1; Mentres (k <= 9 ^ valid) Fer //Comprovem la fila Si ( sol[i, j] = sol[i, k] ^ k != j ) Fer valid := Fals; FSi; FMientres; k := 1; Mientres (k <= 9 ^ valid) Fer //Comprovem la columna Si ( sol[i, j] = sol[k, j] ^ k != i ){ Valid := Fals; FSi; FMentres; k := correspondencia3x3(i); l := correspondencia3x3(j); //Comprobamos el subgrupo de 3x3 Mentres ( k < correspondencia3x3(i) + 3 ^ valid ) Fer Mentras ( l < correspondencia3x3(j) + 3 ^ valid) Fer Si ( sol[i, j] = sol[k, l] ^ i != k ^ j != l) Llavors valid := Fals; FSi; FMentres; FMentres; Retornar valid; FFun;
- Funció auxiliar que s'utilitza per averiguar la cel·la inicial des de la que farem la comprovació de factibilitat d'una cel·la determinada en el seu corresponent subgrup de 3x3 cel·les.
Fun correspondencia3x3 (i: Nat) DEV Nat Var k : Nat; resultat: Nat; FVar; Si ( i MOD 3 = 0) Llavors k := (i DIV 3); En Altre Cas k := ( I DIV 3) + 1; FSi; Casos k = 1 -> resultat := 1; k = 2 -> resultat := 4; k = 3 -> resultat := 7; FCasos; Retornar resultat; FFun;
[edita] Altres estragègies de resolució
- Sudoku backtracking
[edita] Bibliografia
- Plantilla:Ref-llibre