Pascal/Turbo Pascal - Sudoku

 
Vista:

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.
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder

RE:Sudoku

Publicado por Javier (1 intervención) el 17/04/2007 22:47:09
Vaya,a mi tambien me toco hacer un sudoku,pero lo elegimos como nuestro proyecto.
La verdad es que recien me pasna la materia del array,pero dbeere aprender a hacer un sudoku, ojala me puedan ayudar igual
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

RE:Sudoku

Publicado por cader (1 intervención) el 14/10/2007 01:13:51
Ese tema del sudoku en pascal ya se hizo comun, yo tambien necesito que alguien me ayude con esto, si alguien sabe como hacerlo por favor escribanme.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

RE:Sudoku

Publicado por nosfas (1 intervención) el 27/04/2010 17:57:18
es facil, pones un function dentro de un if dento de un while dentro de un for y dentro de un repeat ademas dentro d euna matriz y eso te da, nada
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

RE:Sudoku

Publicado por amelia (1 intervención) el 27/04/2010 17:59:34
gracias por tu ayuda
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar