elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Como proteger una cartera - billetera de Bitcoin


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Java
| | | |-+  Resolvedor de SUDOKU de cualquier dimension		0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Resolvedor de SUDOKU de cualquier dimension  (Leído 1,549 veces)
velectronico

Desconectado Desconectado

Mensajes: 1


Ver Perfil
Resolvedor de SUDOKU de cualquier dimension
« 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.  
« Última modificación: 25 Enero 2019, 13:07 pm por velectronico » En línea
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Dimensión de Arreglos en C « 1 2 3 »
Programación C/C++ 		Principios en C 28 14,563 Último mensaje 27 Septiembre 2011, 23:35 pm
por Lambda
Problema en Dell Dimension 4600
Hardware 		GITANASSO 1 3,436 Último mensaje 16 Octubre 2012, 16:51 pm
por Aprendiz-Oscuro
Ani-Dimension hack wpe pro
Juegos y Consolas 		maelstron2 3 7,760 Último mensaje 13 Diciembre 2012, 00:28 am
por giankrlos26
¿Nos movemos a traves de una dimension estatica?
Foro Libre 		erest0r 6 3,129 Último mensaje 29 Agosto 2014, 19:24 pm
por erest0r
matriz de punteros de una dimensión - liberar memoria[C]
Programación C/C++ 		NOB2014 3 2,356 Último mensaje 11 Junio 2016, 02:35 am
por AlbertoBSD
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines