Llop_Sudoku - Paquete Llop_Sudoku_Java
Llop Site Home > Visual Studio .NET > Sudoku > Llop_Sudoku_Java
Clase Sudoku
import java.util.Date;
public class Sudoku {
// Constantes para definir el problema del sudoku.
public static final int CUATRO_X_CUATRO = 0;
public static final int SEIS_X_SEIS = 1;
public static final int NUEVE_X_NUEVE = 2;
public static final int DOCE_X_DOCE = 3;
public static final int DIECISEIS_X_DIECISEIS = 4;
public static final int[][] TABLA_RANGOS = {{4, 6}, {9, 12}, {24, 40}, {50, 72}, {96, 124}};
// El generador y el solucionador.
private Generador generador;
private Solucionador solucionador;
// Variables para representar el problema y la solución.
private int[] rangoPistas;
private int[][] problema;
private Solucion solucion;
// Variables que representan las diferentes dimensiones del sudoku.
protected int numeroCasillas;
protected int numeroCasillasRegion;
protected int numeroRegiones;
protected int numeroFilas;
protected int numeroColumnas;
protected int numeroFilasRegion;
protected int numeroColumnasRegion;
// Poner en true para sacar mensajes de seguimiento de las principales funciones de la clase.
private boolean depurar;
public Sudoku(int numFil, int numCol, int numFilReg, int numColReg) throws Exception {
depurar = false;
depura("--- Constructor Sudoku " + numFil + "x" + numCol + " ---");
long t1 = new Date().getTime();
if (numFil % numFilReg != 0 || numCol % numColReg != 0)
throw new Exception("Imposible crear un sudoku de estas dimensiones. Las regiones no caben bien en la cuadrícula.");
numeroFilas = numFil;
numeroColumnas = numCol;
numeroFilasRegion = numFilReg;
numeroColumnasRegion = numColReg;
numeroCasillas = numFil * numCol;
numeroCasillasRegion = numFilReg * numColReg;
numeroRegiones = (numFil / numFilReg) * (numCol / numColReg);
switch(numeroCasillas) {
case 16: rangoPistas = TABLA_RANGOS[CUATRO_X_CUATRO]; break;
case 36: rangoPistas = TABLA_RANGOS[SEIS_X_SEIS]; break;
case 81: rangoPistas = TABLA_RANGOS[NUEVE_X_NUEVE]; break;
case 144: rangoPistas = TABLA_RANGOS[DOCE_X_DOCE]; break;
case 256: rangoPistas = TABLA_RANGOS[DIECISEIS_X_DIECISEIS]; break;
default: throw new Exception("El tamaño del sudoku no está permitido.");
}
generador = new Generador(this);
solucionador = new Solucionador(this);
depura("Instancia de Sudoku " + numFil + "x" + numCol + " creada en " + (new Date().getTime() - t1) + " ms.");
}
private void depura(String mensaje) { if (depurar) System.out.println(mensaje); }
public Problema generaProblema() throws Exception {
long t1 = new Date().getTime();
Problema problema = generador.genera();
depura("Generación sudoku: " + (new Date().getTime() - t1) + " ms.");
return problema;
}
private void resuelveProblema() throws Exception {
long t1 = new Date().getTime();
solucion = solucionador.resuelveProblema(problema);
depura("Solución sudoku: " + (new Date().getTime() - t1) + " ms.");
}
public void setNumeroPistas(int nuevoNumeroPistas) throws Exception {
if (nuevoNumeroPistas < rangoPistas[0] || nuevoNumeroPistas > rangoPistas[1])
throw new Exception("Número de pistas fuera de rango.");
generador.setNumeroPistas(nuevoNumeroPistas);
}
public void setProblema(Problema nuevoProblema) throws Exception {
setProblema(nuevoProblema.getProblema());
}
public void setProblema(int[][] nuevoProblema) throws Exception {
if (nuevoProblema.length != numeroFilas || nuevoProblema[0].length != numeroColumnas)
throw new Exception("El problema no respeta las dimensiones de este sudoku.");
for (int i = 0; i < numeroFilas; i++) for (int j = 0; j < numeroColumnas; j++)
if (nuevoProblema[i][j] < 0 || nuevoProblema[i][j] > numeroCasillasRegion)
throw new Exception("El valor de fila " + i + ", columna " + j + " no es válido.");
problema = nuevoProblema;
solucion = null;
}
public void setMaximoSoluciones(int nuevoMaxSols) throws Exception {
solucionador.setMaximoSoluciones(nuevoMaxSols);
}
public Solucion getSolucion() throws Exception {
if (problema == null) throw new Exception("Todavía no se ha establecido el problema.");
if (solucion == null) resuelveProblema();
return solucion;
}
public int getNumeroPistas() { return generador.getNumeroPistas(); }
public int getMaximoSoluciones() { return solucionador.getMaximoSoluciones(); }
public int getNumeroCasillas() { return numeroCasillas; }
public int getNumeroCasillasRegion() { return numeroCasillasRegion; }
public int getNumeroRegiones() { return numeroRegiones; }
public int getNumeroFilas() { return numeroFilas; }
public int getNumeroColumnas() { return numeroColumnas; }
public int getNumeroFilasRegion() { return numeroFilasRegion; }
public int getNumeroColumnasRegion() { return numeroColumnasRegion; }
public int[] getRangoPistas() { return rangoPistas; }
public static int[] getRangoPistasPorDimension(int dimension) { return TABLA_RANGOS[dimension]; }
}
Clase Problema
public class Problema {
private int[][] problema;
private long tiempoGeneracion;
private long cambios;
public Problema(int[][] nuevoProblema, long nuevoTiempoGeneracion, long nuevoCambios) {
problema = nuevoProblema;
tiempoGeneracion = nuevoTiempoGeneracion;
cambios = nuevoCambios;
}
public int[][] getProblema() { return problema; }
public long getTiempoGeneracion() { return tiempoGeneracion; }
public long getCambios() { return cambios; }
}
Clase Solucion
public class Solucion {
private int[][][] soluciones;
private int numeroSoluciones;
private long tiempoSolucion;
private long cambios;
public Solucion(int[][][] nuevoSoluciones, long nuevoTiempoSolucion, long nuevoCambios) {
soluciones = nuevoSoluciones;
numeroSoluciones = soluciones.length;
tiempoSolucion = nuevoTiempoSolucion;
cambios = nuevoCambios;
}
public int[][] getSolucion(int numeroSolucion) throws Exception {
if (numeroSolucion < 0 || numeroSolucion > soluciones.length - 1)
throw new Exception("'numeroSolucion' no es un índice válido.");
return soluciones[numeroSolucion];
}
public int getNumeroSoluciones() { return numeroSoluciones; }
public long getTiempoSolucion() { return tiempoSolucion; }
public long getCambios() { return cambios; }
}
Clase Generador
import Llop_Circular_Doubly_Linked_List_2D.*;
import java.util.Date;
import java.util.Random;
public class Generador {
// Variables del sudoku.
private int numeroFilasSudoku;
private int numeroColumnasSudoku;
private int numeroFilasRegionSudoku;
private int numeroColumnasRegionSudoku;
private int numeroRegionesSudoku;
private int numeroCasillasRegionSudoku;
private int numeroCasillasSudoku;
private int offsetCasillaSudoku;
private int offsetColumnaSudoku;
private int offsetRegionSudoku;
// Variables de control.
private int numeroPistas;
private int cuentaPistas;
private int cuentaSoluciones;
private boolean solucionConseguida;
private long cambios;
private int contadorBusqueda;
private float frecuenciaAleatorias;
// Poner en true para sacar mensajes de seguimiento de las principales funciones de la clase.
private boolean depurar;
// Variables para almacenar el problema.
private NodoBase[] problemaTemp;
private int[][] problema;
private int[][] problemaMaster;
// Variables que representan la circular doubly linked list.
private boolean[][] matriz;
private int[][][][] patron;
private NodoBase raiz;
private Columna[] columnas;
private Nodo[][] nodos;
public Generador(Sudoku sudoku) throws Exception {
depurar = false;
depura("--- Constructor Generador ---");
long t1 = new Date().getTime();
numeroFilasSudoku = sudoku.getNumeroFilas();
numeroColumnasSudoku = sudoku.getNumeroColumnas();
numeroRegionesSudoku = sudoku.getNumeroRegiones();
numeroCasillasSudoku = sudoku.getNumeroCasillas();
numeroCasillasRegionSudoku = sudoku.getNumeroCasillasRegion();
numeroFilasRegionSudoku = sudoku.getNumeroFilasRegion();
numeroColumnasRegionSudoku = sudoku.getNumeroColumnasRegion();
offsetColumnaSudoku = numeroCasillasRegionSudoku * numeroFilasSudoku;
offsetRegionSudoku = offsetColumnaSudoku + numeroCasillasRegionSudoku * numeroColumnasSudoku;
offsetCasillaSudoku = offsetRegionSudoku + numeroCasillasRegionSudoku * numeroRegionesSudoku;
numeroPistas = sudoku.getRangoPistas()[0];
int numeroFilasMatriz = numeroCasillasRegionSudoku * numeroCasillasSudoku;
int numeroColumnasMatriz = offsetCasillaSudoku + numeroCasillasSudoku;
if (numeroCasillasSudoku == 256) frecuenciaAleatorias = 9;
else if (numeroCasillasSudoku == 144) frecuenciaAleatorias = 3.5f;
else frecuenciaAleatorias = 2.5f;
int valor = 0, fila = 0, columna = 0, region = 0, casilla = 0;
int restriccionFila, restriccionColumna, restriccionRegion, restriccionCasilla;
matriz = new boolean[numeroFilasMatriz][numeroColumnasMatriz];
patron = new int[numeroFilasSudoku][numeroColumnasSudoku][numeroCasillasRegionSudoku][4];
for (int i = 0; i < numeroFilasMatriz; i++) {
restriccionFila = numeroColumnasSudoku * fila + valor;
restriccionColumna = offsetColumnaSudoku + numeroFilasSudoku * columna + valor;
restriccionRegion = offsetRegionSudoku + numeroRegionesSudoku * region + valor;
restriccionCasilla = offsetCasillaSudoku + casilla;
matriz[i][restriccionFila] = true;
matriz[i][restriccionColumna] = true;
matriz[i][restriccionRegion] = true;
matriz[i][restriccionCasilla] = true;
patron[fila][columna][valor][0] = restriccionFila;
patron[fila][columna][valor][1] = restriccionColumna;
patron[fila][columna][valor][2] = restriccionRegion;
patron[fila][columna][valor][3] = restriccionCasilla;
columna++;
casilla++;
if (casilla % numeroCasillasSudoku == 0) casilla = 0;
if ((i + 1) % numeroCasillasSudoku == 0) valor++;
if (columna % numeroColumnasSudoku == 0) { columna = 0; fila++; }
if (fila % numeroFilasSudoku == 0) fila = 0;
region = (fila / numeroFilasRegionSudoku) * numeroFilasRegionSudoku + columna / numeroColumnasRegionSudoku;
}
raiz = new NodoBase();
columnas = new Columna[matriz[0].length];
nodos = new Nodo[matriz.length][matriz[0].length];
problemaTemp = new NodoBase[numeroCasillasSudoku];
problemaMaster = new int[numeroFilasSudoku][numeroColumnasSudoku];
raiz.setDerecha(raiz);
raiz.setIzquierda(raiz);
inicializaTabla();
depura("Instancia de Generador creada en " + (new Date().getTime() - t1) + " ms.");
}
private void inicializaTabla() {
int i, j, k;
for (i = 0; i < matriz.length; i++) {
for (j = 0; j < matriz[i].length; j++) {
if (matriz[i][j]) {
if (nodos[i][j] == null) nodos[i][j] = new Nodo();
for (k = j + 1; k != j; k++) {
if (k == matriz[i].length) k = 0;
if (matriz[i][k]) { if (nodos[i][k] == null) nodos[i][k] = new Nodo(); break; }
}
nodos[i][j].setDerecha(nodos[i][k]);
for (k = j - 1; k != j; k--) {
if (k == -1) k = matriz[i].length - 1;
if (matriz[i][k]) { if (nodos[i][k] == null) nodos[i][k] = new Nodo(); break; }
}
nodos[i][j].setIzquierda(nodos[i][k]);
for (k = i + 1; k != i; k++) {
if (k == matriz.length) {
if (columnas[j] == null) { columnas[j] = new Columna(); columnas[j].setId(j); }
nodos[i][j].setAbajo(columnas[j]); break;
}
if (matriz[k][j]) {
if (nodos[k][j] == null) nodos[k][j] = new Nodo();
nodos[i][j].setAbajo(nodos[k][j]); break;
}
}
for (k = i - 1; k != i; k--) {
if (k == -1) {
if (columnas[j] == null) { columnas[j] = new Columna(); columnas[j].setId(j); } nodos[i][j].setArriba(columnas[j]);
break;
}
if (matriz[k][j]) {
if (nodos[k][j] == null) nodos[k][j] = new Nodo();
nodos[i][j].setArriba(nodos[k][j]); break;
}
}
if (columnas[j] == null) { columnas[j] = new Columna(); columnas[j].setId(j); }
nodos[i][j].setColumna(columnas[j]);
}
}
}
for (j = 0; j < columnas.length; j++) {
if (columnas[j] != null) {
for (k = j + 1; k != j; k++) {
if (k == columnas.length) {
columnas[j].setDerecha(raiz);
raiz.setIzquierda(columnas[j]);
break;
}
if (columnas[k] != null) { columnas[j].setDerecha(columnas[k]); break; }
}
for (k = j - 1; k != j; k--) {
if (k == -1) {
columnas[j].setIzquierda(raiz);
raiz.setDerecha(columnas[j]);
break;
}
if (columnas[k] != null) { columnas[j].setIzquierda(columnas[k]); break; }
}
for (k = 0; ; k++) {
if (k == matriz.length) { columnas[j].setAbajo(columnas[j]); break; }
if (matriz[k][j]) { columnas[j].setAbajo(nodos[k][j]); break; }
}
for (k = matriz.length - 1; ; k--) {
if (k == -1) { columnas[j].setArriba(columnas[j]); break; }
if (matriz[k][j]) { columnas[j].setArriba(nodos[k][j]); break; }
}
for (i = k = 0; k < matriz.length; k++) if (matriz[k][j]) i++;
columnas[j].setTamano(i);
}
}
}
private void depura(String mensaje) { if (depurar) System.out.println(mensaje); }
public Problema genera() {
problema = new int[numeroFilasSudoku][numeroColumnasSudoku];
long t1 = new Date().getTime(), t2 = t1;
inventaSolucion();
depura("Inventa solución: " + (new Date().getTime() - t2) + " ms.");
t2 = new Date().getTime();
while (!generaProblema()) { restauraProblema(); }
depura("Genera problema: " + (new Date().getTime() - t2) + " ms.");
return new Problema(problema, new Date().getTime() - t1, cambios);
}
private void inventaSolucion() {
solucionConseguida = false;
inventaSolucion(0);
}
private void inventaSolucion(int profundidad) {
if (solucionConseguida) return;
if (raiz.getDerecha() == raiz) { trataSolucion(); return; }
Columna columna = buscaColumnaRandom();
quitaColumna(columna);
NodoBase nodo1, nodo2;
for (nodo1 = columna.getAbajo(); nodo1 != columna; nodo1 = nodo1.getAbajo()) {
problemaTemp[profundidad] = nodo1;
for (nodo2 = nodo1.getDerecha(); nodo2 != nodo1; nodo2 = nodo2.getDerecha())
quitaColumna(((Nodo)nodo2).getColumna());
inventaSolucion(profundidad + 1);
for (nodo2 = nodo1.getIzquierda(); nodo2 != nodo1; nodo2 = nodo2.getIzquierda())
restauraColumna(((Nodo)nodo2).getColumna());
}
restauraColumna(columna);
}
private void trataSolucion() {
solucionConseguida = true;
boolean[][] sol = new boolean[problemaTemp.length][];
boolean[] filaSol;
int i, j, valor, casilla, fila, columna;
NodoBase nodo1, nodo2;
for (i = 0; i < problemaTemp.length; i++) {
filaSol = new boolean[nodos[0].length];
nodo1 = problemaTemp[i];
filaSol[((Nodo)nodo1).getColumna().getId()] = true;
for (nodo2 = nodo1.getDerecha(); nodo2 != nodo1; nodo2 = nodo2.getDerecha())
filaSol[((Nodo)nodo2).getColumna().getId()] = true;
sol[i] = filaSol;
}
for (i = 0; i < sol.length; i++){
for (j = 0; !sol[i][j]; j++) {}
valor = j % numeroColumnasSudoku + 1;
for (j = sol[i].length - 1; !sol[i][j]; j--) {}
casilla = j - offsetCasillaSudoku;
fila = casilla / numeroColumnasSudoku;
columna = casilla % numeroColumnasSudoku;
problemaMaster[fila][columna] = problema[fila][columna] = valor;
}
}
private boolean generaProblema() {
cuentaPistas = problemaTemp.length;
Random random = new Random();
int i, filaRnd, columnaRnd, repes = 0;
for (i = 0; i < problemaTemp.length; i++) {
do {
filaRnd = random.nextInt(numeroFilasSudoku);
columnaRnd = random.nextInt(numeroColumnasSudoku);
} while (problema[filaRnd][columnaRnd] == 0);
problema[filaRnd][columnaRnd] = 0;
cuentaPistas--;
solucionaRapido();
if (cuentaSoluciones == 1 && cuentaPistas == numeroPistas) return true;
else if (cuentaSoluciones == 2) {
problema[filaRnd][columnaRnd] = problemaMaster[filaRnd][columnaRnd];
cuentaPistas++; repes++; i --;
}
if (repes == problemaTemp.length - cuentaPistas) break;
}
return false;
}
private int iSR;
private int jSR;
private int kSR;
private int[] filaPatron;
private void solucionaRapido() {
cambios = cuentaSoluciones = 0;
for (iSR = 0; iSR < problema.length; iSR++) for (jSR = 0; jSR < problema[0].length; jSR++)
if (problema[iSR][jSR] > 0) {
filaPatron = patron[iSR][jSR][problema[iSR][jSR] - 1];
for (kSR = 0; kSR < 4; kSR++) quitaColumna(filaPatron[kSR]);
}
soluciona();
for (iSR = problema.length - 1; iSR >= 0 ; iSR--) for (jSR = problema[0].length - 1; jSR >= 0; jSR--)
if (problema[iSR][jSR] > 0) {
filaPatron = patron[iSR][jSR][problema[iSR][jSR] - 1];
for (kSR = 3; kSR >= 0; kSR--) restauraColumna(filaPatron[kSR]);
}
}
private void soluciona() {
if (cuentaSoluciones >= 2) return;
if (raiz.getDerecha() == raiz) { cuentaSoluciones++; return; }
Columna columna = buscaColumna();
quitaColumna(columna);
NodoBase nodo1, nodo2;
for (nodo1 = columna.getAbajo(); nodo1 != columna; nodo1 = nodo1.getAbajo()) {
for (nodo2 = nodo1.getDerecha(); nodo2 != nodo1; nodo2 = nodo2.getDerecha())
quitaColumna(((Nodo)nodo2).getColumna());
soluciona();
for (nodo2 = nodo1.getIzquierda(); nodo2 != nodo1; nodo2 = nodo2.getIzquierda())
restauraColumna(((Nodo)nodo2).getColumna());
}
restauraColumna(columna);
}
private Columna buscaColumnaRandom() {
if (contadorBusqueda++ % frecuenciaAleatorias != 0) return buscaColumna();
int random = new Random().nextInt(nodos[0].length);
NodoBase nodo = raiz.getDerecha();
for (int i = 0; i <= random; i++) nodo = nodo.getDerecha();
if (nodo == raiz) nodo = nodo.getDerecha();
return (Columna)nodo;
}
private Columna buscaColumna() {
int tamano = nodos.length;
Columna columna = null;
for (NodoBase nodo = raiz.getDerecha(); nodo != raiz; nodo = nodo.getDerecha())
if (((Columna)nodo).getTamano() < tamano) {
columna = (Columna)nodo;
tamano = columna.getTamano();
}
return columna;
}
public void restauraColumna(int indiceColumna) { restauraColumna(columnas[indiceColumna]); }
private void restauraColumna(Columna columna) {
NodoBase nodo1, nodo2;
for (nodo1 = columna.getArriba(); nodo1 != columna; nodo1 = nodo1.getArriba())
for (nodo2 = nodo1.getIzquierda(); nodo2 != nodo1; nodo2 = nodo2.getIzquierda()) {
((Nodo)nodo2).getColumna().setTamano(((Nodo)nodo2).getColumna().getTamano() + 1);
nodo2.getAbajo().setArriba(nodo2);
nodo2.getArriba().setAbajo(nodo2);
cambios++;
}
columna.getDerecha().setIzquierda(columna);
columna.getIzquierda().setDerecha(columna);
cambios++;
}
public void quitaColumna(int indiceColumna) { quitaColumna(columnas[indiceColumna]); }
private void quitaColumna(Columna columna) {
NodoBase nodo1, nodo2;
columna.getDerecha().setIzquierda(columna.getIzquierda());
columna.getIzquierda().setDerecha(columna.getDerecha());
cambios++;
for (nodo1 = columna.getAbajo(); nodo1 != columna; nodo1 = nodo1.getAbajo())
for (nodo2 = nodo1.getDerecha(); nodo2 != nodo1; nodo2 = nodo2.getDerecha()) {
nodo2.getAbajo().setArriba(nodo2.getArriba());
nodo2.getArriba().setAbajo(nodo2.getAbajo());
((Nodo)nodo2).getColumna().setTamano(((Nodo)nodo2).getColumna().getTamano() - 1);
cambios++;
}
}
private void restauraProblema() {
for (int i = 0; i < problema.length; i++) for (int j = 0; j < problema[i].length; j++)
if (problema[i][j] == 0) problema[i][j] = problemaMaster[i][j];
}
public long getCambios() { return cambios; }
public int getNumeroPistas() { return numeroPistas; }
public void setNumeroPistas(int nuevoNumeroPistas) { numeroPistas = nuevoNumeroPistas; }
}
Clase Solucionador
import Llop_Circular_Doubly_Linked_List_2D.Lista;
import java.util.Date;
public class Solucionador {
// Variables del sudoku.
private int numeroFilasSudoku;
private int numeroColumnasSudoku;
private int numeroFilasRegionSudoku;
private int numeroColumnasRegionSudoku;
private int numeroRegionesSudoku;
private int numeroCasillasRegionSudoku;
private int numeroCasillasSudoku;
private int offsetCasillaSudoku;
private int offsetColumnaSudoku;
private int offsetRegionSudoku;
// Poner en true para sacar mensajes de seguimiento de las principales funciones de la clase.
private boolean depurar;
// Variables circular doubly linked list
private Lista lista;
private int[][][][] patron;
public Solucionador(Sudoku sudoku) {
depurar = false;
depura("--- Constructor Solucionador ---");
long t1 = new Date().getTime();
numeroFilasSudoku = sudoku.getNumeroFilas();
numeroColumnasSudoku = sudoku.getNumeroColumnas();
numeroRegionesSudoku = sudoku.getNumeroRegiones();
numeroCasillasSudoku = sudoku.getNumeroCasillas();
numeroCasillasRegionSudoku = sudoku.getNumeroCasillasRegion();
numeroFilasRegionSudoku = sudoku.getNumeroFilasRegion();
numeroColumnasRegionSudoku = sudoku.getNumeroColumnasRegion();
offsetColumnaSudoku = numeroCasillasRegionSudoku * numeroFilasSudoku;
offsetRegionSudoku = offsetColumnaSudoku + numeroCasillasRegionSudoku * numeroColumnasSudoku;
offsetCasillaSudoku = offsetRegionSudoku + numeroCasillasRegionSudoku * numeroRegionesSudoku;
inicializaLista();
depura("Instancia de Solucionador creada en " + (new Date().getTime() - t1) + " ms.");
}
private void inicializaLista() {
int valor = 0, fila = 0, columna = 0, region = 0, casilla = 0;
int restriccionFila, restriccionColumna, restriccionRegion, restriccionCasilla;
int numeroFilasMatriz = numeroCasillasRegionSudoku * numeroCasillasSudoku;
int numeroColumnasMatriz = offsetCasillaSudoku + numeroCasillasSudoku;
boolean[][] matriz = new boolean[numeroFilasMatriz][numeroColumnasMatriz];
patron = new int[numeroFilasSudoku][numeroColumnasSudoku][numeroCasillasRegionSudoku][4];
for (int i = 0; i < numeroFilasMatriz; i++) {
restriccionFila = numeroColumnasSudoku * fila + valor;
restriccionColumna = offsetColumnaSudoku + numeroFilasSudoku * columna + valor;
restriccionRegion = offsetRegionSudoku + numeroRegionesSudoku * region + valor;
restriccionCasilla = offsetCasillaSudoku + casilla;
matriz[i][restriccionFila] = true;
matriz[i][restriccionColumna] = true;
matriz[i][restriccionRegion] = true;
matriz[i][restriccionCasilla] = true;
patron[fila][columna][valor][0] = restriccionFila;
patron[fila][columna][valor][1] = restriccionColumna;
patron[fila][columna][valor][2] = restriccionRegion;
patron[fila][columna][valor][3] = restriccionCasilla;
columna++;
casilla++;
if (casilla % numeroCasillasSudoku == 0) casilla = 0;
if ((i + 1) % numeroCasillasSudoku == 0) valor++;
if (columna % numeroColumnasSudoku == 0) { columna = 0; fila++; }
if (fila % numeroFilasSudoku == 0) fila = 0;
region = (fila / numeroFilasRegionSudoku) * numeroFilasRegionSudoku + columna / numeroColumnasRegionSudoku;
}
lista = new Lista(matriz);
}
private void depura(String mensaje) { if (depurar) System.out.println(mensaje); }
public Solucion resuelveProblema(int[][] problema) throws Exception {
if (problema == null) throw new Exception("No se ha establecido el problema en este sudoku.");
long t1 = new Date().getTime();
int i, j, k, valor, casilla, fila, columna;
for (i = 0; i < problema.length; i++) for (j = 0; j < problema[0].length; j++)
if (problema[i][j] > 0)
for (k = 0; k < 4; k++)
lista.quitaColumna(patron[i][j][problema[i][j] - 1][k]);
boolean[][][] sols = lista.soluciona();
for (i = problema.length - 1; i >= 0 ; i--) for (j = problema[0].length - 1; j >= 0; j--)
if (problema[i][j] > 0)
for (k = 3; k >= 0; k--)
lista.restauraColumna(patron[i][j][problema[i][j] - 1][k]);
int[][][] soluciones = new int[sols.length][numeroFilasSudoku][numeroColumnasSudoku];
for (i = 0; i < sols.length; i++) {
for (j = 0; j < problema.length; j++) for (k = 0; k < problema[j].length; k++)
if (problema[j][k] != 0) soluciones[i][j][k] = problema[j][k];
for (j = 0; j < sols[i].length; j++) {
for (k = 0; !sols[i][j][k]; k++) {}
valor = k % numeroColumnasSudoku + 1;
for (k = sols[i][j].length - 1; !sols[i][j][k]; k--) {}
casilla = k - offsetCasillaSudoku;
fila = casilla / numeroColumnasSudoku;
columna = casilla % numeroColumnasSudoku;
soluciones[i][fila][columna] = valor;
}
}
depura("Tiempo solución: " + (new Date().getTime() - t1) + " ms");
depura("Numero cambios solución: " + lista.getCambios());
depura("Numero soluciones: " + sols.length);
return new Solucion(soluciones, new Date().getTime() - t1, lista.getCambios());
}
public void setMaximoSoluciones(int nuevoMaxSols) throws Exception {
lista.setMaximoSoluciones(nuevoMaxSols);
}
public int getMaximoSoluciones() { return lista.getMaximoSoluciones(); }
}
¿Comentarios, sugerencias?: llopsite.at.yahoo.es | © 2005-07 Albert Lobo
Última actualización: 18-Feb-2007