su doku

Los juegos de lógica son un pasatiempo genial... hasta que los revientas y pierden la gracia.

Ya rompimos el juego de los palotes y ahora le ha llegado su turno al Su Doku, que seguramente conoceréis por su difusión en periódicos, revistas de pasatiempos, libros de crucigramas, reenvíos de correo electrónico y demás. Para los que sean nuevos a este rompecabezas, explicaré brevemente en qué consiste.

Se trata de un juego parecido a los de los cuadrados mágicos, en el que hay que rellenar un tablero de 9x9 casillas con números del 1 al 9, dados algunos valores preestablecidos, siguiendo las siguientes restricciones:

• No se puede repetir ningún número en la misma fila.
• No se puede repetir ningún número en la misma columna.
• No se puede repetir ningún número en el mismo subtablero de 3x3 en los que está dividido el tablero principal (3x3 subtableros a su vez).

A mí me introdujo mi colega El Cana, contándome por el messenger que estaba bastante viciado al juego y que pensaba escribir un programa para resolverlos cuando volviese de hacer footing. Al final le dio pereza (o se rajó... Cana, mariquita!!! :p) y no lo hizo.

Un par de meses después, en la típica comida familiar de los domingos, dos de mis tíos estaban enganchados a algún su doku y tenían problemillas (más de 15h seguidas con el mismo su doku delante empieza a ser un problema, sí... los que vayan a decirme que lo mismo con el Counter-Strike o el Diablo... hmmmmmm... pues que se vayan a la mierda xD). Yo, haciendo un alarde de pelotas de acero les dije que era capaz de hacer un programa que los resolviese, aunque dudaba del tiempo que le llevaría resolverlo... así a ojo, todas las posibles combinaciones para llenar un tablero de 9x9 con dígitos del 1 al 9 son 9^81, que es el colosal número: 196627050475552913618075908526912116283103450944214766927315415537966391196809.

Para que os hagáis una idea de semenjante magnitud, lo podemos comparar con la anécdota de llenar el tablero de ajedrez con granos de trigo, doblando en cada casilla el número de granos de la anterior (2^64): 18446744073709551616. Así que si alguien os propone que llenéis un tablero de su doku con granos de trigo, poniendo en cada casilla nueve veces más que en la anterior mandadle inmediatamente a tomar por culo.

Por lo tanto, quedaba descartada la fuerza brutísima (pero bruta, eh?) a no ser que tengamos un Deep Blue, un Blue Gene, un Earth Simulator, un Mare Nostrum y unas cuantas PlayStation 3 en casa. Ahora vamos a usar un poco nuestra materia gris (qué curioso, cuando era pequeño pensaba que la materia gris eran los músculos... es que nunca había visto un cerebro) para reducir el problema hasta un tamaño abordable por nuestras entrañables cafeteras.

Mientras miraba el tablero del su doku se me ocurrió que la forma elegante, chula y pofesioná de resolver esto era con Prolog, ya que sólo es cuestión de poner las restricciones en forma de cláusulas de Horn, en plan "si en la fila esta hay un 5, pues aquí ya no puede haberlo" y esas cosillas... pero como no lo tengo muy fresco eso del Prolog (es lo que pasa cuando tu compañero de prácticas se ventila la de Prolog en la sesión de presentación del I CUPCAM mientras se rasca los huevos con la mano que le sobra...) y parecía que el problema podía ser grandecito, pues me tiré al C (también para que se vea que soy un tío versátil, que no todo el Python y Bash en esta vida).

Aquí explico brevemente cómo tenía pensado solucionarlo:

1. Rellenar una matriz de 9x9 cuyo contenido son listas de los números posibles, dadas las restricciones iniciales (comprobar que no estén en la fila, la columna y el grupo 3x3).
2. Hacer un cacho de backtracking, empezando por la casilla 0,0 y terminando por la 8,8, pero en lugar de mirar todos los posibles números del 1 al 9, pues sólo de los que estén en la lista correspondiente a la casilla que se rellenó antes.

Con eso ya tardaba un tiempo inapreciable en resolverlo en mi ordenador (que tampoco es nada del otro mundo, un Athlon XP 1600+), así que no me puse a implementar las posibles mejoras, pero voy a comentarlas aquí:

