Llop_Sudoku - Paquete Llop_Circular_Doubly_Linked_List_2D
Llop Site Home > Visual Studio .NET > Sudoku > Llop_Circular_Doubly_Linked_List_2D
Clase NodoBase
public class NodoBase {
private NodoBase arriba;
private NodoBase abajo;
private NodoBase izquierda;
private NodoBase derecha;
public NodoBase() {}
public void setArriba(NodoBase nuevoArriba) { arriba = nuevoArriba; }
public void setAbajo(NodoBase nuevoAbajo) { abajo = nuevoAbajo; }
public void setIzquierda(NodoBase nuevaIzquierda) { izquierda = nuevaIzquierda; }
public void setDerecha(NodoBase nuevaDerecha) { derecha = nuevaDerecha; }
public NodoBase getArriba() { return arriba; }
public NodoBase getAbajo() { return abajo; }
public NodoBase getIzquierda() { return izquierda; }
public NodoBase getDerecha() { return derecha; }
public boolean equals(Object o) {
if (o != null && o.getClass().equals(this.getClass())) {
NodoBase n = (NodoBase)o;
return arriba == n.arriba && abajo == n.abajo && derecha == n.derecha && izquierda == n.izquierda;
}
return false;
}
}
Clase Nodo
public class Nodo extends NodoBase {
private Columna columna;
public Nodo() {}
public void setColumna(Columna nuevaColumna) { columna = nuevaColumna; }
public Columna getColumna() { return columna; }
public boolean equals(Object o) {
if (o != null && o.getClass().equals(this.getClass())) {
if(!super.equals(o)) return false;
Nodo n = (Nodo)o;
return columna == n.columna;
}
return false;
}
}
Clase Columna
public class Columna extends NodoBase {
private int tamano;
private int id;
public Columna() {}
public int getTamano() { return tamano; }
public int getId() { return id; }
public void setTamano(int nuevoTamano) { tamano = nuevoTamano; }
public void setId(int nuevoId) { id = nuevoId; }
public boolean equals(Object o) {
if (o != null && o.getClass().equals(this.getClass())) {
if(!super.equals(o)) return false;
Columna c = (Columna)o;
return tamano == c.tamano && id == c.id;
}
return false;
}
}
Clase Lista
import java.util.*;
public class Lista {
private int maximoSoluciones;
private int cuentaSoluciones;
private long cambios;
private ArrayList matrizSoluciones;
private NodoBase raiz;
private Columna[] columnas;
private Nodo[][] nodos;
private NodoBase[] solucion;
public Lista(boolean[][] matriz) {
maximoSoluciones = 300;
matrizSoluciones = new ArrayList();
columnas = new Columna[matriz[0].length];
nodos = new Nodo[matriz.length][matriz[0].length];
solucion = new NodoBase[matriz[0].length];
raiz = new NodoBase(); // Inicializar nodo raiz como si la
raiz.setDerecha(raiz); // circular doubly linked list estuviera
raiz.setIzquierda(raiz); // vacía (sin columnas).
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);
}
}
}
public boolean[][][] soluciona() {
matrizSoluciones.clear();
cambios = cuentaSoluciones = 0;
soluciona(0);
boolean[][][] retorno = new boolean[cuentaSoluciones][][];
for (int i = 0; i < cuentaSoluciones; i++)
retorno[i] = (boolean[][])matrizSoluciones.get(i);
return retorno;
}
private void soluciona(int profundidad) {
if (raiz.getDerecha() == raiz) { trataSolucion(profundidad); return; }
if (cuentaSoluciones >= maximoSoluciones) return;
Columna columna = buscaColumna();
quitaColumna(columna);
NodoBase nodo1, nodo2;
for (nodo1 = columna.getAbajo(); nodo1 != columna; nodo1 = nodo1.getAbajo()) {
solucion[profundidad] = nodo1;
for (nodo2 = nodo1.getDerecha(); nodo2 != nodo1; nodo2 = nodo2.getDerecha())
quitaColumna(((Nodo)nodo2).getColumna());
soluciona(profundidad + 1);
for (nodo2 = nodo1.getIzquierda(); nodo2 != nodo1; nodo2 = nodo2.getIzquierda())
restauraColumna(((Nodo)nodo2).getColumna());
}
restauraColumna(columna);
}
private void trataSolucion(int profundidad) {
boolean[][] sol = new boolean[profundidad][];
boolean[] filaSol;
NodoBase nodo1, nodo2;
for (int i = 0; i < profundidad; i++) {
filaSol = new boolean[nodos[0].length];
nodo1 = solucion[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;
}
matrizSoluciones.add(sol);
cuentaSoluciones++;
}
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++;
}
}
public void setMaximoSoluciones(int nuevoMaxSols) throws Exception {
if (nuevoMaxSols < 1 || nuevoMaxSols > 300)
throw new Exception ("Valor no permitido. El máximo de soluciones debe estar entre 1 y 300.");
maximoSoluciones = nuevoMaxSols;
}
public int getMaximoSoluciones() { return maximoSoluciones; }
public long getCambios() { return cambios; }
}
¿Comentarios, sugerencias?: llopsite.at.yahoo.es | © 2005-07 Albert Lobo
Última actualización: 24-Feb-2007