Restricción Sudoku (programación)

[Jose_Soft]

Buenas noches.

Me pregunto si alguno sabrá o tendrá idea alguna de que forma puedo hacer que un sudoku me diga rápidamente si tiene o no tiene solución.

Hay muchas formas de solucionar el sudoku. Lo he resuelto utilizando backtracking, lo malo es que hay algunos casos en los cuales se demora demasiado en informarme de que no encontró solución.

[LarryLurex]

Creo que todos los sudokus tienen solución. -.-"

[undert4ker_k4ne!]

Buenas noches.

Me pregunto si alguno sabrá o tendrá idea alguna de que forma puedo hacer que un sudoku me diga rápidamente si tiene o no tiene solución.

Hay muchas formas de solucionar el sudoku. Lo he resuelto utilizando backtracking, lo malo es que hay algunos casos en los cuales se demora demasiado en informarme de que no encontró solución.

Bueno la unica solucion es que la resuelvas y si no te sale bueno pues.
dale al search en internet ahi encuentras lo que quieras es tu gran amigo
:P

[lmchv]

Creo que todos los sudokus tienen solución. -.-"

No todos los sudokus tienen solucion, un numero mal puesto y ya no se cumplen todas las condiciones.

Bueno la unica solucion es que la resuelvas y si no te sale bueno pues.
dale al search en internet ahi encuentras lo que quieras es tu gran amigo
:P

Trata de leer nuevamente su post, esta preguntando una manera de determinar si un sudoku propuesto tiene solucion.

Un amigo armo un codigo con una funcion recursiva para solucionar un sudoku, es un codigo muy rapido, voy a ver si lo tiene por ahi y lo posteo.

[Jose_Soft]

