En la imagen puedes apreciar:
A - Una fila
B - Una columna
C - Un bloque
Hay 9 filas, 9 columnas y 9 bloques, es fácil contrarlos.
Cuando digo que necesitamos 3 arrays, son uno para guardar los valores de una fila dada, otro para una columna dada y otro para un bloque dado... los 3 son de 9 elementos, porque 9 son las casillas que tienen, aunque el array va del 0 al 8.
------------------------------
Así cuando digo este pseudocodigo:
Código:
TmpFila = GetValoresEnFila(Entero Y)
TmpColumna = GetValoresEnColumna(Entero X)
TmpBloque = GetValoresEnBloque(Entero X, Entero Y)
Me estoy refiriendo a 3 funciones distintas que reciben uno o dos parámetros y devuelven un array... en la siguiente imagen vemos que datos deberían devolver estas 3 funciones, con más claridad.
He marcado un circulito en la casilla que queremos rellenar, al caso es la posición:
X= 5
Y = 5
- Bien si llamo a la función GetvaloresEnFila (x), me debe devolver un array con los valores en la fila x (fila 5), el array siempre será de 9 elementos, y los valores (en este orden) serán: 3,7,8,1,4,0,0,0,0 y se almacena en el array tmpFila
- Cuando llame a la función GetValoresEncolumna(y), me debe devolver un array con los valores en la columna y (columna 5), el array siempre será de 9 elementos, y los valores (también en el orden en que aparecen) serán: 9,4,5,3,7,0,0,0,0 y se almacena en el array tmpColumna
- Finalmente cuando llame a la función GetValoresEnBloque(x,y), me debe devolver un array con los valores que contiene el bloque que contiene la casilla que le paso. La casilla puede ser cualquiera en el bloque. La función debe calcular cual es la posición dx y dy donde se localiza la primera casilla de dicho bloque, a partir de ahí lee 3 casillas, aumenta una fila y lee otras 3 aumenta otra fila y lee las 3 últimas... el bloque se compone de 3 filas de las cuales toma 3 columnas. Así los valores que devuelve en orden serán: 9,8,3, 6,2,7, 1,4,0 y se almacenan en el array tmpBloque
En la imagen he seleccionado, la fila, columna y bloques afectados, por tanto un modo de ver que las funciones operan bien es verificar que en efecto devuelven correctamente esos valores. Nota también como los valores de las casillas vacías devuelve un 0, es la forma de identificar que una casilla está libre.
Lógicamente todos los valores que vamos alamcenando van a para a un array de 81 elementos (9x9), un array unidimensional, pero podrías hacerlo bidimensional (aunque las explicaciones del pseudocódigo dado están pensadas para un array unidimensional. al caso es lo mismo. Uno debe ser capaz de traducir de un array unidimensional a uno bidimensional y viceversa, son matemáticas de suma, resta, multiplicación y división, además de módulo.
Y para qué necesitamos estos arrays de valores. Bueno tu eliges al azar un valor del 1 al 9, y luego verificas que no esté en la fila, la columna y el bloque, pero las más de las veces ya estará, así que de nuevo tendrás que pedir otro valor al azar entre 1 y 9 y será muy lento, tanto más cuanto más cerca de estar completo esté el sudoku.
Aquí la forma de ser más inteligentes es primero recoger qué valores están... (ya lo hemos hecho con esas 3 funciones en sendos arrays), lo siguiente es unificar los 3 arrays en uno solo... es decir eliminar los valores repetidos, así la función UnificarCubiculos, hace esto mismo.
Y cómo lo hace. básicamente se crea un array cuyos índices 1,2,3,4,5,6,7,8,9 serán contadores del valor cuyo índice son. es decir cuando en uno de los arrays aparezca por ejemplo tmpFila(3) = 9 entonces en el unificado se hsumará uno al índice 9 tmpUnificado(9) +=1 pero no podemos poner directamente 9, ya que dicho valor está contenido en el array, o lo pasamosa una variable:
v = tmpfila(3) // 'v' vale 9 en este caso
tmpUnificado(v) +=1
o bien lo hacemos directamente sin una varible auxiliar:
tmpUnificado(tmpFila(3)) +=1
Haciendo lo mismo con todo el array tmpFila, tmpColumna, tmpBloque tendremos al final el array con estos valores de cuenta (valores reales obtenidos de la imagen):
tmp(1) = 2
tmp(2) = 1
tmp(3) = 3
tmp(4) = 3 //aparece 3 veces, una en la fila, otra en la columna y otra en el bloque.
tmp(5) = 1
tmp(6) = 1
tmp(7) = 3
tmp(8) = 2
tmp(9) = 2
Obviamente algunos están contados más de una vez, según que formen parte 8por ejemplo) de una fila y una columna, o una columna y un bloque o un bloque y la fila, o incluso de los 3 arrays. No importa, queremos saber cuales aparecen y si hay más de 1 vez aparecen.
Luego este array lo simplificamos para que no sea el índice, si no el valor quien refleje su presencia (al final el valor estará el el mismo índice, pero eso no nos importará luego).
Por eso se hace un bucle de reasignaciónde valores:
Código:
bucle para k desde 1 a 9
si tmp(k) Es mayor que 0 luego
tmp(k) = k // tmp(1) = 1 .... tmp(5)= 5 ... tmp(9) = 9
fin si
fin bucle
Ahora ya hemos únificado los 3 arrays en 1 sólo. y el resumen es que el array contiene todos los valores que están presentes en la fila, columna o bloque a la que la casilla x,y hace referencia.
Lo siguiente entonces es generar un array con los valores que faltan. Para ello con el array de salida de la función UnificarCubiculos (tu ponle el nombre que te dé la gana, siempre que te oriente con su significado), es el parámetro de entrada para la función: TomarAusentes
Da la casulaidad de que en este punto hemos llegado a una situación de bloqueo. Luego te explico por qué...
Ahora mismo tengo que hacer unas cosas, así que envío esto aunque no esté terminado y luego (2-3 horas) pongo otra imagen sin bloqueo y sigo explicando (a partir de ella) y detrás la situación de bloqueo, por qué se produce y la solución para salir adelante...
Editado para reponer las imágenes que parece que la página web las ha eliminado... (afortunadamente las guardaba en la misma carpeta donde hice el programa).