Resolvedor de SUDOKU de cualquier dimension

[velectronico]

Buenos dias, os adjunto un progama Java que es capaz de resolver Sudokus de cualquier dimension por el método de backtracking por lo que os da la primera solucion que escuentra. Sólo debeis de incluir los numeros iniciales y la dimensión. En cuando a los números iniciales teneis dos métodos para escribirlos: el primero es rellenar todas las posiciones del tablero por lo que os aconsejo usar éste sólo para el 4×4  porque a nadie le gustaria rellenar 81 casillas para el 9×9 o 256 para el 16×16, el otro metodo consiste en rellenar únicamente las posiciones con los numeros iniciales posicionándolos con su fila y columna ( cuidado con poner una coordenada fuera del tablero porque java os dará un error). Para cambiar la dimension tendreis que cambiar el valor de N del main de la clase SUDOKU. Os aconsejo que probeis con 4, 9 y 16 porque con 25 o superiores tarda mucho.

Si quereis hacer una prueba, utilizad el segundo metodo para incluir los números y escribir un 0  cuando os pregunte la filam de este modo buscará una solución para un tablero vacio.
Está formado por 3 clases:

Código (java) [Seleccionar] Expandir

import java.util.Scanner;
public class SUDOKU {

public static void main(String[] args) {
// TODO Auto-generated method stub
//int matriz[][][];//[nivel][fila][columna]
Tabla t;
Tabla tb;
int N=9; //dimension-----------------------------------------------------------------
int aux;
int a;
//matriz= new int [2][N][N];
t=new Tabla (N);
tb=new Tabla(N);
Scanner sc=new Scanner(System.in);
System.out.println("Escribe la opcion de relleno del Sudoku:");
System.out.println("0: todas las posiciones son rellenadas (0 para espacios en blanco)");
System.out.println("otro numero: rellenar solo los espacios con numero (fila,columna,valor)");
a=sc.nextInt();
if(a==0) {
for(int i =0;i<N*N;i++) {
System.out.print("Escribe la posicion fila : "+i/N+", columna: "+i%N+" =");
aux=sc.nextInt();
t.set(aux);
}
}
else {
System.out.println("Escribe 0 en la fila para dejar de rellenar posiciones");
boolean esc=true;
while(esc==true) {
int f;
int c;
int v;
System.out.println("Escribe la fila");
f=sc.nextInt();
if(f!=0) {
System.out.println("Escribe la columna");
c=sc.nextInt();
System.out.println("Escribe el número");
v=sc.nextInt();
t.set(f-1, c-1, v);
}
else
esc=false;
}
}
if(!t.noError()) {
System.out.println("No se puede resolver");
}
else {
for(int i =0;i<N;i++) {//fila
for(int j=0;j<N;j++) {//columna
tb.set(t.get(i, j));
}
}
//uso del backtracking--------------------
int i=0;
int j=0;
boolean retrocede=false;
int numaux=1;
while(i<N) {//fila
while(j<N) {//columna
numaux=1;
do{
while(t.get(i, j)==N&&retrocede==true) {
t.set(i, j, 0);
if(j==0&&i>0) {
j=N-1;
i--;
}
else
j--;

if(i==-1)
i=0;

while(t.get(i, j)==N&&tb.get(i, j)!=0&&retrocede==true) {
if(j==0&&i>0) {
j=N-1;
i--;
}
else
j--;

if(i==-1)
i=0;
}
if(retrocede==true&&t.get(i, j)!=N&&tb.get(i, j)==0)
retrocede=false;

}
numaux=t.get(i,j)+1;

if(tb.get(i, j)==0) {
do{
t.set(i, j, numaux);
retrocede=false;
numaux++;
}while(numaux<N+1&&!t.noError());
if(t.noError())
retrocede=false;
if(numaux==N+1&&!t.noError()) {
retrocede=true;

}
}
}while(retrocede==true);
j++;
//Si descomentas lo siguiente puedes observar como va realizando el bactracking paso a paso
/*System.out.println("");
System.out.println("");
for(int c=0;c<N;c++) {
for(int v=0;v<N;v++) {

System.out.print(t.get(c, v)+" ");
}
System.out.println("");
}*/

}
j=0;
i++;
}
//representaxion de la solucion
System.out.println("Solución:");
System.out.println("");
if(t.noError()) {
for(int c=0;c<N;c++) {
if(c%(int)(N/Math.sqrt(N))==0)
System.out.println(lineas(N));
for(int v=0;v<N;v++) {
if(v%(int)(N/Math.sqrt(N))==0)
System.out.print("|");
System.out.print(t.get(c, v)+"\t");
}
System.out.println("|");
}
System.out.println(lineas(N));}}
sc.close();
}
public static String lineas(int N) {
String sal="";
for(int i=0;i<N;i++)
sal=sal+"--------";
return sal+"-";
}

}

Código (java) [Seleccionar] Expandir

