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:
- 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).
- 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í:
- 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).
- 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).
- 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) &&
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 ;-)