1. Crear una lista de las casillas a rellenar, ordenarla de forma creciente según el número de posibles números a rellenar y hacer back-tracking con las casillas por ese orden (para que el árbol de back-tracking fuese lo menos ancho posible en las primeras ramas).
2. Actualizar en tiempo de ejecución las listas de posibles casillas, aunque esto quizá sería contraproducente (demasiado trabajo que habría que hacer y deshacer en cada invocación y vuelta) y podria crear conflictos a la hora de recorrer la lista de casillas si se reordena (lo típico de saltarte una, procesar la misma dos veces... esas cositas).
3. Eliminar al recursividad, simulándola con una pila de tuplas (n,i,j).
   

Así que sin más dilaciones, os pongo las 201 líneas de código en C que os harán los putos amos del su doku y frustrarán a vuestras amistades cuando vean que los resolvéis en... unos cuantos minutos, tampoco os flipéis y deis la solución al momento:

  1  typedef int bool;
  2  #define TRUE    1
  3  #define FALSE   0
  4
  5
  6  int tablero_orig[9][9];
  7  int tablero_busq[9][9];
  8
  9  int posibles[9][9][10];
 10
 11
 12  void leer_tablero();
 13  long long calcular_posibles();
 14  int calcular_posibles_casilla(int i, int j);
 15  bool comprobar_insertar(int n, int i, int j);
 16  bool resolver_recursivo(int i, int j);
 17  inline bool es_valido(int n, int i, int j);
 18  bool esta_en_fila(int n, int i);
 19  bool esta_en_columna(int n, int j);
 20  bool esta_en_cuadrante(int n, int i, int j);
 21  void print_posibilidades();
 22  void print_tablero();
 23  void leer_tablero();
 24
 25  /**
 26   * Rellena posibles para todas las casillas, y devuelve
 27   * el numero total de combinaciones posibles.
 28   */
 29  long long calcular_posibles() {
 30          int i, j;
 31          int m;
 32          long long n = 1;
 33          for (i = 0; i < 9; ++i) {
 34                  for (j = 0; j < 9; ++j) {
 35                          if (tablero_orig[i][j] == 0) {
 36                                  m = calcular_posibles_casilla(i, j);
 37                                  n *=m;
 38                          }
 39                  }
 40          }
 41          return n;
 42  }
 43
 44  /**
 45   * Rellena los valores de posibles[i][j], dejando un 0 tras
 46   * la ultima casilla rellena y devolviendo el número de
 47   * posibilidades;
 48   */
 49  int calcular_posibles_casilla(int i, int j) {
 50          int n;
 51          int k = 0;
 52          for (n = 1; n <= 9; ++n) {
 53                  if (es_valido(n, i, j)) {
 54                          posibles[i][j][k++] = n;
 55                  }
 56          }
 57          posibles[i][j][k] = 0;
 58          if (k == 0) {
 59                  k = 1;
 60          }
 61          return k;
 62  }
 63
 64  inline bool es_valido(int n, int i, int j) {
 65          return
 66                  !esta_en_fila(n,i) &&
 67                  !esta_en_columna(n,j) &amp;&
 68                  !esta_en_cuadrante(n, i/3, j/3);
 69  }
 70
 71  bool esta_en_fila(int n, int i) {
 72          int j;
 73          for (j = 0; j < 9; ++j) {
 74                  if (tablero_busq[i][j] == n) {
 75                          return TRUE;
 76                  }
 77          }
 78          return FALSE;
 79  }
 80
 81  bool esta_en_columna(int n, int j) {
 82          int i;
 83          for (i = 0; i < 9; ++i) {
 84                  if (tablero_busq[i][j] == n) {
 85                          return TRUE;
 86                  }
 87          }
 88          return FALSE;
 89  }
 90
 91
 92  /**
 93   * Indica si n esta en el cuadrante i, j, que son las coordenadas
 94   * del cuadrante (de 0 a 2), NO las coordenadas de una casilla
 95   * dentro del cuadrante.
 96   */
 97  bool esta_en_cuadrante(int n, int i, int j) {
 98          int k, l;
 99          int mk, ml;
100          mk = (i+1)*3;
101          ml = (j+1)*3;
102          for (k = i*3; k < mk; ++k) {
103                  for (l = j*3; l < ml; ++l) {
104                          if (tablero_busq[k][l] == n) {
105                                  return TRUE;
106                          }
107                  }
108          }
109          return FALSE;
110  }
111
112
113  bool resolver_recursivo(int i, int j) {
114          int n;
115          int k;
116          int si, sj;
117
118          si = i;
119          sj = j + 1;
120          if (sj == 9) {
121                  sj = 0;
122                  ++si;
123          }
124
125          if (tablero_orig[i][j]) {
126                  return resolver_recursivo(si, sj);
127          }
128
129          for (k = 0; n = posibles[i][j][k]; ++k) {
130                  if (es_valido(n,i,j)) {
131                          tablero_busq[i][j] = n;
132                          if (i == 8 && j == 8) {
133                                  return TRUE;
134                          }
135                          else if (resolver_recursivo(si, sj)) {
136                                  return TRUE;
137                          }
138                          tablero_busq[i][j] = 0;
139                  }
140          }
141          return FALSE;
142  }
143
144  void print_tablero(int t[9][9]) {
145          int i, j;
146          for (i = 0; i < 9; ++i) {
147                  for (j = 0; j < 9; ++j) {
148                          printf("%d ", t[i][j]);
149                          if (((j+1)%3) == 0) {
150                                  printf("  ");
151                          }
152                  }
153                  printf("\n");
154                  if ((i+1)%3 == 0) {
155                          printf("\n");
156                  }
157          }
158  }
159
160  void print_posibilidades() {
161          int i, j, k, n;
162          for (i = 0; i < 9; i++) {
163                  for (j = 0; j < 9; j++) {
164                          printf("(%d, %d) : ", i+1, j+1);
165                          for (k = 0; n = posibles[i][j][k]; k++) {
166                                  printf("%d ", n);
167                          }
168                          printf("\n");
169                  }
170          }
171  }
172
173  void leer_tableros() {
174          int i, j;
175          int n;
176          for (i = 0; i < 9; i++) {
177                  for (j = 0; j < 9; j++) {
178                          scanf(" %d ", &n);
179                          tablero_orig[i][j] = n;
180                          tablero_busq[i][j] = n;
181                  }
182          }
183  }
184
185  int main() {
186          long long n;
187          leer_tableros();
188          print_tablero(tablero_orig);
189          printf("analizando tablero...\n");
190          n = calcular_posibles();
191          print_posibilidades();
192          printf("%lld posibles combinaciones.\n", n);
193          printf("buscando solucion...\n");
194          if (resolver_recursivo(0,0)) {
195                  printf("solución encontrada!:\n");
196          }
197          else {
198                  printf("solución no encontrada :(\n");
199          }
200          print_tablero(tablero_busq);
201  }

