Foro de elhacker.net

Programación => Java => Mensaje iniciado por: velectronico en 25 Enero 2019, 12:40 pm


Título: Resolvedor de SUDOKU de cualquier dimension
Publicado por: velectronico en 25 Enero 2019, 12:40 pm
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
  1. import java.util.Scanner;
  2. public class SUDOKU {
  3.  
  4. 	public static void main(String[] args) {
  5. 		// TODO Auto-generated method stub
  6. 		//int matriz[][][];//[nivel][fila][columna]
  7. 		Tabla t;
  8. 		Tabla tb;
  9. 		int N=9;		//dimension-----------------------------------------------------------------
  10. 		int aux;
  11. 		int a;
  12. 		//matriz= new int [2][N][N];
  13. 		t=new Tabla (N);
  14. 		tb=new Tabla(N);
  15. 		Scanner sc=new Scanner(System.in);
  16. 		System.out.println("Escribe la opcion de relleno del Sudoku:");
  17. 		System.out.println("0: todas las posiciones son rellenadas (0 para espacios en blanco)");
  18. 		System.out.println("otro numero: rellenar solo los espacios con numero (fila,columna,valor)");
  19. 		a=sc.nextInt();
  20. 		if(a==0) {
  21. 			for(int i =0;i<N*N;i++) {
  22. 				System.out.print("Escribe la posicion fila : "+i/N+", columna: "+i%N+" =");
  23. 				aux=sc.nextInt();
  24. 				t.set(aux);	
  25. 				}
  26. 		}
  27. 		else {
  28. 			System.out.println("Escribe 0 en la fila para dejar de rellenar posiciones");
  29. 			boolean esc=true;
  30. 			while(esc==true) {
  31. 				int f;
  32. 				int c;
  33. 				int v;
  34. 				System.out.println("Escribe la fila");
  35. 				f=sc.nextInt();
  36. 				if(f!=0) {
  37. 					System.out.println("Escribe la columna");
  38. 					c=sc.nextInt();
  39. 					System.out.println("Escribe el número");
  40. 					v=sc.nextInt();
  41. 					t.set(f-1, c-1, v);
  42. 					}
  43. 				else
  44. 					esc=false;	
  45. 			}	
  46. 		}	
  47. 		if(!t.noError()) {
  48. 			System.out.println("No se puede resolver");
  49. 		}
  50. 		else {
  51. 		for(int i =0;i<N;i++) {//fila
  52. 			for(int j=0;j<N;j++) {//columna
  53. 				tb.set(t.get(i, j));
  54. 			}
  55. 		}
  56. 		//uso del backtracking--------------------
  57. 		int i=0;
  58. 		int j=0;
  59. 		boolean retrocede=false;
  60. 		int numaux=1;
  61. 		while(i<N) {//fila
  62. 			while(j<N) {//columna
  63. 				numaux=1;
  64. 				do{ 
  65. 					while(t.get(i, j)==N&&retrocede==true) {
  66. 						t.set(i, j, 0);
  67. 							if(j==0&&i>0) {
  68. 								j=N-1;
  69. 								i--;
  70. 							}
  71. 							else
  72. 								j--;
  73.  
  74. 							if(i==-1)
  75. 								i=0;
  76.  
  77. 						while(t.get(i, j)==N&&tb.get(i, j)!=0&&retrocede==true) {
  78. 									if(j==0&&i>0) {
  79. 										j=N-1;
  80. 										i--;
  81. 									}
  82. 									else
  83. 										j--;
  84.  
  85. 									if(i==-1)
  86. 										i=0;
  87. 									}
  88. 						if(retrocede==true&&t.get(i, j)!=N&&tb.get(i, j)==0) 
  89. 							retrocede=false;
  90.  
  91. 					}
  92. 					numaux=t.get(i,j)+1;
  93.  
  94. 					if(tb.get(i, j)==0) {
  95. 						do{ 
  96. 						t.set(i, j, numaux);
  97. 						retrocede=false;
  98. 						numaux++;
  99. 						}while(numaux<N+1&&!t.noError());
  100. 						if(t.noError())
  101. 							retrocede=false;
  102. 						if(numaux==N+1&&!t.noError()) {
  103. 							retrocede=true;
  104.  
  105. 						}
  106. 					}
  107. 				}while(retrocede==true);
  108. 				j++;
  109. 				//Si descomentas lo siguiente puedes observar como va realizando el bactracking paso a paso
  110. 				/*System.out.println("");
  111. 				System.out.println("");
  112. 				for(int c=0;c<N;c++) {
  113. 					for(int v=0;v<N;v++) {
  114.  
  115. 						System.out.print(t.get(c, v)+" ");
  116. 					}
  117. 					System.out.println("");
  118. 				}*/
  119.  
  120. 			}
  121. 			j=0;
  122. 			i++;
  123. 		}
  124. 		//representaxion de la solucion
  125. 		System.out.println("Solución:");
  126. 		System.out.println("");
  127. 		if(t.noError()) {
  128. 		for(int c=0;c<N;c++) {
  129. 			if(c%(int)(N/Math.sqrt(N))==0) 
  130. 				System.out.println(lineas(N));	
  131. 			for(int v=0;v<N;v++) {
  132. 				if(v%(int)(N/Math.sqrt(N))==0)
  133. 					System.out.print("|");
  134. 				System.out.print(t.get(c, v)+"\t");			
  135. 			}
  136. 			System.out.println("|");
  137. 		}
  138. 		System.out.println(lineas(N));}}
  139. 		sc.close();
  140. 	}
  141. 	public static String lineas(int N) {
  142. 		String sal="";
  143. 		for(int i=0;i<N;i++)
  144. 			sal=sal+"--------";
  145. 		return sal+"-";
  146. 	}
  147.  
  148. }
