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. }