public class Tabla {
public Cuadrado cs[][];
public int dim;
public int n_i;
public int n_ii;
public int n_j;
public int n_jj;
public Tabla (int d) {
dim=d;
n_ii=0;
n_i=0;
n_jj=0;
n_j=0;
cs=new Cuadrado[(int)(d/Math.sqrt(d))][(int)(d/Math.sqrt(d))];
for(int i=0;i<(d/Math.sqrt(d));i++)
for(int j=0;j<(d/Math.sqrt(d));j++)
cs[i][j]=new Cuadrado((int)(d/Math.sqrt(d)));

}
//devuelve true si el Sudoku no tiene errores en cuanto a la distribución de números
public boolean noError() {
boolean sal=true;
int a[] =new int [dim];
int i=0;
int p=0;
int cont=0;
//comprueba las filas
while(sal==true&&i<(int)(dim/Math.sqrt(dim))) {
while(sal==true&&p<(int)(dim/Math.sqrt(dim))) {
cont=0;
for(int k=0;k<(int)(dim/Math.sqrt(dim));k++) {
for(int j=0;j<(int)(dim/Math.sqrt(dim));j++) {
a[cont]= cs[i][k].get(p,j);
cont++;
}
}
int ii=0;
int jj=0;
while(sal==true&&ii<a.length) {
while(sal==true&&jj<a.length) {
if(ii!=jj) {
if(a[ii]==a[jj])
if(a[ii]!=0&&(a[jj]!=0))
sal=false;
}
jj++;
}
ii++;
jj=0;
}
p++;
}
p=0;
i++;
}
//comprueba las columnas
int q=0;
int w=0;
int e=0;
int r=0;
while(sal==true&&q<(int)(dim/Math.sqrt(dim))) {
while(sal==true&&w<(int)(dim/Math.sqrt(dim))) {
cont=0;
for(e=0;e<(int)(dim/Math.sqrt(dim));e++) {
for(r=0;r<(int)(dim/Math.sqrt(dim));r++) {
a[cont]= cs[e][q].get(r,w);
cont++;
}
}
int ii=0;
int jj=0;
while(sal==true&&ii<a.length) {
while(sal==true&&jj<a.length) {
if(ii!=jj) {
if(a[ii]==a[jj])
if(a[ii]!=0&&(a[jj]!=0))
sal=false;
}
jj++;
}
ii++;
jj=0;
}
w++;
}
w=0;
q++;
}
//comprueba los cuadrados
int z=0;
int x=0;
while(sal==true&&z<(int)(dim/Math.sqrt(dim))) {
while(sal==true&&x<(int)(dim/Math.sqrt(dim))) {
sal=!cs[z][x].repetidos();
x++;
}
x=0;
z++;
}
return sal;
}
//posiciona un numero en la siguente posicion. se usa solo en la opcion de relleno del Sudoku =0 (en la que incluyes todas las posiciones del SudoKu)
public void set (int v) {
cs[n_i][n_j].set(n_ii,n_jj,v);
n_jj++;
if(n_jj==(int)(dim/Math.sqrt(dim))) {
n_j++;
n_jj=0;
if(n_j==(int)(dim/Math.sqrt(dim))) {
n_ii++;
n_j=0;
if(n_ii==(int)(dim/Math.sqrt(dim))) {
n_i++;
n_ii=0;
}
}
}
}
//Devuelve el valor de la fila i y columna j
public int get (int i,int j) {
int sub_i=i%((int)(dim/Math.sqrt(dim)));
int sub_j=j%((int)(dim/Math.sqrt(dim)));
int ir=i/((int)(dim/Math.sqrt(dim)));
int jr=j/((int)(dim/Math.sqrt(dim)));
return cs[ir][jr].get(sub_i, sub_j);
}
//posiciona el valor en la fila i y columna j
public void set(int i, int j, int v) {
int sub_i=i%((int)(dim/Math.sqrt(dim)));
int sub_j=j%((int)(dim/Math.sqrt(dim)));
int ir=i/((int)(dim/Math.sqrt(dim)));
int jr=j/((int)(dim/Math.sqrt(dim)));
cs[ir][jr].set(sub_i, sub_j,v);
}
}



Código (java) [Seleccionar] Expandir

public class Cuadrado {
public int cuadrado[][];
public int dimension; //lado

public Cuadrado(int d) {
dimension=d;
cuadrado=new int [d][d];
for(int i =0;i<d;i++) { //fila
for(int j=0;j<d;j++) { //columna
cuadrado[i][j]=0;
}
}
}
//comprueba si hay numero repetidos en un cuadrado
public boolean repetidos() {
boolean rep=false;
int i=0;
int j=0;
int cont =0;
int a[]=new int [dimension*dimension];
while(i<dimension) {
while(j<dimension) {
a[cont]=cuadrado[i][j];
cont++;
j++;
}
j=0;
i++;
}
i=0;
j=0;
while(rep==false&&i<a.length) {
while(rep==false&&j<a.length) {
if(i!=j) {
if(a[i]==a[j])
if(a[i]!=0&&(a[j]!=0))
rep=true;
}
j++;
}
i++;
j=0;
}
return rep;
}
//Devuelve el valor de la fila i y columna j
public int get(int i,int j) {
return cuadrado[i][j];
}
//Posiciona el valor v en la fila i y columna j
public void set(int i,int j,int v) {
cuadrado[i][j]=v;
}
}