Sudoku en pascal Buenas, estoy haciendo un trabajo para la facultad y la verdad que hay una parte del trabajo que me supero,
La letra:
La tarea. Resolver un sudoku
4. Terminología.
4.1 Fila, Columna y Región
Consideraremos un sudoku como una matriz de 9x9 y utilizaremos los términos fila y columna con su significado habitual. Una fila es una secuencia de 9 celdas contiguas alineadas horizontalmente. Una columna es una secuencia de 9 celdas contiguas alineadas verticalmente. Utilizaremos los números del 0 al 8 para identificar las filas y columnas. Las filas se numeran de izquierda a derecha, las columnas de arriba hacia abajo. Una celda se identifica por un par (i,j) donde i representa la fila y j la columna.
Utilizaremos el término región para referirnos a cada una de las 9 subcuadrículas de 3x3. Las regiones se identifican con un par (m,n) con m y n entre 0 y 2, de izquierda a derecha y de arriba hacia abajo. Así por ejemplo la región (0,1) contiene el conjundo de celdas: { (i,j) : 0 ≤ i ≤ 2, 3 ≤ j ≤ 5 }
4.2 Candidato de una celda
Dado un sudoku, un número d ∈ {1,2,3,4,5,6,7,8,9} es un candidato para la celda (i,j) vacía, si se cumple que d no aparece en la fila i, ni en la columna j , ni en la región que contiene a la celda (i,j).
Notar que candidato sólo se define para las celdas vacías.
C(S,i,j) representa el conjunto de candidatos de la celda (i,j) en el sudoku S.
Así por ejemplo, si llamamos S1 al sudoku de la primera figura, tendremos:
C(S1,0,0) = { 2, 8, 9}
C(S1,8,8) = { 9 }
El conjunto de candidatos definido aquí es en realidad lo que llamamos conjunto inicial de candidatos ya que luego veremos, que este conjunto puede reducirse aplicando tácticas apropiadas.
En esta tarea no aplicaremos métodos de ensayo y error sino que nos limitaremos a las tácticas que se describen a continuación.
5.1 Candidato único
Decimos que un dígito d es candidato único para una celda (i,j) en un sudoku S si se cumple que:
C(S,i,j) = { d }
Cuando esto se cumple podemos asegurar que la celda (i,j) debe ser ocupada por el dígito d.
5.2 Candidato exclusivo
Decimos que un dígito d es un candidato exclusivo de una celda (i,j), si d es candidato para esa celda y además se cumple al menos una de las siguientes condiciones:
d no es candidato de ninguna otra celda en la fila i (exclusivo en fila).
d no es candidato de ninguna otra celda en la columna j (exclusivo en columna).
d no es candidato de ninguna otra celda en la region que contiene a la celda (i,j) (exclusivo en región).
Cuando esto se cumple podemos asegurar que la celda (i,j) debe ser ocupada por el dígito d.
5.3 Tácticas de reducción de candidatos
Las dos tácticas anteriores permiten identificar de manera inequívoca cuál es el valor que debe asignarse a una celda. La aplicación de ambas tácticas permite resulver un número importante de sudokus calificados como de nivel fácil pero no son suficientes para resolver muchos sudokus (nivel medio, difícil, extremo, etcétera).
Cuando no se detecta ninguna celda que cumpla con las condiciones de candidato único o exclusivo, surge la aplicación de tácticas que permiten descartar ciertos candidatos de una o más celdas y por eso se denominan de reducción de candidatos. La aplicación de una o más de estas tácticas dará lugar a la aparición de nuevos candidatos únicos y exclusivos y así se continuará alternando ambas familias de tácticas hasta resolver todas las celdas.
6. ESTRUCTURA DE DATOS
6.1 El tablero
Se define la siguiente estructura para representar el tablero de un sudoku:
type
Rango9 = 0..8;
Digito = '0'..'9';
TipoTablero = array [Rango9,Rango9] of Digito;
Si tenemos una variable S de tipo tablero entonces S[i,j] contiene el valor asignado a la celda ubicada en la fila i, columna j El carácter ‘0′ se utiliza para representar una celda vacía.
6.2 Candidatos
En todas las estrategias de resolución resulta fundamental llevar registro de los candidatos de las celdas aún por completar. Se propone la siguiente estructura de datos:
type
ConjuntoDigito = set of Digito;
TipoCandidatos = array [Rango9,Rango9] of ConjuntoDigito;
El tipo set de Pascal es utilizado para representar el conjunto de candidatos de una celda libre.
Para las celdas ocupadas el conjunto de candidatos es irrelevante por lo que lo tomaremos como el conjunto vacío.
7. Subprogramas
En esta parte se deben implementar los siguientes subprogramas:
function SudokuCorrecto(tablero: TipoTablero) : boolean;
{ RESUELTO}
function SudokuResuelto(tablero: TipoTablero) : boolean;
{ RESUELTO}
procedure CrearCandidatos(tablero: TipoTablero; var candidatos: TipoCandidatos);
{ NI IDEA COMO HACERLO }
8. Se pide
Escribir un archivo con todos los subprogramas solicitados.
Las funciones no tuve problema para hacerlas pero el procedimiento no tengo idea como hacerlo en pascal(La idea a lapiz si)
LA idea que tengo para el procedimiento es:
leer filas columnas y regiones, después recorrer el tablero y en cada celda igual a '0' asignar todos los valores(1 al 9) y restarles los que hay en esa fila esa comuna y esa región,
Pero no se implementarlo en Pascal , agradeceréis la ayuda, les dejo el link de la web si quieren ver mejor la tarea:
http://www.fing.edu.uy/inco/cursos/prog1/pm/field.php/Laboratorio/LetraTareaDos2012-0
