Sudoku
Publicado por Gaston (1 intervención) el 18/11/2005 02:34:11
Hola, en la facultad me propusieron hacer un Sudoku en Pascal y la verdad no tengo mucha idea de como. Me gustaria que alguien pueda ayudarme a hacerlo, lo necesito para el viernes 25.
La guia q me dan es la siguiente:
begin
inicializar-estructuras;
leer-sudoku;
repeat
desplegar numero de recorrida;
para cada celda (i,j) hacer
if (existe d unico en (i,j)) then
begin
asignar d a la celda (i,j);
desplegar "(i,j) -> d (unico)"
end
else if (existe d exclusivo en (i,j)) then
begin
asignar d a la celda (i,j);
desplegar " (i,j) -> d (exclusivo)";
end;
incrementar numero de recorrida;
until (sudoku-completo) o (no-hubo-cambios);
if no-hubo-cambios then
desplegar mensaje;
mostrar sudoku
end
Estructuras de datos
La definición del tablero es clara:
type
Digito = '0'..'9';
TTablero = array [1..9,1..9] of Digito;
Los ceros se utilizan para representar los lugares vacíos. Los dígitos también podrían ser enteros, pero no hay necesidad puesto que no se realiza ninguna aritmética sobre ellos.
Es fundamental poder manejar el conjunto de candidatos de cada celda. Una opción es calcularlo cada vez que se necesita, pero esto es muy costoso. La mejor opción parece ser una estructura así:
type
TCandidatos = array [1..9,1..9] of ConjDeDigitos;
Donde ConjDeDigitos es un tipo que representa el conjunto de candidatos de una celda. Se puede definir de varias maneras. Recomendamos la siguiente representación:
ConjDeDigitos = array [1..10] of Char;
Esta representación es un array con centinela. Se ocupan los primeros lugares del arreglo con los elementos del conjunto y se utiliza un carácter especial para marcar el fin de los datos.
Así, por ejemplo el conjunto {1,2,3} se puede representar así:
1
3
2
@
?
x
a
5
7
#
Observar:
El orden no es relevante.
El centinela es '@'
Los caracteres luego del centinela son “basura”.
El conjunto vacío se representa con un arreglo cuyo primer elemento es el centinela.
Es necesario implementar algunas operaciones mínimas para el tipo conjunto de dígitos:
function esVacioConj(conj : ConjDeDigitos): boolean
procedure quitarConj(d : Digito; var conj: ConjDeDigitos)
function largoConj(conj : ConjDeDigitos) : integer
function pertenece(d : digito; conj: ConjDeDigitos): boolean
Se pueden agregar más operaciones de ser necesarias. Puede ser útil una operación para descubrir candidatos únicos:
function esUnico(d : Digito; conj: ConjDeDigitos): boolean
Algunas líneas generales:
Al inicio comenzamos con el tablero vacío y los conjuntos de candidatos completos.
Se recomienda hacer un procedimiento que permita colocar un dígito en una celda del tablero y actualice todos los conjuntos de candidatos afectados.
La lectura del sudoku llama al procedimiento anterior para cada dítigo del tablero (distinto de cero).
Acerca de las recorridas
El programa contiene muchas recorridas parciales y totales de las estructuras. Muchas de estas recorridas buscan alguna celda con cierta condición (por ejemplo cuando queremos verificar si un candidato es exclusivo). Es imporatante no continuar la recorrida una vez que se encontró lo deseado (dicho de otro modo, no hacerlas con for)
Sobre la región
Una de las recorridas más complejas es la de la región. Una ayuda para recorrer la región que contiene una celda:
function comienzoRegion(i : Rango): Rango;
begin
comienzoRegion:= (i - 1) div 3 * 3 + 1
end;
function finRegion(i : Rango): Rango;
begin
finRegion:= ((i - 1) div 3 + 1) * 3
end;
Estas dos funciones nos permiten hallar rápidamente la columna o fila de comienzo y fin de una región. Si se desea recorrer completamente la región que contiene a la celda (i,j) se puede hacer lo siguiente:
for k:= comienzoRegion(i) to finRegion(i) do
for p:= comienzoRegion(j) to finRegion(j) do
...
Observar que si la recorrida es una búsqueda la estructura FOR no sería la adecuada.
La guia q me dan es la siguiente:
begin
inicializar-estructuras;
leer-sudoku;
repeat
desplegar numero de recorrida;
para cada celda (i,j) hacer
if (existe d unico en (i,j)) then
begin
asignar d a la celda (i,j);
desplegar "(i,j) -> d (unico)"
end
else if (existe d exclusivo en (i,j)) then
begin
asignar d a la celda (i,j);
desplegar " (i,j) -> d (exclusivo)";
end;
incrementar numero de recorrida;
until (sudoku-completo) o (no-hubo-cambios);
if no-hubo-cambios then
desplegar mensaje;
mostrar sudoku
end
Estructuras de datos
La definición del tablero es clara:
type
Digito = '0'..'9';
TTablero = array [1..9,1..9] of Digito;
Los ceros se utilizan para representar los lugares vacíos. Los dígitos también podrían ser enteros, pero no hay necesidad puesto que no se realiza ninguna aritmética sobre ellos.
Es fundamental poder manejar el conjunto de candidatos de cada celda. Una opción es calcularlo cada vez que se necesita, pero esto es muy costoso. La mejor opción parece ser una estructura así:
type
TCandidatos = array [1..9,1..9] of ConjDeDigitos;
Donde ConjDeDigitos es un tipo que representa el conjunto de candidatos de una celda. Se puede definir de varias maneras. Recomendamos la siguiente representación:
ConjDeDigitos = array [1..10] of Char;
Esta representación es un array con centinela. Se ocupan los primeros lugares del arreglo con los elementos del conjunto y se utiliza un carácter especial para marcar el fin de los datos.
Así, por ejemplo el conjunto {1,2,3} se puede representar así:
1
3
2
@
?
x
a
5
7
#
Observar:
El orden no es relevante.
El centinela es '@'
Los caracteres luego del centinela son “basura”.
El conjunto vacío se representa con un arreglo cuyo primer elemento es el centinela.
Es necesario implementar algunas operaciones mínimas para el tipo conjunto de dígitos:
function esVacioConj(conj : ConjDeDigitos): boolean
procedure quitarConj(d : Digito; var conj: ConjDeDigitos)
function largoConj(conj : ConjDeDigitos) : integer
function pertenece(d : digito; conj: ConjDeDigitos): boolean
Se pueden agregar más operaciones de ser necesarias. Puede ser útil una operación para descubrir candidatos únicos:
function esUnico(d : Digito; conj: ConjDeDigitos): boolean
Algunas líneas generales:
Al inicio comenzamos con el tablero vacío y los conjuntos de candidatos completos.
Se recomienda hacer un procedimiento que permita colocar un dígito en una celda del tablero y actualice todos los conjuntos de candidatos afectados.
La lectura del sudoku llama al procedimiento anterior para cada dítigo del tablero (distinto de cero).
Acerca de las recorridas
El programa contiene muchas recorridas parciales y totales de las estructuras. Muchas de estas recorridas buscan alguna celda con cierta condición (por ejemplo cuando queremos verificar si un candidato es exclusivo). Es imporatante no continuar la recorrida una vez que se encontró lo deseado (dicho de otro modo, no hacerlas con for)
Sobre la región
Una de las recorridas más complejas es la de la región. Una ayuda para recorrer la región que contiene una celda:
function comienzoRegion(i : Rango): Rango;
begin
comienzoRegion:= (i - 1) div 3 * 3 + 1
end;
function finRegion(i : Rango): Rango;
begin
finRegion:= ((i - 1) div 3 + 1) * 3
end;
Estas dos funciones nos permiten hallar rápidamente la columna o fila de comienzo y fin de una región. Si se desea recorrer completamente la región que contiene a la celda (i,j) se puede hacer lo siguiente:
for k:= comienzoRegion(i) to finRegion(i) do
for p:= comienzoRegion(j) to finRegion(j) do
...
Observar que si la recorrida es una búsqueda la estructura FOR no sería la adecuada.
Valora esta pregunta


0