(qué majo el vim, eh? que nos lo saca con colorines... si lo queréis compilar, acordaos de quitar los números de línea).

Si no os apetece hacer ingeniería inversa para saber cómo funciona, ya os lo cuento yo:
Lee por la entrada estándar 81 enteros. que pueden estar separados por blancos de cualquier forma (como si os da ponerlos todos en la misma línea). No he probado qué pasa si se meten menos números ó texto entre medias, supongo que casca, así que no hagáis mucho el cafre. En las casillas que estén en blanco debéis introducir ceros.

Aquí os pongo un ejemplo de cómo funciona el tema con un su doku de los jodidos:

[fortran@johnny sudoku]$ cat prueba.txt
0 1 0   0 0 8   0 0 6
0 0 0   0 0 0   0 0 3
0 0 0   0 7 5   4 0 0

0 0 2   0 0 4   0 8 0
0 4 6   0 0 0   7 9 0
0 5 0   9 0 0   1 0 0

0 0 5   3 6 0   0 0 0
8 0 0   0 0 0   0 0 0
9 0 0   8 0 0   0 5 0
[fortran@johnny sudoku]$ ./sudoku < prueba.txt
0 1 0   0 0 8   0 0 6
0 0 0   0 0 0   0 0 3
0 0 0   0 7 5   4 0 0

