Bueno, veréis, resulta que para el lunes tengo que entregar un trabajo en la uni y tengo problemas con el código (que encima es lo menos importante del trabajo). El caso es que el proyecto trata sobre la probabilidad de que un sudoku de 9x9 tenga solución.
Para implementar el código utilicé un solucionador de sudokus en java que encontré en internet. Este código parece que funciona bien y resuelve los sudokus que tú le metas. Va acompañado de un applet donde le introduces los valores iniciales con los que quieres crear el sudoku y donde luego te muestra el sudoku resuelto.
Ahora bien, mi código lo que hace es crear una serie de números aleatorios. Estos números son insertados en celdas aleatorias de un sudoku y luego utilizo el código que descargué para que me solucione el sudoku creado aleatoriamente.
Finalmente, ejecuto este código tantas veces como quiera, es decir, resuelvo 1000 sudokus, por ejemplo, y le pido que me muestre con qué probabilidad se han resuelto los sudokus y el tiempo que ha tardado en hacerlo.
Os pongo aquí el código:
CODE
package ISAL;
/**
* Esta clase se encarga de crear y resolver un sudoku,
* guardarlo en un array y sacar el número de sudokus
* resueltos y no resueltos.
*/
import java.util.Random;
public class ProbSudoku {
// Array que guardará el tablero del sudoku.
private int[][] tablero = new int[9][9];
private int aFila;
private int aCol;
private long elapsed;
private Random rnd = new Random();
private int[] valoresAl;
private int[] comp = new int[41];
private static int count;
/*********************************************Inicio código de resolución de sudokus******************************************************/
/**
* Método para limpiar el tablero del sudoku y dejarlo sin números dentro.
*/
public void limpiar() {
for (int f = 0; f < 9; f++){
for (int c = 0; c < 9; c++){
tablero[f][c] = 0;
}
}
}
/**
* Método para imprimir por pantalla el tablero del sudoku en formato texto.
*/
public void crearTabla() {
for (int f = 0; f < 9; f++) {
for (int c = 0; c < 9; c += 3) {
System.out.print(tablero[f][c]);
System.out.print(tablero[f][c + 1]);
System.out.print(tablero[f][c + 2]);
System.out.print("\t");
}
System.out.print("\n");
if ((f + 1) % 3 == 0)
System.out.print("\n");
}
}
/**
* Insertamos el valor indicado en los parámetros en la posición indicada por los mismo.
*
* @param fila fila en la que insertaremos el valor.
* @param col columna en la que insertaremos el valor.
* @param valor valor que queremos insertar en la celda determinada por la columna y fila dadas.
*/
public void insertarValor(int fila, int col, int valor) {
tablero[fila][col] = valor;
}
/**
* Método que comprueba si el número (valor) insertado se encuentra en alguna fila, columna o caja.
*/
public boolean Valido() {
// Comprobamos si está en su fila.
for (int f = 0; f < 9; f++) {
boolean[] Insertado = new boolean[10]; // Vector que contiene a las celdas de una fila. Vale "false" si el número no está en esa celda y "true" si sí que lo está.
for (int aux = 0; aux < 10; aux++)
Insertado[aux] = false;
for (int c = 0; c < 9; c ++) {
if ((tablero[f][c]) == 0) continue; // Si la celda tiene valor "0", está vacía y continuamos.
else {
if (Insertado[tablero[f][c]]){
// La celda tiene el número que íbamos a poner en otra de la misma fila, por tanto, no se puede poner.
return false;
}
else Insertado[tablero[f][c]] = true; // Marca el número como usado.
}
}
}
// Comprobamos si está en su columna.
for (int c = 0; c < 9; c++) {
boolean[] Insertado = new boolean[10]; // Vector que contiene a las celdas de una columna. Vale "false" si el número no está en esa celda y "true" si sí que lo está.
for (int aux = 0; aux < 10; aux++)
Insertado[aux] = false;
for (int f = 0; f < 9; f ++) {
if ((tablero[f][c]) == 0) continue; // Si la celda tiene valor "0", está vacía y continuamos.
else {
if (Insertado[tablero[f][c]]) {
// La celda tiene el número que íbamos a poner en otra de la misma columna, por tanto, no se puede poner.
return false;
}
else Insertado[tablero[f][c]] = true; // Marca el número como usado.
}
}
}
// Comprobamos si está en su caja.
for (int bf = 0; bf < 3; bf++) {
for (int bc = 0; bc < 3; bc++) { // Para nueve cajas.
boolean[] Insertado = new boolean[10]; // Vector que contiene a las celdas de una caja. Vale "false" si el número no está en esa celda y "true" si sí que lo está.
for (int aux = 0; aux < 10; aux++)
Insertado[aux] = false;
for (int f = 0; f < 3; f++) { // Para cada celda en una caja.
for (int c = 0; c < 3; c++) {
if ((tablero[bf*3 + f][bc*3 + c]) == 0) continue; // Si la celda tiene valor "0", está vacía y continuamos.
if (Insertado[(tablero[bf*3 + f][bc*3 + c])]) {
return false; // Si el número está usado, el Sudoku no es válido.
} else {
Insertado[(tablero[bf*3 + f][bc*3 + c])] = true; // Si el número no está usado, se marca como usado.
}
}
}
}
}
return true; //El sudoku es válido.
}
public boolean resolver(){
int flibre, clibre; // Siguiente fila o culumna a rellenar.
int []CeldaLibre = new int[2];
CeldaLibre = nextCeldaLibre();
if (CeldaLibre[0] < 0 && CeldaLibre[1] < 0){
return this.Valido(); // No hay más celdas a rellenar y el Sudoku es válido. ¡Sudoku resuelto!
}
else {
flibre=CeldaLibre[0];
clibre=CeldaLibre[1];
return resolver(flibre,clibre);
}
}
private boolean resolver(int fila, int columna){
int []nextLibre;
boolean resuelto = false;
for (int numero=1; numero< 10; numero++){
this.insertarValor(fila,columna,numero);
if (this.Valido()){
nextLibre = nextCeldaLibre();
if (nextLibre[0] < 0) return true;
else{
count++;
resuelto = resolver(nextLibre[0],nextLibre[1]);
if (resuelto) return true;
}
}
this.insertarValor(fila,columna,0);
}
return false;
}
private int[] nextCeldaLibre(){
// La posición [0] del vector devuelve la fila; la posición [1] del vector devuelve la columna.
int[] nextLibre = new int[2];
nextLibre[0]=-1;
nextLibre[1]=-1;
for (int fila =0; fila < 9; fila++){
for(int col=0; col < 9; col++){
if (tablero[fila][col] == 0){
nextLibre[0]= fila;
nextLibre[1]= col;
}
}
}
return nextLibre;
}
public int[][] sacarTablero(){
return tablero;
}
/************************************************Fin código de resolución de sudokus******************************************************/
/****************************************************Inicio códigos aleatorios************************************************************/
/**
* Crea n números aleatorios.
*
* @param n cantidad de números aleatorios a crear.
* @return un vector con los n números aleatorios.
*/
public int[] aleatorio (int n) {
int[] numeros = new int[n];
for (int i = 0; i < n; i++) {
numeros[i] = rnd.nextInt(9)+1;
}return numeros;
}
/**
* Crea 1 número aleatorio del 0 al 8.
*
* @return el núemro aleatorio.
*/
public int lineasAleatorias () {
int lineas = rnd.nextInt(9);
return lineas;
}
/**
* Crea un número aleatorio.
*
* @return un número aleatorio entre 5 y 15.
*/
public int aleatorio(){
int aleatorio = rnd.nextInt(11)+5;
return aleatorio;
}
/**
* Inserta un número de valores aleatorios en celdas aleatorias del sudoku.
*/
public void insertarAleatorio(){
int n = 5; // Número de valores iniciales a insertar en el sudoku
valoresAl = this.aleatorio(n);
while(this.comprobarValores(valoresAl)==false) valoresAl=this.aleatorio(n);
for (int i = 0; i < n; i++){
int valor=valoresAl[i];
this.posicionesAleatorias();
this.insertarValor(aFila, aCol, valor);
if(this.Valido()==false){
insertarValor(aFila, aCol, 0);
i=i-1;
}
}
}
private void posicionesAleatorias(){
this.aFila = lineasAleatorias();
this.aCol = lineasAleatorias();
}
/**
* Comprueba que no se intente insertar un valor más de 9 veces.
*
* @param valores vector con los valores a insertar.
* @return Devuelve false si se intentan insertar un valor más de 9 veces.
*/
public boolean comprobarValores(int[] valores){
for (int i=0;i<valores.length-1;i++){
for (int j=i+1;j<valores.length;j++){
if (valores[i]==valores[j]){
comp[valores[i]]=comp[valores[i]]+1;
if(comp[valores[i]]+1==10) return false;
}
}
}
return true;
}
/**
* Resuelve n sudokus y mira a ver si son válidos o no.
*
* @param n número de susokus a resolver.
* @return el número de sudokus resueltos.
*/
public int sudokusResueltos(int n){
int r=0;
this.limpiar();
for (int i=0; i<n; i++){
count=0;
this.insertarAleatorio();
if (this.resolver()){
r=r+1;
}
this.limpiar();
System.out.println(count);
}
return r;
}
/**
* Calcula la probabilidad de resolver un sudoku.
*
* @param n número de sudokus a resolver.
* @return vector de dos celdas con la probabilidad de que el sudoku se haya resuelto o que no respectivamente.
*/
public float[] probabilidadSudoku(int n){
float[] prob = new float[2];
long ini = System.currentTimeMillis();
int r = this.sudokusResueltos(n);
long fin = System.currentTimeMillis();
elapsed = (fin - ini);
float resueltos = (r/n);
float noresueltos = 1-resueltos;
prob[0] = resueltos;
prob[1] = noresueltos;
return prob;
}
/*****************************************************Fin de códigos aleatorios***********************************************************/
//método main
public static void main(String[]args){
ProbSudoku prob = new ProbSudoku();
float[] res = prob.probabilidadSudoku(100);
System.out.println(res[0]);
System.out.println(res[1]);
System.out.println("Tiempo empleado:");
System.out.println(prob.elapsed+" milisegundos");
}
}
El caso es que este código funciona a veces sí a veces no. Si por ejemplo le pongo a resolver 3000 sudokus, pues muchas veces (la mayoría por no decir todas) se queda parado en un número cualquiera de sudokus y no pasa de ahí. Este número no es siempre el mismo.
El caso es que no le veo ningún error al código, ni al que bajé (al que llamo "código de resolución de sudokus") ni al que he creado ("códigos aleatorios").
Para evitar problemas con la memoria en "códigos aleatorios" he sacado todas las creaciones de objetos de los bucles y los he puesto en la zona de declaración de variables.
También he suprimido todos los métodos recursivos para que no se me llene la pila y me salte el error StackOverflowError. El problema es que no puedo quitar el método recursivo "resolver(int fila, int columna). No me salta el error que digo, pero si cuento el número de llamadas que se hace a sí mismo (con la variable "count") me sale lo siguiente, por ejemplo:
CODE
319
308
154
431
1368
161
401
579
379
1683
350
173
802
394
169
411
183
205
151
144
215
156
294
135
337
218
194
617
301
273
140
237
114
110
488
439
464
286
161
355
353
203
178
811
110
320
287
403
366
242
199
242
213
140
186
385
195
289
272
576
121
328
390
113
162
413
732
336
164
172
621
379
220
303
198
145
870
121
481
348
121
137
129
123
157
377
136
358
300
184
306
189
493
196
546
338
576
486
1075424
11685
1.0
0.0
Tiempo empleado:
35406 milisegundos
Aquí le he pedido al programa que me recuelva 100 sudokus. Las 4 últimas líneas son las probabilidades que me han dado de resolución (100% de resueltos, algo que también me mosquea, aunque poniendo sólo 5 valores iniciales no deja de ser normal...).
Las otras 100 líneas son las llamadas que se ha hecho así mismo el método en cada uno de los sudokus.
Ahora, si ejecuto este código:
CODE
public class OverflowErrorCount {
public static int count = 0;
public static void main(String args[]) {
System.out.println(++count);
main(null);
}
}
La última cifra debería mostrarme la cantidad de llamadas que puede hacerse así mismo un método. Esa cifra es 10265.
Si os fijáis en las dos últimas líneas de esas 100 de antes, este número es superado, pero sigo sin obtener ningún error y el programa continúa con normalidad
El caso es que todo parece indicar que el problema está en que el código no contempla correctamente lo que debe pasar cuando no encuentra una solución al sudoku. Porque creo que es ahí cuando se queda tirado en un bucle infinito. Pero no veo que haya nada mal en el código!!
En fin, quizás el código es un poco largo para andar pidiendo ayuda, pero bueno, si le podéis echar un vistazo o darme alguna pista o algo, pues mejor que mejor...Yo mientras tanto seguiré dejándome los ojos en la pantalla a ver si encuentro el error esta noche
Un saludo y gracias
Mensaje modificado por LordSauron el Dec 9 2006, 03:28 AM
Solucionador de sudokus, Un problemilla con java
Dec 8 2006, 10:43 PM