Código
  1. public class Tabla {
  2. 	public Cuadrado cs[][];
  3. 	public int dim;
  4. 	public int n_i;
  5. 	public int n_ii;
  6. 	public int n_j;
  7. 	public int n_jj;
  8. 	public Tabla (int d) {
  9. 		dim=d;
  10. 		n_ii=0;
  11. 		n_i=0;
  12. 		n_jj=0;
  13. 		n_j=0;
  14. 		cs=new Cuadrado[(int)(d/Math.sqrt(d))][(int)(d/Math.sqrt(d))];
  15. 		for(int i=0;i<(d/Math.sqrt(d));i++)
  16. 			for(int j=0;j<(d/Math.sqrt(d));j++)
  17. 				cs[i][j]=new Cuadrado((int)(d/Math.sqrt(d)));
  18.  
  19. 	}
  20. 	//devuelve true si el Sudoku no tiene errores en cuanto a la distribución de números
  21. 	public boolean noError() {
  22. 		boolean sal=true;
  23. 		int a[] =new int [dim];
  24. 		int i=0;
  25. 		int p=0;
  26. 		int cont=0;
  27. 		//comprueba las filas
  28. 		while(sal==true&&i<(int)(dim/Math.sqrt(dim))) {	
  29. 			while(sal==true&&p<(int)(dim/Math.sqrt(dim))) {			
  30. 			cont=0;
  31. 				for(int k=0;k<(int)(dim/Math.sqrt(dim));k++) {
  32. 					for(int j=0;j<(int)(dim/Math.sqrt(dim));j++) {
  33. 						a[cont]= cs[i][k].get(p,j);
  34. 						cont++;
  35. 					}
  36. 				}
  37. 				int ii=0;
  38. 				int jj=0;
  39. 				while(sal==true&&ii<a.length) {
  40. 					while(sal==true&&jj<a.length) {
  41. 						if(ii!=jj) {
  42. 						if(a[ii]==a[jj])
  43. 							if(a[ii]!=0&&(a[jj]!=0))
  44. 							sal=false;
  45. 						}
  46. 						jj++;
  47. 					}
  48. 				ii++;
  49. 				jj=0;
  50. 				}
  51. 			p++;
  52. 			}
  53. 		p=0;
  54. 		i++;
  55. 		}
  56. 		//comprueba las columnas
  57. 		int q=0;
  58. 		int w=0;
  59. 		int e=0;
  60. 		int r=0;
  61. 		while(sal==true&&q<(int)(dim/Math.sqrt(dim))) {
  62. 			while(sal==true&&w<(int)(dim/Math.sqrt(dim))) {			
  63. 			cont=0;
  64. 				for(e=0;e<(int)(dim/Math.sqrt(dim));e++) {
  65. 					for(r=0;r<(int)(dim/Math.sqrt(dim));r++) {
  66. 						a[cont]= cs[e][q].get(r,w);
  67. 						cont++;
  68. 					}
  69. 				}
  70. 				int ii=0;
  71. 				int jj=0;
  72. 				while(sal==true&&ii<a.length) {
  73. 					while(sal==true&&jj<a.length) {
  74. 						if(ii!=jj) {
  75. 						if(a[ii]==a[jj])
  76. 							if(a[ii]!=0&&(a[jj]!=0))
  77. 							sal=false;
  78. 						}
  79. 						jj++;
  80. 					}
  81. 				ii++;
  82. 				jj=0;
  83. 				}
  84. 			w++;
  85. 			}
  86. 		w=0;
  87. 		q++;
  88. 		}
  89. 		//comprueba los cuadrados
  90. 		int z=0;
  91. 		int x=0;
  92. 		while(sal==true&&z<(int)(dim/Math.sqrt(dim))) {
  93. 			while(sal==true&&x<(int)(dim/Math.sqrt(dim))) {
  94. 				sal=!cs[z][x].repetidos();		
  95. 				x++;
  96. 			}
  97. 			x=0;
  98. 			z++;
  99. 		}		
  100. 		return sal;
  101. 	}
  102. 	//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)
  103. 	public void set (int v) {
  104. 		cs[n_i][n_j].set(n_ii,n_jj,v);
  105. 		n_jj++;
  106. 		if(n_jj==(int)(dim/Math.sqrt(dim))) {
  107. 			n_j++;
  108. 			n_jj=0;
  109. 			if(n_j==(int)(dim/Math.sqrt(dim))) {
  110. 				n_ii++;
  111. 				n_j=0;
  112. 				if(n_ii==(int)(dim/Math.sqrt(dim))) {
  113. 					n_i++;
  114. 					n_ii=0;
  115. 				}
  116. 			}
  117. 		}
  118. 	}
  119. 	//Devuelve el valor de la fila i y columna j
  120. 	public int get (int i,int j) {
  121. 		int sub_i=i%((int)(dim/Math.sqrt(dim)));
  122. 		int sub_j=j%((int)(dim/Math.sqrt(dim)));
  123. 		int ir=i/((int)(dim/Math.sqrt(dim)));
  124. 		int jr=j/((int)(dim/Math.sqrt(dim)));
  125. 		return cs[ir][jr].get(sub_i, sub_j);
  126. 	}
  127. 	//posiciona el valor en la fila i y columna j
  128. 	public void set(int i, int j, int v) {
  129. 		int sub_i=i%((int)(dim/Math.sqrt(dim)));
  130. 		int sub_j=j%((int)(dim/Math.sqrt(dim)));
  131. 		int ir=i/((int)(dim/Math.sqrt(dim)));
  132. 		int jr=j/((int)(dim/Math.sqrt(dim)));
  133. 		cs[ir][jr].set(sub_i, sub_j,v);
  134. 	}
  135. }
  136.  
  137.  