0 0 2   0 0 4   0 8 0
0 4 6   0 0 0   7 9 0
0 5 0   9 0 0   1 0 0

0 0 5   3 6 0   0 0 0
8 0 0   0 0 0   0 0 0
9 0 0   8 0 0   0 5 0

analizando tablero...
(1, 1) : 2 3 4 5 7
(1, 2) :
(1, 3) : 3 4 7 9
(1, 4) : 2 4
(1, 5) : 2 3 4 9
(1, 6) :
(1, 7) : 2 5 9
(1, 8) : 2 7
(1, 9) :
(2, 1) : 2 4 5 6 7
(2, 2) : 2 6 7 8 9
(2, 3) : 4 7 8 9
(2, 4) : 1 2 4 6
(2, 5) : 1 2 4 9
(2, 6) : 1 2 6 9
(2, 7) : 2 5 8 9
(2, 8) : 1 2 7
(2, 9) :
(3, 1) : 2 3 6
(3, 2) : 2 3 6 8 9
(3, 3) : 3 8 9
(3, 4) : 1 2 6
(3, 5) :
(3, 6) :
(3, 7) :
(3, 8) : 1 2
(3, 9) : 1 2 8 9
(4, 1) : 1 3 7
(4, 2) : 3 7 9
(4, 3) :
(4, 4) : 1 5 6 7
(4, 5) : 1 3 5
(4, 6) :
(4, 7) : 3 5 6
(4, 8) :
(4, 9) : 5
(5, 1) : 1 3
(5, 2) :
(5, 3) :
(5, 4) : 1 2 5
(5, 5) : 1 2 3 5 8
(5, 6) : 1 2 3
(5, 7) :
(5, 8) :
(5, 9) : 2 5
(6, 1) : 3 7
(6, 2) :
(6, 3) : 3 7 8
(6, 4) :
(6, 5) : 2 3 8
(6, 6) : 2 3 6 7
(6, 7) :
(6, 8) : 2 3 4 6
(6, 9) : 2 4
(7, 1) : 1 2 4 7
(7, 2) : 2 7
(7, 3) :
(7, 4) :
(7, 5) :
(7, 6) : 1 2 7 9
(7, 7) : 2 8 9
(7, 8) : 1 2 4 7
(7, 9) : 1 2 4 7 8 9
(8, 1) :
(8, 2) : 2 3 6 7
(8, 3) : 1 3 4 7
(8, 4) : 1 2 4 5 7
(8, 5) : 1 2 4 5 9
(8, 6) : 1 2 7 9
(8, 7) : 2 3 6 9
(8, 8) : 1 2 3 4 6 7
(8, 9) : 1 2 4 7 9
(9, 1) :
(9, 2) : 2 3 6 7
(9, 3) : 1 3 4 7
(9, 4) :
(9, 5) : 1 2 4
(9, 6) : 1 2 7
(9, 7) : 2 3 6
(9, 8) :
(9, 9) : 1 2 4 7
-6363586273474510848 posibles combinaciones.
buscando solucion...
solución encontrada!:
4 1 9   2 3 8   5 7 6
5 2 7   4 9 6   8 1 3
6 8 3   1 7 5   4 2 9

7 9 2   6 1 4   3 8 5
1 4 6   5 8 3   7 9 2
3 5 8   9 2 7   1 6 4

2 7 5   3 6 1   9 4 8
8 6 4   7 5 9   2 3 1
9 3 1   8 4 2   6 5 7
[fortran@johnny sudoku]$

Fijaos que el número de posibilidades "a priori" es lo suficientemente grande como para desbordar un "long long int" en una máquina de 32 bit. Si queréis saber cuánto es exactamente, en la función "calcular_posibilidades()" podéis ir imprimiendo los valores de "m" separados por asteriscos y luego lo pegáis en algún intérprete de python, ruby o una hoja de cálculo para que os diga el resultado.

Hale, como siempre, se admiten mejoras, sugerencias, quejas, reclamaciones porque te ha petado el ordenador... por cierto, sería interesante que alguien propusiese una versión en Prolog ;-)