Sudoku ramificació i poda

El famós joc del Sudoku consistix en reblir una gaveta de 9 x 9 celes dispostes en 9 subgrups de 3 x 3 celes, en números de l'1 al 9, atenent a la restricció de que no es deu repetir el mateix número en la mateixa fila, columna o subgrup de 9.

Un Sudoku dispon de vàries celes en un valor inicial, de modo que devem escomençar a resoldre el problema a partir d'esta solució parcial sense modificar cap de les celes inicials.

Estratègia de resolució usant Ramificació i poda

El joc del Sudoku no és un problema de optimación, en lo que no recorrerem l'arbre de busca guiant-nos en una funció de cost.

A diferència dels algoritmes de Regrés Arrere, en Ramificació i Poda podem fer un recorregut per nivells de l'arbre d'exploració, gestionant els nodos vius en una coa.

El tauler del Sudoku a resoldre ve dau per una matriu “Sol [1..9,1..9] de 0..9” a on Sol[i, j] representa el valor que pren dita cela, corresponent-se el valor 0 en una casella buida.

S'utilisarà en este apartat una matriu auxiliar “inicial[1..9, 1..9] de Bool” a on inicial[i, j] representa una cela en valor inicial que no es pot modificar i es correspon en la cela “Sol[i, j]”.

A l'hora de ramificar l'arbre d'exploració, solament ho farem si la solució parcial que estem atenent és k-prometedora, açò és, si a partir de dita solució parcial podrem seguir construint solucions parcials. Per a atendre a este punt, utilisarem una funció auxiliar denominada “és_factible”, detallada en l'eixemple del Sudoku en Regrés Arrere.

La funció “és_factible” comprova per a una cela determinada, que no es repetixca el seu valor en la mateixa fila, columna o subgrup de 3x3, atenent aixina a la restricció que comentàvem en la descripció detallada del problema.

Ya que un Sudoku pot tindre vàries solucions, implementarem l'algoritme en conseqüència.

Estructures de senyes necessàries

En cada iteración de l'algoritme, necessitarem saber l'estat de la solució parcial al complet, per a això necessitem:

1. La solució parcial fins al moment.
2. Informació sobre la casella en la que nos trobem (fila i columna);

NODO = Registre
        fila, columna : Nat;
        Sol : Vector [1..9, 1..9] de 0..9;
       FRegistro;

La coa per a gestionar els nodos vius serà:

Vius: coa de NODO;

Vore també

• Algoritmes per a la resolució de sudokus
• Sudoku backtracking