Código
  1. public class Cuadrado {
  2. 	public int cuadrado[][];
  3. 	public int dimension;	//lado
  4.  
  5. 	public Cuadrado(int d) {
  6. 		dimension=d;
  7. 		cuadrado=new int [d][d];
  8. 		for(int i =0;i<d;i++) {	//fila
  9. 			for(int j=0;j<d;j++) {	//columna
  10. 				cuadrado[i][j]=0;
  11. 			}
  12. 		}
  13. 	}
  14. 	//comprueba si hay numero repetidos en un cuadrado
  15. 	public boolean repetidos() {
  16. 		boolean rep=false;
  17. 		int i=0;
  18. 		int j=0;
  19. 		int cont =0;
  20. 		int a[]=new int [dimension*dimension];
  21. 		while(i<dimension) {
  22. 			while(j<dimension) {
  23. 				a[cont]=cuadrado[i][j];
  24. 				cont++;
  25. 				j++;
  26. 			}
  27. 			j=0;
  28. 			i++;
  29. 		}
  30. 		i=0;
  31. 		j=0;
  32. 		while(rep==false&&i<a.length) {
  33. 			while(rep==false&&j<a.length) {
  34. 				if(i!=j) {
  35. 				if(a[i]==a[j])
  36. 					if(a[i]!=0&&(a[j]!=0))
  37. 						rep=true;
  38. 				}
  39. 				j++;
  40. 			}
  41. 		i++;
  42. 		j=0;
  43. 		}
  44. 		return rep;	
  45. 	}
  46. 	//Devuelve el valor de la fila i y columna j
  47. 	public int get(int i,int j) {
  48. 		return cuadrado[i][j];
  49. 	}
  50. 	//Posiciona el valor v en la fila i y columna j
  51. 	public void set(int i,int j,int v) {
  52. 		cuadrado[i][j]=v;
  53. 	}
  54. }
  55.  


Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines