jmidas
16 de Junio del 2008

Tengo que resolver un sudoku por ramificacion y poda en c++,el algoritmo que uso es el de la wikipedia:

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

Fun 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> 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> 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;


Con las funciones auxiliares:

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> resultado := 1;
k = 2 -> resultado := 4;
k = 3 -> resultado := 7;
FCasos;
Devolver resultado;
FFun;



Se que tiene los siguientes fallos:
*Funci贸n es_Factible: antes del final del primer "Mientras" y del segundo, falta incrementar k, y entre medias de ellos,
hacer k=1. En el "Mientras" anidado posterior, falta incrementar l antes de terminar el "Mientras" interior, e incrementar k antes
de terminar el "Mientras" exterior
*Funci贸n sudoku_RyP: hay que cambiar "Y.columna := Y.columna + 1;" por "Y.columna := X.columna + 1" las dos veces que aparece. Adem谩s,
hay que cambiar en la condici贸n "Si (inicial [X.fila, X.columna] = Falso)" Falso por Cierto, o bien modificar la inicializaci贸n de la
matriz booleana "inicial" que aparece antes cambiando Falso por Cierto y viceversa, porque est谩 al rev茅s.

Si alguien pudiese poner este algoritmo en c++ a ser posible probando que funciona se lo agradeceria mucho puesto que no domino el c++ y por mas que lo intento no consigo que me salga bien.