 Autor
|
Tema: Codigo para crear SUDOKUS (Leído 25,264 veces)
|
Editame
 Desconectado
Mensajes: 11
Todo radica en la Humildad !
|
Hola amigos que tal, bueno soy nuevo por aca y no se si este en el lugar equivocado y si es asi pido disculpas a los moderadores y pido redireccionamiento del tema al hilo indicado donde pueda encontrar la ayuda que necesito. Bueno mi inconveniente es el siguiente: - Estoy realizando un sudoku parte de un proyecto de la Universidad y necesito ayuda con el codigo que genera la matriz aleatoriamente, he creado tres funciones para verificar si existe el dato en la fila, columna o cuadrante al parecer todo esta bien pero al correrlo entra en un bucle infinito, al realizar algunas pruebas de escritorio me encontre que sin tener error en el codigo llega a un punto que en la inserccion de los datos no se da ya que no encuentra ningun numero valido a ingresar, en fin dejo el codigo y ya sabran de lo que le hablo adjunto una imagen en una prueba de escritorio que iba haciendo tomado de la consola y muestra hasta donde llega la matriz y que en los valores validos a ingresar no se puede por esa razon sigue evaluando infinitamente  package Clases;
import java.util.Random;
public class Metodos {
static Random ran = new Random();
static int matriz [][] = new int [9][9];
public static void main(String[] args) {
generadorAleatorio();
}
public static void generadorAleatorio (){
int i=0,j;
while (i < 9){
System.out.println("fila: " + i);
j = 0;
while (j < 9){
System.out.println("Columna" + j);
int numero = 1 + ran.nextInt(9);
System.out.println(numero);
System.out.println(busquedaFilas(numero, i));
if (busquedaFilas(numero, i).equalsIgnoreCase("no")) {
System.out.println(busquedaColumnas(numero, j));
if (busquedaColumnas(numero, j).equalsIgnoreCase("no")) {
System.out.println(busquedaCaja(numero, i, j));
if (busquedaCaja(numero, i, j).equalsIgnoreCase("no")) {
matriz[i][j] = numero;
System.out.println(numero + "Valido");
j++;
}
}
}
}
i++;
}
for (int k = 0; k < 9; k++) {
System.out.println("");
for (int l = 0; l < 9; l++) {
System.out.print(matriz[k][l] + "\t");
}
}
}
public static String busquedaFilas (int valor, int filas) {
String resultado = "no";
for (int i = 0; i < 9; i++) {
if (valor == matriz[filas][i]) {
resultado = "si";
break;
}
}
return resultado;
}
public static String busquedaColumnas (int valor, int columnas) {
String resultado = "no";
for (int i = 0; i < 9; i++) {
if (valor == matriz[i][columnas]) {
resultado = "si";
break;
}
}
return resultado;
}
public static String busquedaCaja (int valor, int filas, int columnas) {
int minfila, maxfila;
int mincolum, maxcolum;
if (filas >= 0 && filas < 3) {
minfila = 0;
maxfila = 2;
}else if (filas >= 3 && filas < 6) {
minfila = 3;
maxfila = 5;
}else {
minfila = 6;
maxfila = 8;
}
if (columnas >= 0 && columnas < 3) {
mincolum = 0;
maxcolum = 2;
}else if (columnas >=3 && columnas <6) {
mincolum = 3;
maxcolum = 5;
}else{
mincolum = 6;
maxcolum = 8;
}
String resultado = "no";
for (int i = minfila; i <= maxfila ; i++) {
for (int j = mincolum; j <= maxcolum; j++) {
if (valor == matriz[i][j]) {
resultado = "si";
break;
}
}
}
return resultado;
}
}
|
|
|
|
« Última modificación: 1 Agosto 2017, 08:30 am por Editame »
|
En línea
|
Edilberto Tapias Mercado
Estudiante Ing. Telematica
|
|
|
footer
Desconectado
Mensajes: 37
|
Hola amigo estuve revisando tu codigo y despues de un largo rato llegue a la respuesta: te aclaro que no tengo la solucoin pero tengo la causa del problema. Lo que hice fue escribir tu codigo nuevamente paso a paso e ir verificandolo de a poco, y le puse para que solo me mostrara por consola cuando un numero es valido, sin importarme si ese numero estaba en la fila o no que solo mostrar los numeros validos y me devolvio esto: 8 Valido 1 Valido 7 Valido 3 Valido 4 Valido 6 Valido 2 Valido 5 Valido 9Valido 3 Valido 2 Valido 6 Valido 5 Valido 1 Valido 7 Valido 4 Valido 8 Valido Si acomodas los numeros para formar el sudoku queda asi: |817|346|259| |326|517|48?| Miralo detenidamente... ningun numero se repita horizontalmente, ni verticalmente. Pero falta uno, que es justamente el que causa el bucle infinito. El la primera fila estan todos del 1 al 9 siendo este ultimo el ultimo de la fila, y el la segunda fila estan del 1 al 8, menos el 9... entonces en ese ? solo podria ir el 9 por que los otros ya estan acomodados en la fila, pero eso no puede pasar por que conincidiria con un numero verticalmente, entonces el programa descartara el nueve y sorteara otro numero pero no importa que numero diferente de nueve salga sorteado sea cual sea coincidira con numeros de la fila, conclusion el bucle se produce por un error logico. donde no importa que numero saldra sorteado nunca sera valido. Espero haberme explicado. Mira este otro ejemplo: 2Valido 8Valido 7Valido 3Valido 4Valido 6Valido 5Valido 9Valido 1Valido 4Valido 5Valido 6Valido 7Valido 2Valido 1Valido 8Valido 3Valido |287|346|591| |456|721|83?| Aqui el numero que falta cumple es el 9 si sale sorteado ese numero cumple la condicion de que no exista en la fila y no exista en la columna pero no cumple la condicion de que no exista en el cuadrado de 3x3, es decir numero sortedo < 9 --> se repite en fila asi que se descarta; numero sorteado = 9 se repite en cuadrado 3x3; esto genera error logico. Ultimo ejemplo: 5Valido 8Valido 9Valido 6Valido 4Valido 1Valido 3Valido 2Valido 7Valido 4Valido 3Valido 2Valido 7Valido 9Valido 8Valido 1Valido 5Valido 6Valido 7Valido 6Valido 1Valido 5Valido 2Valido 3Valido 8Valido 4Valido 9Valido 3Valido 5Valido 4Valido 1Valido 7Valido 6Valido 9Valido 8Valido 2Valido 6Valido 1Valido 8Valido 2Valido 3Valido 9Valido 7Valido Esta vez me devolvio varias filas |589|641|327| |432|798|156| |761|523|849| |354|176|982| |618|239|7??| Faltan el 4 y el 5, esta vez el problema esta en la posicion 8 de la ultima fila, si pone un 4 se repite en la columna y si pone un 5 tambien lo hara y si pone cualquier otro numero se repetira en la fila. Lo que podrias hacer es un algoritmo que detecte cuando se producen estos errores y hacer que intente generarlo desde cero hasta q en algun momento haga 9 filas, yo en varios intentos a mano logre que generara 4 filas tal vez en x intentos logre 9  Aqui te dejo el link de descarga del codigo que hice que es identico al tuyo xD pero le cambio algunos nombre a las variables para no perderme en los bucles y el array. link= https://drive.google.com/open?id=0B1i-JNEuRD1zTFlOZzdNMWJMSTA
|
|
|
|
« Última modificación: 30 Julio 2017, 20:18 pm por footer »
|
En línea
|
|
|
|
|
Serapis
|
Sin revisar el código a fondo, parece que el problema del bucle infinito es porque en efecto trata de elegir 'al azar' un número donde solo existe una posibilidad de elección y resulta que esa elección ya está presente. Tal y como te comenta footer. De entrada, no hace falta que busques el 9º número al azar, busca solo los 8 primeros, el 9º será el número que reste de la serie, así evitas el bucle infinito. Y ahora que termina la segunda fila (y siguientes, pero no para la primera) debes verificar si verticalmente también existe conincidencia (y en cada uno de los 3 bloques implicados) en cuyo caso descarta de nuevo la fila actual y la regeneras al azar hasta que se valide, así vas avanzando con cada fila.... -------------------- Sin embargo el método, no es adecuado, vas a tirar mucho de azar para lograr cada Sudoku... Un modo más inteligente es mantener con claridad 3 arrays para decidir entre qué números debe elegirse al azar. tú ahora estás en la casilla x,y, pués rellenas 3 arrays (que serían Fila(), Columna(), Bloque()... (ver más abajo el pseudocódigo para la función de ejemplo para obtener el array de Fila: GetValoresEnFila)) TmpFila = GetValoresEnFila(Entero Y) //solo pongo el psedocodigo para esta función, comprendiendo ésta es fácil deducir como han de ser las otras dos funciones...
TmpColumna = GetValoresEnColumna(Entero X)
TmpBloque = GetValoresEnBloque(Entero X, Entero Y) Esos 3 arrays con los valores actuales en la fila, columna y bloque (si un valor no está tendrán valor 0), se deben luego unificar en uno solo array resumen donde aparezcan cada valor existente una sola vez Ver más abajo la función (aquí la llamada con los 3 arrays como parámetros y la devolución de uno resumido: Tmp = UnificarCubiculos(TmpFila, TmpColumna, TmpBloque) Entonces llamas a una función preguntan do para ser rellenado con los valores ausentes, pasándole como entrada ese array unificado: Presentes, es el array resultado de 'unificarCubiculos'... Array Byte = Funcion TomarAusentes(Array Byte Presentes(), Out Entero NumAusentes)
Array tipo Byte V(0 a c_Ocho)
Entero k
NumAusentes=0
Bucle para k desde 1 a c_Nueve
Si (Presentes(k) = 0) luego // El valor está vacío como casilla, en fila, columna y bloque... se añade
V(NumAusentes) = k
NumAusentes +=1
Fin si
Fin Bucle
Devolver V
Fin Funcion Array Byte Sudoku(0 a 80) //es el array que mantiene internamente los valores. Devuelve un array con los valores de la fila recibida. Array Byte = Funcion GetValoresEnFila(Entero n)
Array tipo Byte V(0 a c_Ocho)
Entero Index, k
Index= (n * c_Nueve)
n = 0 // Reutilizamos n (se recibe por valor)
Bucle para k desde Index a (Index + c_Ocho)
V(n) = Sudoku(k) //Aray que contiene los valores
n +=1
Fin Bucle
Devolver V
Fin Funcion l array 'resumen', simplemente toma todos los valores distintos presentes, sin repetición... Unificando así los 3 arrays en uno de resumen... Array Byte = Funcion UnificarCubiculos(Array Byte Fila(), Array Byte Columna(), Array Byte Bloque())
Array tipo Byte V(0 a c_Nueve)
// contar el número de presencias de cada valor...
Bucle para k desde 0 a c_Ocho
Si (Fila(k) > 0) luego // Si no está vacía la casilla...
V(Fila(k)) += 1
fin si
Si Columna(k) > 0 luego // Si no está vacía la casilla...
V(Columna(k)) += 1
fin si
Si (Bloque(k) > 0) luego // Si no está vacía la casilla...
V(Bloque(k)) += 1
fin si
Fin Bucle
// Ahora se reagrupan arriba en el array (las ausencias (valor 0), quedan 'huecas' en la parte alta del array.
V(0) = 0 //Realmente no es necesario, ya que no llevó la cuenta de 'ceros'
Bucle para k desde 1 a c_Nueve
Si (V(k) > 0) luego
V(k) = k
Fin si
Fin Bucle
Devolver V
Fin Funcion Así el orden de estas funciones para tomar UN VALOR al azar sería, la siguiente función: X,Y representan la casilla donde deseamos poner el valor no se verifica que x e y estén en el rango correcto, se supone que son correctos, que fueron verificados, antes de llamar aqui Byte = funcion SeleccionarValorAzar(Entero X, Entero Y)
Array tipo Byte TmpFila()
Array tipo Byte TmpColumna()
Array tipo Byte TmpBloque()
Array tipo Byte Tmp()
Array tipo Byte Azar()
// Primero consultamos que tenemos, en la 'vecindad' de esa casilla.
// Puede optimizarse si se mantienen en memoria 9 arrays de filas, 9 de columnas y los 9 de bloques y se actualizan convenientemente. Será mas veloz, pero más complejo y másgasto de memoria... Hacerlo, queda a tu esfuerzo si te interesa.
// Recuérdese que las casillas 'vacías', tienen valor 0
TmpFila = GetValoresEnFila(Entero Y)
TmpColumna = GetValoresEnColumna(Entero X)
TmpBloque = GetValoresEnBloque(Entero X, Entero Y)
// Ya tenemos, los 3 cubículos con los que comparar el valor al azar... pero...
// ya dije que no vamos a comparar, en su defecto, integraremos los 3 en 1 ( a modo de resumen, que simplica
// por completo la verificación a un simple bucle).
Tmp = UnificarCubiculos(TmpFila, TmpColumna, TmpBloque)
// Ahora rellenamos otro array con los valores ausentes en el array resumen unificado.
Byte n
Azar = TomarAusentes(Tmp, n)
// OJO: si el array queda vacío implica que hay que desecha los valores actuales de la fila y volver a reconstruirla entera
Si (n=0) luego devolver 0
// Finalmente se toma un valor al azar entre 0 y n-1, que representa el indice del array Azar. Este array tiene exclusivamente los números que no aparecen ni en la fila, ni en columna, ni en bloque.
k = Aleatorio( entre 0 y n-1)
Devolver Azar(k)
Fin Funcion
La función que rellena el sudoku entero sería algo como esto: Funcion RellenarSudokuAlAzar()
Entero Fila, columna
Byte Valor
Fila=0 // la primera fila, la podrías obtener al azar completamente en ese caso marcar aquí 1, para comenzar en la fila 1, la 0 no va a requerir todas las comprobaciones que pueden requerir las siguientes.
Hacer '// esto es fila, puede ser un bucle que va de 0 a 8
Columna = 0
Hacer
Valor = SeleccionarValorAzar(Columna, Fila) //la función que obtiene un valor de cada vez.
Si (Valor>0) luego
Sudoku((Fila * c_Nueve) + Columna) = valor //Sudoku() es el array que mantiene internamente los valores.
// Si el array es bidimensional se pondría así...
//Sudoku(Columna, Fila) = valor
Columna +=1
Si no
// Borra los valores de la fila actual
Bucle para k desde 0 a columna
Sudoku((Fila * c_Nueve) + k) = 0
Fin bucle
Columna = 0
Fin si
Repetir Mientras (Columna <9)
Fila +=1
Repetir Mientra (Fila<9)
Fin Funcion c_Ocho, c_Nueve son constantes con esos valores que en este juego se van a usar muy a menudo. Igualmente constantes para 2 y 3 podrían ser usadas, para las consultas en los bloques. -------------------------------------------------------------------------------------------------------------- p.d.: Actualizo la funcion para rellenar el Sudoku, para salir del bache ante bloqueos... Fijarse en los cambios añadidos para Intentos, cuando el valor devuelto es 0. Si se va dibujando desde esta función cuando sale un valor y se borra cuando se anulan los valores, se ve sobre la marcha como opera , se detiene y rada un poco en algunas filas, y a veces borra también la previa y luego sale del bache y lo completa siempre... La función que rellena el sudoku entero sería algo como esto: Funcion RellenarSudokuAlAzar()
Entero Fila, columna
Byte Valor, Intentos
Fila=0 // la primera fila, la podrías obtener al azar completamente en ese caso marcar aquí 1, para comenzar en la fila 1, la 0 no va a requerir todas las comprobaciones que pueden requerir las siguientes.
Hacer '// esto es fila, puede ser un bucle que va de 0 a 8
Intentos = 0
Columna = 0
Hacer
Valor = SeleccionarValorAzar(Columna, Fila) //la función que obtiene un valor de cada vez.
Si (Valor>0) luego
Sudoku((Fila * c_Nueve) + Columna) = valor //Sudoku() es el array que mantiene internamente los valores.
Columna +=1
Si no
// Borra los valores de la fila actual
Bucle para k desde 0 a columna
Sudoku((Fila * c_Nueve) + k) = 0
Fin bucle
// Tras 10 intentos en la misma fila, borramos también la fila previa
Intentos += 1
Si (Intentos = 10) luego
Si (Fila > 0) luego // no podemos retroceder a filas más atrás que la primera.
Fila = (Fila - 1) // Borramos también la fila anterior (y si sucede otra vez, la previa, etc...)
Bucle para k desde 0 To c_Ocho
Sudoku((Fila * c_Nueve) + k) = 0
Fin Bucle
Fin si
Intentos = 0
Fin si
Columna = 0
Fin si
Repetir Mientras (Columna <9)
Fila +=1
Repetir Mientra (Fila<9)
Fin Funcion
// Al término de esta función se podría dibujar los valores en el tablero para verificar visualmente el resultado.
|
|
|
|
« Última modificación: 31 Julio 2017, 06:10 am por NEBIRE »
|
En línea
|
|
|
|
Editame
Desconectado
Mensajes: 11
Todo radica en la Humildad !
|
Hola amigos como estan ?, espero que bien. Bueno primero que todo quiero agradecerles el tiempo que dedicaron ambos compañeros para revisar el codigo y ayudarme, de verdad les agradezco mucho. Pero retomando el tema NEBIRE la verdad no entiendo mucho tu logica, intento comprender lo que me dices, pero no lo logro primero me dices que cree numeros del 1 al 8 y calcule la ultima posicion por fila, columna o caja buscando la que falte, eso por un lado, luego hablas de crear 3 arrays distintos para para hallar valores entre los cuales debo obetener los que faltan (Es lo que entiendo) osea estando en tal posicion que cree una fila una columna y un bloque ??? .... y me perdi  no se de verdad hay muchas cosas que no entiendo de tu codigo, podrias por favor intentar enseñarme tu logica con palabras o pasos mas simples no se como decirte, pero como dice mi profesor de programacion "formas de programar hay muchas", tal vez yo no lo veo como tu no lo entiendo por que esta es tu forma pero intenta explicarme tu logica (asi sea sin codigo solo la logica) que si entiendo la logica ya vere de que manera lo programo.. No se si entiendas el punto no quiero tener que hacer algo como tu jajaj si no poder aprender de ti... te agradezco muchisimo a ti a todos los que puedan participar cuidense y espero sus respuestas. |
|
|
|
« Última modificación: 31 Julio 2017, 07:45 am por Editame »
|
En línea
|
Edilberto Tapias Mercado
Estudiante Ing. Telematica
|
|
|
|
Serapis
|
Ok, te lo explicaré más sencillo, con palabras ..y dibujitos, pero entonces será a la tarde, ahora(después de comer, tengo el tiempo muy justo) no tengo tiempo para hacer los dibujitos y escribir las explicaciones.
|
|
|
|
|
En línea
|
|
|
|
|
Serapis
|
Una imagen para hacernos una idea de qué hablamos...  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: 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: 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 Esta parte no es estrictamente necesaria, pero es buena práctica a la hora de optimizar, uno puede hacer luego algo de 'código espagueti' siempre y cuando lo entienda... el array de salida, nos sería válido tanto antes como después de este último bcle, solo sería cuestión de en la siguiente función interpretarlo correctamente, para evitar equívocos, hacemos que el valor sea lo importante... por so el bucle final. 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). |
|
|
|
« Última modificación: 19 Enero 2020, 16:45 pm por NEBIRE »
|
En línea
|
|
|
|
|
Serapis
|
Continuamos, ahora con la siguiente imagen... como puede verse, el contenido es casi el mismo que la vez anterior, solo ha cambiado el contenido de la última fila... (y con ello del bloque, pero se mantiene el de la columna.
Actualizo los datos que debieran devolver los 3 arrays conforme a la nueva imagen:
- función GetvaloresEnFila (x), serán: 3,7,8,5,4,0,0,0,0 en el array tmpFila
- función GetValoresEncolumna(y), serán: 9,4,5,3,7,0,0,0,0 en el array tmpColumna
- función GetValoresEnBloque(x,y), serán: 9,8,3, 6,2,7, 5,4,0 en el array tmpBloque
Ahora al unificar los 3 arrays en 1, obtenemos (en el primer paso):
0 1 3 3 3 1 3 2 2
tmp(1) = 0
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) = 3
tmp(6) = 1
tmp(7) = 3
tmp(8) = 2
tmp(9) = 2
Esto es, la cuenta de cuantas veces aparece cada valor. el valor referenciado por el índice. Así el 9 aparece 2 veces, una vez en la columna y otra en el bloque.
Ahora terminamos la unificación, como ya dije para tener como valor no la cuenta si no contancia de la 'presencia'.
Lo previo se puede considerar una tabla de apariciones, donde se cuenta cuantas veces aparece cada valor (en este caso de los 3 arrays).
La siguiente es una tabal de presencia, donde se constar que valores aparecen, sin importar el número de veces, y como dije el código encargado de ello es el que ya puse:
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 Y el resultado del array será: tmp(1) = 0 tmp(2) = 2 tmp(3) = 3 tmp(4) = 4 //aparece 3 veces, una en la fila, otra en la columna y otra en el bloque. tmp(5) = 5 tmp(6) = 6 tmp(7) = 7 tmp(8) = 8 tmp(9) = 9 Nótese que en esta función es la única que construye un array de 9 valores (10 elementos), porque el índice 9, ha de contener cuantas veces aparece el 9. Finalmente llegamos a la siguiente función que nos entregará un array con todos los ítems que no aparecen, para ello recibe como parámetro 'éste array'... Función: TomarAusentes Este array hace algo opuesto a la última parte de la fase anterior. de hecho se podría haber remplazado esa fase con lo que hace esta función, si se quiere optimizar, sin embargo resultaría un código más oscuro de cara a entenderlo... Array Byte = Funcion TomarAusentes(Array Byte Presentes(), Out Entero NumAusentes)
Array tipo Byte V(0 a c_Ocho)
Entero k
NumAusentes=0
Bucle para k desde 1 a c_Nueve
Si (Presentes(k) = 0) luego // El valor está vacío como casilla, en fila, columna y bloque... se añade
V(NumAusentes) = k
NumAusentes +=1
Fin si
Fin Bucle
Devolver V
Fin Funcion
Nótese que como el array de entrada tiene 10 elementos, el bucle termina en el índice 9, y comienza en el 1, porque no nos interesan los 0 (los valores del sudoku van del 1 al 9). Cada vez que se encuentra que un valor no aparece se añade al array y se aumenta el índice. Casualmente solo hay un valor que no aparece en el array el '1', luego cuando se elija al azar de este array devolverá el índice 0 con contenido 1... Que será el valor a consignar en la casilla x,y. En la siguiente casilla nos encontramos de nuevo que solo qeueda un valor elegible, el 2... Pero en la siguiente casilla (penúltima de la fila), da dos opciones, veamos el resultado que arroja el array tras la llamada a 'UnificarCubiculos' (el indice del 0, lo pongo con guión, señalando con ello que no importa): array tmp: -,1,2,3,4,5,0,7,8,0 Como se ve ya mismo hay ausentes el 6 y el 9, que es lo que nos debe arrojar la función 'TomarAusentes': tmp(0) = 6 tmp(1) = 9 Lo siguiente en el código es elegir al azar entre el 0 y el 1, para devolver justo el valor del elemento en el índice 'azaroso'. en mi caso mi equipo ha seleccionado el '0' que crresponde al valor 6, luego si no se da situación de bloqueo en la siguiente columna, allí quedará por consignar el 9... La columna admitiría más valores que ese, pero la fila y el bloque lo impiden, solo les falta el 9 a ambos. Vamos a mostrar algo más interesante de modo que haya más elementos ausentes tras la unificación de los arrays... seguramente nos suceda al comenzar la siguiente fila, pués también se comienza el bloque y solo existen 'presentes' los valores que tiene la columna '0' al caso pongo un nuevo dibujo actualizado.  El resultado de los 3 arrays... para la ca: tmpFila: 0,0,0,0,0,0,0,0,0 porque está vacía. tmpColumna: 7,8,9,4,5,3,0,0,0 tmpBloque: 0,0,0,0,0,0,0,0,0 porque está vacío. Y pasamos al resultado de reunificar los tres arrays, y ya en la devolución, no en pasos intermedios, también por brevedad, los pondré en fila: tmp: -,0,0,3,4,5,0,7,8,9 Y ahora el array de ausentes La misma función devuelve por referencias cuantos elementos son válidos en el array al caso 3 (el array sigue teneiendo 9 elementos): tmp: 1,2,6 Esto nos indica que al azar debemos elegir entre 0 y 2, que son los índices válidos.. sea cual sea el elegido (al caso me sale el índice 1), se entrwega el valor cuyo índice ha salido: k = Aleatorio( entre 0 y n-1) //n es aquí el valor devuelto por referencia de la cantidad de 'valores válidos' en el array.
Devolver Azar(k) En resumen es más inteligente, porque no elegimos a al azar un valor a ciegas entre 0 y 9, y luego comprobamos que no exista en fila, columna ni bloque y si está vuelta a elegir y vuelta a comprobar y así hasta que no esté. Es más inteligente orque esa comprobación se hace una sola vez al inicio y así cuando elegimos ala azar elegimos solo entre los valores que no constan ya. Todavía se puede ir más lejos y crear una función (con parte de la que existe en 'SeleccionarValorAzar'), para que cuando el usuario pretenda meter un valor verifique si ese valor es válido para la casilla o no... Y para optimizarlo, dicha función podría partirse en dos, una hasta obtener el array de ausentes y otra para de entre esos ausentes elegir el valor al azar y luego cuando el usuario quiera poner un valor, llamamos igualmente a esa primera función para entregar el array de ausentes y creamos una segunda para con ese array ver si contiene el valor que el usuario pretende introducir, devolviendo un buleano de 'existe'... Desmontando la función como he dicho (esta ahora llama a dos, cuyo contenido se repartió entre ellas): Cuando se va a rellenar el Sudoku: Byte = funcion SeleccionarValorAzar(Entero X, Entero Y)
Array tipo Byte Tmp()
Byte n
Tmp = GetArrayAusentes(X, Y)
Si (n>0) luego
n = DevolverValorAzar(Tmp, n)
Fin si
Devolver n
Fin Funcion Array byte = GetArrayAusentes(Entero X, Entero Y, Out Entero NumAusentes)
Array tipo Byte TmpFila()
Array tipo Byte TmpColumna()
Array tipo Byte TmpBloque()
Array tipo Byte Tmp()
Array tipo Byte Azar()
// Primero consultamos que tenemos, en la 'vecindad' de esa casilla.
// Puede optimizarse si se mantienen en memoria 9 arrays de filas, 9 de columnas y los 9 de bloques y se actualizan convenientemente. Será mas veloz, pero más complejo y másgasto de memoria... Hacerlo, queda a tu esfuerzo si te interesa.
// Recuérdese que las casillas 'vacías', tienen valor 0
TmpFila = GetValoresEnFila(Entero Y)
TmpColumna = GetValoresEnColumna(Entero X)
TmpBloque = GetValoresEnBloque(Entero X, Entero Y)
// Ya tenemos, los 3 cubículos con los que comparar el valor al azar... pero...
// ya dije que no vamos a comparar, en su defecto, integraremos los 3 en 1 ( a modo de resumen, que simplica
// por completo la verificación a un simple bucle).
Tmp = UnificarCubiculos(TmpFila, TmpColumna, TmpBloque)
// Ahora rellenamos otro array con los valores ausentes en el array resumen unificado.
Devolver = TomarAusentes(Tmp, NumAusentes)
Fin Funcion Se toma un valor al azar entre 0 y Cantidad-1, que representa el indice del array Azar. Este array tiene exclusivamente los números que no aparecen ni en la fila, ni en columna, ni en bloque. Byte = DevolverValorAzar(Array byte Ausentes(), Byte Cantidad)
byte k
k = Aleatorio( entre 0 y Cantidad-1)
Devolver Ausentes(k)
Fin Funcion Cuando se va a verificar si el valor que introduce el usuario es correcto: Será válido si está ausente en Fila, Columna y bloque que refiere la casilla... Buleano = funcion ValorEsAdmisible(Entero X, Entero Y, Byte ValorUser)
Array tipo Byte Tmp()
Byte n
Tmp = GetArrayAusentes(X, Y)
Si (n>0) luego
Devolver ExisteValorEnAusentes(Tmp, n, ValorUser)
Si no
Devolver FALSE
Fin si
Devolver n
Fin Funcion Buleano = ExisteValorEnAusentes(Array byte Ausentes(), Byte Cantidad, byte ValorUser)
byte k
Bucle para k desde 0 a Cantidad-1
Si (Ausentes(k) = ValorUser) luego
Devolver TRUE
Fin si
Fin Bucle
Fin Funcion Me falta explicarte solamente un poco más lo de los bloqueos, asíq eu seré breve y si no lo entiendes me lo dices... El bloqueo se produce cuando tanto en la fila como en la columna como en el bloque ya hay puesto (al menos entre todos ellos (valores unificados)), todos los 9 valores, y en consecuencia no existe posibilidad de elgir uno que no esté... en tu caso (me refiero a tu código) elijas el que elijas, ya está, por tanto da igual que elijas 1000 veces como está la comprobación forzará a elegir otra vez... En mi código, en el mensaje de ayer, al final puse un cambio para salir del bloqueo, y consiste en que cuando se alcance un bloqueo, se elimine por completo esa fila y se recomience d enuevo la fila, y si tras 10 intentos sigue sin poderse completar la fila, borra también la anterior (yaq que es posible que e la actual no haya solución, porque con la anterior ya cais no deja opciones). en teoría es posible que si tras borra rla actual y la prevuia aparecieren al recrear la previa 10 bloqueos seguidos, borrara también la anterior... en fin, en cualquier caso cuantos menos filas haya más difícil que se dé una situación de bloqueo, por eso suele basta con borrar la fila actual... Pongo el código que se ocupa de esa parte (que corresponde a la función 'RellenarSudokuAlAzar'), para refrescar la memoria: .... //código previo
Valor = SeleccionarValorAzar(Columna, Fila) //la función que obtiene un valor de cada vez.
Si (Valor>0) luego
Sudoku((Fila * c_Nueve) + Columna) = valor //Sudoku() es el array que mantiene internamente los valores.
Columna +=1
Si no
// Borra los valores de la fila actual
Bucle para k desde 0 a columna
Sudoku((Fila * c_Nueve) + k) = 0
Fin bucle
// Tras 10 intentos en la misma fila, borramos también la fila previa
Intentos += 1
Si (Intentos = 10) luego
Si (Fila > 0) luego // no podemos retroceder a filas más atrás que la primera.
Fila = (Fila - 1) // Borramos también la fila anterior (y si sucede otra vez, la previa, etc...)
Bucle para k desde 0 To c_Ocho
Sudoku((Fila * c_Nueve) + k) = 0
Fin Bucle
Fin si
Intentos = 0
Fin si
Columna = 0
Fin si
.... // código después...
------------- p.d.: Puedes modificar el tema del hilo para que refleje lo que realmente es, y así si alguien utiliza el buscador pueda encontrarlo?. Nadie pone a buscar "necesito ayuda" ni "ayuda con mi código", ....pero alguien sí buscaría algo como: "sudoku"... Así te reclamo que cambies el título del tema a algo más acorde como: "Código para Sudoku"
Editado para reponer las imágenes... |
|
|
|
« Última modificación: 19 Enero 2020, 16:38 pm por NEBIRE »
|
En línea
|
|
|
|
Editame
Desconectado
Mensajes: 11
Todo radica en la Humildad !
|
Hola NEBIRE que tal,
Ya esta mucho mejor esto ya puedo decir que comprendo muchisimo mas tu logica solo me queda ponerlo en practica y mirar hasta donde llego, cualquier inquietud o ayuda que necesite te la estare comunicando muchisimas gracias por tu colaboracion hasta el momento, espero poder seguir contando contigo jajajaj
Bendiciones Saludos a todos
|
|
|
|
|
En línea
|
Edilberto Tapias Mercado
Estudiante Ing. Telematica
|
|
|
Editame
Desconectado
Mensajes: 11
Todo radica en la Humildad !
|
Nebire amigo tengo problemas al unificar los tres arrays en uno no se como pasarlos como parametros a la funcion Unificado. solo llevo las tres funciones que obtienen los arrays de fila, columna y caja me podrias ayudar. public static int [] obtenerFila (int matriz[][], int filas, int columnas){
int renglon[] = new int[9];
for (int i = 0; i < 9; i++) {
renglon[i]=matriz[i][columnas];
}
return renglon;
}
public static int [] obtenerColumna (int matriz[][], int filas, int columnas){
int colum[] = new int[9];
for (int i = 0; i < 9; i++) {
colum[i]=matriz[filas][i];
}
return colum;
}
public static int [] obtenerCaja (int matriz[][], int filas, int columnas){
int minfila, maxfila;
int mincolum, maxcolum;
if (filas >= 0 && filas < 3) {
minfila = 0;
maxfila = 2;
}else if (filas >= 3 && filas < 6) {
minfila = 3;
maxfila = 5;
}else {
minfila = 6;
maxfila = 8;
}
if (columnas >= 0 && columnas < 3) {
mincolum = 0;
maxcolum = 2;
}else if (columnas >=3 && columnas <6) {
mincolum = 3;
maxcolum = 5;
}else{
mincolum = 6;
maxcolum = 8;
}
int k=0;
int caja[] = new int[9];
for (int i = minfila; i < maxfila; i++) {
for (int j = mincolum; j < maxcolum; j++) {
caja[k]=matriz[i][j];
k++;
}
}
return caja;
} |
|
|
|
|
En línea
|
Edilberto Tapias Mercado
Estudiante Ing. Telematica
|
|
|
|
Serapis
|
Nebire amigo tengo problemas al unificar los tres arrays en uno no se como pasarlos como parametros a la funcion Unificado.
mmmm... y cómo has pasado el array que contiene todo el sudoku???. Yo veo en tu código una función así: public static int [] obtenerFila (int matriz[][], int filas, int columnas){ ... Y bueno, en esta función... public static int [] obtenerCaja (int matriz[][], int filas, int columnas){Esta parte se puede simplificar y mejorar mucho:
if (filas >= 0 && filas < 3) {
minfila = 0;
maxfila = 2;
}else if (filas >= 3 && filas < 6) {
minfila = 3;
maxfila = 5;
}else {
minfila = 6;
maxfila = 8;
}
if (columnas >= 0 && columnas < 3) {
mincolum = 0;
maxcolum = 2;
}else if (columnas >=3 && columnas <6) {
mincolum = 3;
maxcolum = 5;
}else{
mincolum = 6;
maxcolum = 8;
} Mira, yo lo tengo así de simple: bX = ((X \ c_Tres) * c_Tres)
bY = ((Y \ c_Tres) * c_Tres) X,Y son las cordenadas de la casilla sobre la que estamos operando. bX y bY, serían el X e Y de bloques, que en efecto serán 0,3 ó 6 Y en efecto, si haces la cuenta, para todas ellas del 0 al 8: bX = (( 0\3)*3) = 0 bX = (( 1\3)*3) = 0 bX = (( 2\3)*3) = 0 bX = (( 3\3)*3) = 3 bX = (( 4\3)*3) = 3 bX = (( 5\3)*3) = 3 bX = (( 6\3)*3) = 6 bX = (( 7\3)*3) = 6 bX = (( 8\3)*3) = 6 Date cuenta que es una división entera... Por último, no pases parámetros a una función si no los necesita para nada. Por ejemplo si la función 'obtenerFila ' no usa 'filas', elimina ese parámetro. Si la función 'obtenerColumna' no utiliza para nada el parámetro 'columnas', retíralo de la función. También sería más acorde llamar a esos parámetros 'X' e 'Y', 'Filas' y 'Columnas' dan sentido como nombre a una cantidad de filas y columnas, para una posición única al menos que sea singular.
|
|
|
|
|
En línea
|
|
|
|
|
 |