Gracias ojalá lo encuentres =D
Mi restricción actual fue colocar como máximo de intentos 15 millones. Número excesivamente elevado me dirás. Originalmente le puse 500 000 pero me encontre con un sudoku en internet que para mi mala suerte (o para darme cuenta) se resolvió recién en el backtracking 10 millones y pico. Con los 15 millones hasta ahorita o he resuelto un tablero o mostrado que no tiene solución. A por cierto...en realidad mi interés por esta restricción es que programé el sudoku samurai y en algunas esquinas compartidas (sobre todo la última) se demora demasiado (al menos lo logra!!!) en decirme que no encuentra solución (como 3 minutos explotando mis pobres dos nucleos de procesador =( )

[tomas1251]

tal vez seria mejor que hagas lo que toda persona sana haria...

puedes consultar la "webdelprogramador" "conclase", el "rincondelc"; cuando posteaba en yahoo.answers habia mucha gente que tambien pedia lo mismo en la seccion de programacion, puede q alguno le hayan dado el codigo del programa. pero si lo que tu kieres es solucionar sudokus, creo q deberia empezar por validar el sudoku, es decir ver primero que tiene solucion unica!, eso es todo un jaraneo complejo, suerte!.

no te olvides de la web del programador es una pag donde te podrian dar, sino la restuesta, una buena asesoria en sus foros *_*

[Fonchi]

1. import java.io.*;
2. class Sudoku
3. {
4. int SQN = 3;
5. int N = 9;
6. int celda[][] = new int [N][N];
7. boolean sector[][][] = new boolean [SQN][SQN][N+1];
8. boolean RESUELTO;
9. int celda_actual;
10. public Sudoku ()
11. {
12. /* Inicializamos el sudoku con todo a cero */
13. int i, j, k;
14. celda_actual = 0;
15. RESUELTO = false;
16. for (i=0; i<9; i++)
17. for (j=0; j<9; j++)
18. celda [i][j] = 0;
19. for (i=0; i<3; i++)
20. for(j=0; j<3; j++)
21. for(k=1; k<=9; k++)
22. sector[i][j][k] = false;
23. }
24. public int getCelda(int i, int j)
25. {
26. return celda[i][j];
27. }
28. public void setCelda(int i, int j, int value)
29. {
30. celda[i][j] = value;
31. }
32. public boolean isResuelto()
33. {
34. return RESUELTO;
35. }
36. public void reset()
37. {
38. int i, j, k;
39. celda_actual = 0;
40. RESUELTO = false;
41. for (i=0; i<9; i++)
42. for (j=0; j<9; j++)
43. celda [i][j] = 0;
44. for (i=0; i<3; i++)
45. for(j=0; j<3; j++)
46. for(k=1; k<=9; k++)
47. sector[i][j][k] = false;
48. }
49. public void muestra ()
50. {
51. int i, j;
52. int h;
53. System.out.printf("\n\n");
54. for (i=0;i<N;i++)
55. {
56. if ((i%SQN == 0)&&(i!=0))
57. {
58. System.out.printf("\n -");
59. System.out.printf("--------|------------|----------");
60. System.out.printf("\n");
61. }
62. else
63. System.out.printf("\n");
64. for (j=0;j<N;j++)
65. if ((j%SQN==0)&&(j!=0))
66. {
67. System.out.printf(" |%3d ",celda[i][j]);
68. }
69. else
70. {
71. System.out.printf("%3d", celda[i][j]);
72. }
73. }
74. System.out.printf("\n\n");
75. }
76. public void resuelve ()
77. {
78. /* Comprueba que es resoluble, ajusta los sectores y lo resuelve */
79. if (checkIntegridad())
80. {
81. resuelve (0);
82. }
83. else
84. {
85. RESUELTO = false;
86. }
87. }
88. public boolean checkIntegridad ()
89. {
90. int i, j, k;
91. boolean VALIDO = true;
92. for(i=0; i<N; i++)
93. {
94. for(j=0; j<N; j++)
95. {
96. if (celda[i][j]!=0)
97. {
98. /* Veamos que no hay un número igual en toda la columna o fila*/
99. for(k=0; k<N; k++)
100. {
101. if( ((k!=j)&&(celda[i][k]==celda[i][j])) || ((k!=i)&&(celda[k][j]==celda[i][j])) )
102. {
103. VALIDO = false; System.out.printf("\nMalo 1 en (%d,%d) k = %d", i,j,k);
104. }
105. }
106. if(sector[i/SQN][j/SQN][celda[i][j]] == true) // ya estaba en el sector de antes
107. {
108. VALIDO = false; System.out.printf("\nMalo 2 en (%d, %d) ", i,j);
109. }
110. sector[i/SQN][j/SQN][celda[i][j]] = true;
111. }
112. }
113. }
114. return VALIDO;
115. }
116. public void resuelve (int celda_actual)
117. {
118. int i, j, n;
119. boolean LEGAL;
120. boolean VACIA = false;
121. boolean ULTIMA = true;
122. i = celda_actual/N;
123. j = celda_actual%N;
124. if (celda_actual < (N*N)-1)
125. ULTIMA=false;
126. if (celda[i][j] == 0)
127. VACIA = true;
128. n=0;
129. if (VACIA)
130. {
131. do
132. {
133. n++;
134. RESUELTO = false;
135. LEGAL = true;
136. /* ¿Es legal n? */
137. for(int k=0; k<N; k++)
138. if(celda[i][k]==n || celda[k][j]==n)
139. LEGAL = false;
140. if (sector[i/SQN][j/SQN][n]==true)
141. LEGAL = false;
142. if (LEGAL)
143. {
144. /* Escribimos el número en la casilla */
145. celda[i][j] = n;
146. sector[i/SQN][j/SQN][n] = true;
147. /* Si era la última, hemos acabado */
148. if (ULTIMA)
149. RESUELTO = true;
150. else // No es la última
151. {
152. /* Si no era la última, hay que seguir */
153. resuelve(celda_actual+1);
154. if (!RESUELTO) /* Si no ha tenido éxito, hay que borrar esta casilla y probar otra cosa */
155. {
156. celda[i][j] = 0;
157. sector[i/SQN][j/SQN][n] = false;
158. }
159. }
160. }
161. }while((RESUELTO==false)&&(n<N));
162. }
163. else // No está vacía
164. {
165. if(ULTIMA)
166. RESUELTO = true;
167. else
168. {
169. resuelve(celda_actual+1);
170. }
171. }
172. }
173. }

[Baldoceda]

1. import java.io.*;
2. class Sudoku
3. {
4. int SQN = 3;
5. int N = 9;
6. int celda[][] = new int [N][N];
7. boolean sector[][][] = new boolean [SQN][SQN][N+1];
8. boolean RESUELTO;
9. int celda_actual;
10. public Sudoku ()
11. {
12. /* Inicializamos el sudoku con todo a cero */
13. int i, j, k;
14. celda_actual = 0;
15. RESUELTO = false;
16. for (i=0; i<9; i++)
17. for (j=0; j<9; j++)
18. celda [i][j] = 0;
19. for (i=0; i<3; i++)
20. for(j=0; j<3; j++)
21. for(k=1; k<=9; k++)
22. sector[i][j][k] = false;
23. }
24. public int getCelda(int i, int j)
25. {
26. return celda[i][j];
27. }
28. public void setCelda(int i, int j, int value)
29. {
30. celda[i][j] = value;
31. }
32. public boolean isResuelto()
33. {
34. return RESUELTO;
35. }
36. public void reset()
37. {
38. int i, j, k;
39. celda_actual = 0;
40. RESUELTO = false;
41. for (i=0; i<9; i++)
42. for (j=0; j<9; j++)
43. celda [i][j] = 0;
44. for (i=0; i<3; i++)
45. for(j=0; j<3; j++)
46. for(k=1; k<=9; k++)
47. sector[i][j][k] = false;
48. }
49. public void muestra ()
50. {
51. int i, j;
52. int h;
53. System.out.printf("\n\n");
54. for (i=0;i<N;i++)
55. {
56. if ((i%SQN == 0)&&(i!=0))
57. {
58. System.out.printf("\n -");
59. System.out.printf("--------|------------|----------");
60. System.out.printf("\n");
61. }
62. else
63. System.out.printf("\n");
64. for (j=0;j<N;j++)
65. if ((j%SQN==0)&&(j!=0))
66. {
67. System.out.printf(" |%3d ",celda[i][j]);
68. }
69. else
70. {
71. System.out.printf("%3d", celda[i][j]);
72. }
73. }
74. System.out.printf("\n\n");
75. }
76. public void resuelve ()
77. {
78. /* Comprueba que es resoluble, ajusta los sectores y lo resuelve */
79. if (checkIntegridad())
80. {
81. resuelve (0);
82. }
83. else
84. {
85. RESUELTO = false;
86. }
87. }
88. public boolean checkIntegridad ()
89. {
90. int i, j, k;
91. boolean VALIDO = true;
92. for(i=0; i<N; i++)
93. {
94. for(j=0; j<N; j++)
95. {
96. if (celda[i][j]!=0)
97. {
98. /* Veamos que no hay un número igual en toda la columna o fila*/
99. for(k=0; k<N; k++)
100. {
101. if( ((k!=j)&&(celda[i][k]==celda[i][j])) || ((k!=i)&&(celda[k][j]==celda[i][j])) )
102. {
103. VALIDO = false; System.out.printf("\nMalo 1 en (%d,%d) k = %d", i,j,k);
104. }
105. }
106. if(sector[i/SQN][j/SQN][celda[i][j]] == true) // ya estaba en el sector de antes
107. {
108. VALIDO = false; System.out.printf("\nMalo 2 en (%d, %d) ", i,j);
109. }
110. sector[i/SQN][j/SQN][celda[i][j]] = true;
111. }
112. }
113. }
114. return VALIDO;
115. }
116. public void resuelve (int celda_actual)
117. {
118. int i, j, n;
119. boolean LEGAL;
120. boolean VACIA = false;
121. boolean ULTIMA = true;
122. i = celda_actual/N;
123. j = celda_actual%N;
124. if (celda_actual < (N*N)-1)
125. ULTIMA=false;
126. if (celda[i][j] == 0)
127. VACIA = true;
128. n=0;
129. if (VACIA)
130. {
131. do
132. {
133. n++;
134. RESUELTO = false;
135. LEGAL = true;
136. /* ¿Es legal n? */
137. for(int k=0; k<N; k++)
138. if(celda[i][k]==n || celda[k][j]==n)
139. LEGAL = false;
140. if (sector[i/SQN][j/SQN][n]==true)
141. LEGAL = false;
142. if (LEGAL)
143. {
144. /* Escribimos el número en la casilla */
145. celda[i][j] = n;
146. sector[i/SQN][j/SQN][n] = true;
147. /* Si era la última, hemos acabado */
148. if (ULTIMA)
149. RESUELTO = true;
150. else // No es la última
151. {
152. /* Si no era la última, hay que seguir */
153. resuelve(celda_actual+1);
154. if (!RESUELTO) /* Si no ha tenido éxito, hay que borrar esta casilla y probar otra cosa */
155. {
156. celda[i][j] = 0;
157. sector[i/SQN][j/SQN][n] = false;
158. }
159. }
160. }
161. }while((RESUELTO==false)&&(n<N));
162. }
163. else // No está vacía
164. {
165. if(ULTIMA)
166. RESUELTO = true;
167. else
168. {
169. resuelve(celda_actual+1);
170. }
171. }
172. }
173. }

y en q programa de java copio y pego eso?? netbeans o Jcreator?

si me ekivoco corrijanme :$