Podremos crear un Tablero de Sudoku a partir de otro o de una string de 81 caracteres del tipo
.4....36263.941...5.7.3.....9.3751..3.48.....17..62...716.9..2...96.......312..9.Donde los caracteres son las filas concatenadas y un punto significa que ésa casilla está vacía.
Aquí os dejo UNA solución, pero debo deciros que hay muchas más ;)
import java.util.*;
public class TableroSudoku implements Cloneable {
// constantes relativas al nº de filas y columnas del tablero
protected static final int MAXVALOR=9;
protected static final int FILAS=9;
protected static final int COLUMNAS=9;
////////////////////////////////////////////////////////////////////////////////
protected static final int raízFilas = (int) Math.sqrt(FILAS);
protected static final int raízColumnas = (int) Math.sqrt(COLUMNAS);
///////////////////////////////////////////////////////////////////////////////
protected static Random r = new Random();
protected int celdas[][]; // una celda vale cero si est\u00E1 libre.
public TableroSudoku() {
celdas = new int[FILAS][COLUMNAS]; //todas a cero.
}
// crea una copia de su par\u00E1metro
public TableroSudoku(TableroSudoku uno) {
TableroSudoku otro = (TableroSudoku) uno.clone();
this.celdas = otro.celdas;
}
// crear un tablero a parir de una configuraci\u00D3n inicial (las celdas vac\u00EDas
// se representan con el caracter ".".
public TableroSudoku(String s) {
this();
if(s.length() != FILAS*COLUMNAS) { //tiene que tener tantos caracteres como casillas MIO
throw new RuntimeException("Construcci\u00D3n de sudoku no v\u00E1lida.");
} else {
for(int f=0;f<FILAS;f++)
for(int c=0;c<COLUMNAS;c++) {
Character ch = s.charAt(f*FILAS+c);
celdas[f][c] = (Character.isDigit(ch) ? Integer.parseInt(ch.toString()) : 0 );
}
}
}
/* Realizar una copia en profundidad del objeto
* @see java.lang.Object#clone()
*/
public Object clone() {
TableroSudoku clon;
try {
clon = (TableroSudoku) super.clone();
clon.celdas = new int[FILAS][COLUMNAS];
for(int i=0; i<celdas.length; i++)
System.arraycopy(celdas[i], 0, clon.celdas[i], 0, celdas[i].length);
} catch (CloneNotSupportedException e) {
clon = null;
}
return clon;
}
/* Igualdad para la clase
* @see java.lang.Object#equals()
*/
public boolean equals(Object obj) {
if (obj instanceof TableroSudoku) {
TableroSudoku otro = (TableroSudoku) obj;
for(int f=0; f<FILAS; f++)
if(!Arrays.equals(this.celdas[f],otro.celdas[f]))
return false;
return true;
} else
return false;
}
public String toString() {
String s = "";
for(int f=0;f<FILAS;f++) {
for(int c=0;c<COLUMNAS;c++)
s += (celdas[f][c]==0 ? "." : String.format("%d",celdas[f][c]));
}
return s;
}
// devuelva true si la celda del tablero dada por fila y columna est\u00E1 vac\u00EDa.
protected boolean estaLibre(int fila, int columna) {
return celdas[fila][columna] == 0;
}
// devuelve el número de casillas libres en un sudoku.
protected int numeroDeLibres() {
int n=0;
for (int f = 0; f < FILAS; f++)
for (int c = 0; c < COLUMNAS; c++)
if(estaLibre(f,c))
n++;
return n;
}
protected int numeroDeFijos() {
return FILAS*COLUMNAS - numeroDeLibres();
}
// Devuelve true si @valor ya esta en la fila @fila.
protected boolean estaEnFila(int fila, int valor) {
// A completar por el alumno
for(int i=0; i < COLUMNAS; i++){
if(celdas[fila][i] == valor) return true;
}
return false;
}
// Devuelve true si @valor ya esta en la columna @columna.
protected boolean estaEnColumna(int columna, int valor) {
// A completar por el alumno
for(int i=0; i < FILAS; i++){
if(celdas[i][columna] == valor) return true;
}
return false;
}
// Devuelve true si @valor ya esta en subtablero al que pertence @fila y @columna.
protected boolean estaEnSubtablero(int fila, int columna, int valor) {
// A completar por el alumno
//int raízFilas = (int) Math.sqrt(FILAS);
//int raízColumnas = (int) Math.sqrt(COLUMNAS);
int x = fila/raízFilas;
int y = columna/raízColumnas;
int finicio = x * raízFilas;
int cinicio = y * raízColumnas;
for(int i= finicio; i< finicio + raízFilas; i++){
for(int j= cinicio; j < cinicio + raízFilas; j++ ){
if(celdas[i][j] == valor) return true;
}
}
return false;
}
// Devuelve true si se puede colocar el @valor en la @fila y @columna dadas.
protected boolean sePuedePonerEn(int fila, int columna, int valor) {
// A completar por el alumno
boolean resultado = false;
if(!estaEnColumna(columna,valor) && !estaEnFila(fila, valor) && !estaEnSubtablero(fila, columna, valor))
resultado = true;
return resultado;
}
protected void resolverTodos(List<TableroSudoku> soluciones, int fila, int columna) {
// A completar por el alumno
if (estaLibre(fila, columna)) {
for (int i = 1; i <= MAXVALOR; i++) {
if (sePuedePonerEn(fila, columna, i)) {
celdas[fila][columna] = i; //como se puede poner, lo escribo en esa posición
if(fila == FILAS -1 && columna == COLUMNAS -1){
// es la última casilla y ya los hemos colocado todos, por tanto es solucion
this.toString();
soluciones.add(new TableroSudoku(this)); //construtor que copia el tablero
} else if(fila < FILAS - 1 && columna == COLUMNAS -1){ //quedan filas pero no columnas
resolverTodos(soluciones, fila + 1, 0);
} else { //quedan aun columnas
resolverTodos(soluciones, fila, columna + 1);
}
celdas[fila][columna] = 0; //ponemos a 0 el escrito para volver a construir con el siguiente valor
}
}
} else { //no está libre
if(fila == FILAS -1 && columna == COLUMNAS -1){
// es la última casilla y ya los hemos colocado todos, por tanto es solucion
this.toString();
soluciones.add(new TableroSudoku(this)); //construtor que copia el tablero
} else if(fila < FILAS - 1 && columna == COLUMNAS -1){ //quedan filas pero no columnas
resolverTodos(soluciones, fila + 1, 0);
} else { //quedan aun columnas
resolverTodos(soluciones, fila, columna + 1);
}
}
}
public List<TableroSudoku> resolverTodos() {
List<TableroSudoku> sols = new LinkedList<TableroSudoku>();
resolverTodos(sols, 0, 0);
return sols;
}
public static void main(String arg[]) {
TableroSudoku t = new TableroSudoku(
".4....36263.941...5.7.3.....9.3751..3.48.....17..62...716.9..2...96.......312..9.");
List<TableroSudoku> lt = t.resolverTodos();
System.out.println(t);
System.out.println(lt.size());
for(Iterator<TableroSudoku> i= lt.iterator(); i.hasNext();) {
TableroSudoku ts = i.next();
System.out.println(ts);
}
}
}
Pues lo que hace es ver si lo que le damos es solución. si lo es, lo mete en una lista y en otro caso crea una lista con los posibles candidatos a soluciones (las cuasi-soluciones a las que puede llegar dando un único paso). Y con un while va usando recursivamente la función resolverTodos en cada una de ellas. De esta forma si alguna presunta solución (al pasarle el resolverTodos) no tiene huecos libres, será solución y se añadirá a la lista.
Saludos, espero que os haya gustado ;)
No hay comentarios:
Publicar un comentario