domingo, septiembre 25, 2005

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 ;-)

17 comentarios:

fortran dijo...

He añadido una modificación que consiste mientras se van calculando las posibilidades, en las que sólo hay una opción se añade a la configuración original, y se repite el proceso hasta que no queden casillas para las que sólo haya una opción. Los sudokus fáciles se resuelven ahora de forma directa, sin necesidad de backtracking, mientras que los más difíciles apenas mejoran... si a alguien le interesa el código, que lo pida y lo pongo :-)

fortran dijo...

Estoy jodido, tremendamente jodido, hermano... el cabronazo del Granadino me ha pasado un puto contraejemplo en el que el resolvedor de sudokus no funciona :'( y yo que pensaba que con 3 ejemplos valía y sobraba... en fin... que me estoy devanando los sesos, así que a ver si es cierto eso que dicen en lo de la Catedral y el Bazar (sobre el Bazar), que si miles de ojos miran un código, es fácil que por lo menos a uno el error le resulte evidente (vale, aquí no somos miles, pero creo que sí que hay ojos muy capaces).

El ejemplo que petó fue este:

8 0 0 1 0 0 3 0 6
0 6 0 0 8 0 7 5 0
7 5 0 0 0 9 0 0 0

0 0 6 9 0 2 0 0 5
0 1 0 0 0 0 0 6 0
9 0 0 5 0 4 1 0 0

0 0 0 7 0 0 0 9 3
0 8 9 0 2 0 0 7 0
5 0 7 0 0 8 0 0 1

Probé con la segunda versión, y ahí no fallaba, pero me di cuenta de que era porque encontraba una única solucción por reducción de posibilidades, sin necesidad de hacer backtracking. Así que decidí hacer otras pruebas...

Veamos este sudoku que sí se resuelve bien en las dos versiones y que sí necesita backtracking:

0 0 0 0 0 0 0 0 8
0 0 3 9 7 0 0 0 0
6 0 0 0 3 0 0 2 0

8 0 0 2 0 0 0 7 0
0 7 9 0 0 0 2 4 0
0 1 0 0 0 7 0 0 9

0 6 0 0 5 0 0 0 4
0 0 0 0 0 2 9 0 0
5 0 0 0 0 0 0 0 0

¿Cuál era la diferencia trascendental entre esos dos sudokus? Después de mirar un par de sudokus más que sí funcionaban y el que no, vi que en los que funcionaba, el primer el elemento siempre era cero... no había ninguno de mis casos de prueba que tuviese en la primera casilla un número fijo.


Decidí hacer un pequeño experimento bastante revelador, probar con el mismo sudoku, pero rotado 90º:

8 0 0 0 0 9 4 0 0
0 0 2 7 4 0 0 0 0
0 0 0 0 2 0 0 9 0

0 0 0 0 0 7 0 2 0
0 7 3 0 0 0 5 0 0
0 9 0 2 0 0 0 0 0

0 3 0 0 9 0 0 0 0
0 0 0 0 7 1 6 0 0
0 0 6 8 0 0 0 0 5

¿Encontró la solución? Nope. Así que parecía que ahí estaba el problema... ahora bien, sabiendo cuál es la causa de que falle, miro mi código no veo el por qué. Lo cuál me deja bastante jodido y herido en mi orgullo de chapucillas... me siento como un Minglanillas :-S

Seguramente mañana lo vea con más claridad. Aunque no nos engañemos, todavía me queda un rato de seguir mirando absorto estas putas líneas de código intentando encontrar el fallo...

fortran dijo...

Mierda! seré gilipollas! he estado jodidamente ciego! el problema no era en el primer elemento... sino en el último!!! Claro! la condición para que devuelva TRUE sólo funciona si la última posición es libre y tiene que hacer backtracking... nada, nada, metemos un if más y está solucionado... ufff, por lo menos no me ha hecho falta tirarme toda la noche jodido y sin dormir pensando en la puta mierda de los sudokus! :-D

Conclusión: mejor la explico con una cita de Los Simpson
- ¿Ves esta piedra, papá? Ahuyenta a los tigres...
- ¿En serio?
- ¿Ves algún tigre por aquí?
- ¡Te la compro, Lisa!

No sé si el diálogo era exactamente así, pero la conclusión es que aunque todas las observaciones hasta el momento se ajusten a tu hipótesis, esto no la hace verdadera... Cualquier científico sabe esto, pero parece que a los informáticos se nos olvida muy a menudo... si hubiésemos prestado más atención en clase de filosofía cuando nos hablaban de Karl Popper (hey, si se apellida igual que la droga que usan los gays para dilatarse el ojal!) otro gallo nos cantaría...

Un bis de la conclusión: cada vez tengo más claro que tengo que estudiar una carrera de ciencias de verdad ó una ingeniería más seria...

Raúl dijo...

Lo de los Simpsons es como aquello de:

- "Papá papá, ¿qué está más cerca, la Luna o Zaragoza?"
- "Pues la Luna hijo, ¿¿¿ o es que tú ves Zaragoza desde aquí ???"

Buen trabajo lo del sudoku Fortran. Un minglanillas habría usado el patrón Abstract Factory siguiendo el consejo del asistente de cesharp dotnet, y no seria capaz de resolver en problema en ~200 líneas.

Saludetes

Pesso dijo...

Segun mis fuentes infiltradas en la UCM, el examen de septiembre en no se que asignatura era, justamente, programar un algoritmo con backtracking para solucionar sudokus. Por tanto, Fortran, si te ha llevado más de tres horas seria un suspensillo. Esto me da que pensar, ¿Nos ha amariconado nuestra Universidad? ¿Hacen falta más Javis para mantenernos en forma? Inquietante. Por lo menos sabemos que los que vienen detras nuestra son aun más blandos.

fortran dijo...

No, no me ha llevado más de 3 horas, estimo que fue un tiempo entre 30 y 45 minutos.

Aunque sí que es cierto que la versión que hice en media hora era la que tenía el fallo en la condición de finalización (peta cuando la casilla [9,9] está prefijada). Corregirlo era tan fácil como quitar todos los "return TRUE" que hay en resolver_recursivo y poner al comiezo del un:

if (i == 8 && j == 10) {
return TRUE;
}

y así quedaría un poco más bonito y encima funcionando bien. De todos modos cuando saque la versión 2.0 os vais a cagar! XD

Está previsto que ésta además de resolver Sudokus también los genere...
reutilizando el algoritmo de resolución (para vago yo): sólo tienes que decirle que resuelva un sudoku en blanco y antes haber inicializado la matriz "posibilidades" con todos los números del 1 al 9, pero desordenados de forma aleatoria, para que cada vez genere un sudoku distinto. Luego está el tema de empezar a quitar casillas y que la solución siga siendo única, lo cuál o se hace a lo bruto por ensayo y error, ó se piensa una solución mejor y formalmente más correcta.

el sucio dijo...

No comparto tú opinión Pesso. Cometes el error de generalizar, mal mal mal. Uno por uno y cubata mediante (Fortran TM) es como se harían esas comparaciones sobre el nivel universitario, y el resultado me importa bien poco. Ha habido gente mejor que yo en el pasado (esto es obvio) y habrá gente mejor que yo en el futuro (esto también es obvio), y a pesar de ello ya he oído varias veces lo que dices de "somos peores que en el pasado pero mejores que en el futuro". Un poco derrotista para mi gusto.

Sobre lo del examen, pues me parece un ejercicio bastante lógico. Además, probablemente todo el mundo lo resolvió con backtracking a saco y algunos con backtracking podando opciones como ha hecho Fortran. Esa solución está muy bien, pero ciertamente no incorpora nada brillante, como podría ser el uso de alguna cojo-heurística. De hecho, todos los que hemos visto el programa lo hemos entendido y al menos a mi me ha gustado.

A favor de Fortran: ¿cuántos estudiantes de la UCM están en su casa y de repente se ponen a pensar en un algoritmo para resolver sudokus, y además lo implementan?. Probablemente no todos los que son capaces de hacerlo.

Pero bueno, que estamos en lo de siempre, uno a uno y cubata mediante es como se resuelven los duelos.

fortran dijo...

Coño, Sucio, es de lo más bonito que me han dicho nunca, si es que me he emocionado... snif, snif... :'(

En lo de los cubata parece que te me has adelantado... no sería la primera vez xD bueno, ya lo veréis en el próximo post. Por cierto, el código arrefinitivo del resolvedor (¿o resolutor?) de sudokus lo dejo por aquí:

---------------------------

#include <stdio.h>

typedef int boolean;
#define TRUE 1
#define FALSE 0

int tablero_orig[9][9];//guarda los numeros prefijados (0 son libres)
int tablero_busq[9][9];//se usa para ir resolviendo el puzle
int posibles[9][9][10];//contiene los posibles valores que puede tener una celda

#define es_valido(n,i,j) (!esta_en_fila (n, i) && !esta_en_columna (n, j) && !esta_en_cuadrante (n, i / 3, j / 3))

boolean esta_en_fila (int n, int i) {
int j;

for (j = 0; j < 9; ++j) {
if (tablero_busq[i][j] == n) {
return TRUE;
}
}
return FALSE;
}

boolean esta_en_columna (int n, int j) {
int i;

for (i = 0; i < 9; ++i) {
if (tablero_busq[i][j] == n) {
return TRUE;
}
}
return FALSE;
}

/**
* Indica si n esta en el cuadrante i, j, que son las coordenadas
* del cuadrante (de 0 a 2), NO las coordenadas de una casilla
* dentro del cuadrante.
*/
boolean esta_en_cuadrante (int n, int i, int j) {
int k, l;
int mk, ml;

mk = (i + 1) * 3;
ml = (j + 1) * 3;
for (k = i * 3; k < mk; ++k) {
for (l = j * 3; l < ml; ++l) {
if (tablero_busq[k][l] == n) {
return TRUE;
}
}
}
return FALSE;
}

/**
* Rellena los valores de posibles[i][j], dejando un 0 tras
* la ultima casilla rellena y devolviendo el numero de
* posibilidades;
*/
int calcular_posibles_casilla (int i, int j) {
int n;
int k = 0;

for (n = 1; n <= 9; ++n) {
if (es_valido (n, i, j)) {
posibles[i][j][k++] = n;
}
}
posibles[i][j][k] = 0;
if (k == 0) {
k = 1;
}
return k;
}

void print_tablero (int t[9][9]) {
int i, j;

for (i = 0; i < 9; ++i) {
for (j = 0; j < 9; ++j) {
printf ("%d ", t[i][j]);
if (((j + 1) % 3) == 0) {
printf (" ");
}
}
printf ("\n");
if ((i + 1) % 3 == 0) {
printf ("\n");
}
}
}

/**
* Rellena posibles para todas las casillas, y devuelve
* el numero total de combinaciones posibles.
*/
long long calcular_posibles () {
int i, j;
int m, p;
boolean seguir = TRUE;
long long n = 1;

//mientras queden casillas con una sola posibilidad
while (seguir) {
seguir = FALSE;
n = 1;
for (i = 0; i < 9; ++i) {
for (j = 0; j < 9; ++j) {
if (tablero_orig[i][j] == 0) {
m = calcular_posibles_casilla (i, j);
//si solo hay una opcion la cableamos
if (m == 1) {
seguir = TRUE;
p = posibles[i][j][0];
tablero_orig[i][j] = p;
tablero_busq[i][j] = p;
posibles[i][j][0] = 0;
}
n *= m;
}
}
}
if (seguir) {
printf ("ajustando algunos valores\n");
print_tablero (tablero_orig);
}
}
return n;
}

boolean resolver_recursivo (int i, int j) {
int n;
int k;
int si, sj;

//si hemos terminado el tablero
if (i == 9 && j == 0) {
return TRUE;
}

//calculamos la siguiente celda
si = i;
sj = j + 1;
if (sj == 9) {
sj = 0;
++si;
}

if (tablero_orig[i][j]) {
return resolver_recursivo (si, sj);
}
for (k = 0; (n = posibles[i][j][k]); ++k) {
if (es_valido (n, i, j)) {
tablero_busq[i][j] = n;
if (resolver_recursivo (si, sj)) {
return TRUE;
}
tablero_busq[i][j] = 0;
}
}
return FALSE;
}

void print_posibilidades () {
int i, j, k, n;

for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
printf ("(%d, %d) : ", i + 1, j + 1);
for (k = 0; (n = posibles[i][j][k]); k++) {
printf ("%d ", n);
}
printf ("\n");
}
}
}

void leer_tableros () {
int i, j;
int n;

for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
scanf (" %d ", &n);
tablero_orig[i][j] = n;
tablero_busq[i][j] = n;
}
}
}

int main () {
long long n;

leer_tableros ();
print_tablero (tablero_orig);
printf ("analizando tablero...\n");
n = calcular_posibles ();
print_posibilidades ();
printf ("%lld posibles combinaciones.\n", n);
printf ("buscando solucion...\n");
if (resolver_recursivo (0, 0)) {
printf ("solucion encontrada!:\n");
} else {
printf ("solucion no encontrada :(\n");
}
print_tablero (tablero_busq);
return 0;
}



---------------------------

Siento que esté mal tabulado, esto no deja poner tags "pre". Si eso luego le dais caña al indent...

Prostibulero dijo...

Vamos a lo realmente importante:

¿Cuál es tu ritmo pajeril estival?

Esa encuesta está desfasada. Ya sabes lo que te toca, Frotran.

Anónimo dijo...

Para:
7 9 6 8 5 3 4 2 1
5 1 3 4 9 2 8 7 6
2 4 8 1 6 7 5 3 9
6 3 1 5 2 4 9 8 7
9 2 7 3 1 8 6 5 8
8 5 4 9 7 6 3 1 2
1 8 9 2 4 5 7 6 3
4 6 5 7 3 1 2 9 0
3 7 2 6 8 9 1 4 5

que es un tablero erróneo, porque la casilla 5,9 es un 8 y debería ser un 4, entra en un bucle infinito.

Anónimo dijo...

Simplemente com poner:

if(i==8 && j==8)notdone = false;

antes de

n*=m;

en calcular_posibles se arregla.

Anónimo dijo...

Una optimización de las fáciles sería ahorrando iteraciones en calcularposibles saliendo del bucle controlado por seguir con un goto cada vez que "cablees" una solución.
En plan

bucle:
while(seguir)
{
blablablá
if(posibles para 1 casilla son sólo 1)
{
blablablá
seguir = true;
goto bucle;
}
}

Anónimo dijo...

AQUÍ NI GOTOS NI HOSTIAS!

Anónimo dijo...

Joder macho,que es un goto de los buenos, como un break con etiqueta en java...

Ingeniero dijo...

Tengo un problema con esto de los sudokus, haber si alguien me lo puede resolver, el caso es que en un examen del año pasao en la politecnica Carlos 3 pusieron un examen, no que resolviese sudokus, sino que los comprobase, una vez echos, si eran correctos, en FORTRAN. El caso esque estoy en primer año de carrera y como que no me entero exactamente de lo que hacen en este porgrama, sobretodo, la parte de subprogramas, no se exactamente para que sirve el vector "esta". Alguien me lo puede explicar¿¿, aqui va el programa:

PROGRAM ComprobarSudoku
!Examen Feb 2006
!Escribir un programa en Fortran que compruebe si una solución dada a un Sudoku es
correcta.
!Normas generales:
!1. Un tablero sudoku se compone de 81 casillas, 9 filas por 9 columnas. A su vez el
tablero se subdivide en 9 subcuadrados de 9 casillas cada uno (3x3) NO SUPERPUESTOS
(un numero en una posición NO puede pertenecer a dos subcuadros).
!2. Se debe cumplimentar todas las casillas con un número comprendido entre el 1 y el
9.
!3. No puede repetirse ninguna cifra en la misma fila, ni en la misma columna ni en el
mismo subcuadrado.
IMPLICIT NONE
INTEGER :: sudoku(9,9)
INTEGER:: f,c,kf,kc
LOGICAL ::incorrecto
LOGICAL, EXTERNAL:: FCorrectoFila, FCorrectoColumna,FCorrectoSubcuadrado
!-----suponemos el sudoku precargado en memoria, aquí se genera aleatoriamente
Do f=1,9
Do c=1,9
sudoku(f,c)=f
End Do
End Do
!-----comprobamos que en todas las casillas hay un numero entre el 1 y el 9
incorrecto=.false.
f=1
c=1
Do while ((f<=9) .and. (incorrecto==.false.))
Do while ((c<=9) .and. (incorrecto==.false.))
select case (sudoku(f,c))
case (1,2,3,4,5,6,7,8,9)
incorrecto=.false.
case default
incorrecto=.true.
end select
c=c+1
End Do
f=f+1
End Do
f=1
Do while ((incorrecto==.false.) .and. (f<=9))
incorrecto=.not. (FCorrectoFila(f,sudoku))
f=f+1
End do
c=1
Do while ((incorrecto==.false.) .and. (c<=9))
incorrecto=.not. (FCorrectoColumna(c,sudoku))
c=c+1
End do
kf=1
kc=1
Do while ((incorrecto==.false.) .and. (kf<=7))
Do while ((incorrecto==.false.) .and. (kc<=7))
incorrecto=.not. (FCorrectoSubcuadrado(kf,kc,sudoku))
!Cada subcuadrado se identifica por los indices de su esquina
! superior izda kf,kc
kf=kf+3
End do
kc=kc+3
End Do
If (incorrecto) then
Print *, 'el sudoku no es correcto'
Else
Print *, 'el sudoku SI es correcto'
End IF
END PROGRAM ComprobarSudoku
!Funciones y subrutinas
LOGICAL FUNCTION FCorrectoFila(fila,s)
Integer::s(9,9),esta(9)
Integer::fila,i
Logical:: hay_un_cero
esta=(/0,0,0,0,0,0,0,0,0/)
!uso el vector está, para comprobar si un determinado digito está en la fila
!cuando encuentro un digito pongo esa posicion del vector a 1
Do i=1,9
esta(s(fila,i))=1
End do
!reviso el vector esta para ver si es todo unos
hay_un_cero = .false.
i=1
Do while ((hay_un_cero==.false.) .and. (i<=9))
If (esta(i)==0) then
hay_un_cero = .true.
End if
i=i+1
End Do
FCorrectoFila=.not. (hay_un_cero)
END FUNCTION FCorrectoFila
LOGICAL FUNCTION FCorrectoColumna(col,s)
Integer::s(9,9),esta(9)
Integer::col,i
Logical:: hay_un_cero
esta=(/0,0,0,0,0,0,0,0,0/)
!uso el vector esta, para comprobar si un determinado digito está en la fila
!cuando encuentro un digito pongo esa posicion del vector a 1
Do i=1,9
esta(s(i,col))=1
End do
!reviso el vector esta para ver si es todo unos
hay_un_cero = .false.
i=1
Do while ((hay_un_cero==.false.) .and. (i<=9))
If (esta(i)==0) then
hay_un_cero = .true.
End if
i=i+1
End Do
FCorrectoColumna=.not.(hay_un_cero)
END FUNCTION FCorrectoColumna
LOGICAL FUNCTION FCorrectoSubcuadrado(f_sub,c_sub,s)
Integer::s(9,9),esta(9)
Integer::f_sub,c_sub,i,j
Logical:: hay_un_cero
esta=(/0,0,0,0,0,0,0,0,0/)
!uso el vector esta, para comprobar si un determinado digito está en el
subcuadrado
!cuando encuentro un digito pongo esa posicion del vector a 1
Do i=0,T_SUB-1
Do j=0,T_SUB-1
!cada subcuadrado se identifica por los indices de su esquina
¡superior izquerda f_sub. c_sub
esta(s(f_sub+i,c_sub+j))=1
End Do
End do
!reviso el vector esta para ver si es todo unos
hay_un_cero = .false.
i=1
Do while ((hay_un_cero==.false.) .and. (i<=9))
If (esta(i)==0) then
hay_un_cero = .true.
End if
i=i+1
End Do
FCorrectoSubcuadrado=.not.(hay_un_cero)
END FUNCTION FCorrectoSubcuadrado

Ingeniero dijo...

Tengo un problema con esto de los sudokus, haber si alguien me lo puede resolver, el caso es que en un examen del año pasao en la politecnica Carlos 3 pusieron un examen, no que resolviese sudokus, sino que los comprobase, una vez echos, si eran correctos, en FORTRAN. El caso esque estoy en primer año de carrera y como que no me entero exactamente de lo que hacen en este porgrama, sobretodo, la parte de subprogramas, no se exactamente para que sirve el vector "esta". Alguien me lo puede explicar¿¿, aqui va el programa:

PROGRAM ComprobarSudoku
!Examen Feb 2006
!Escribir un programa en Fortran que compruebe si una solución dada a un Sudoku es
correcta.
!Normas generales:
!1. Un tablero sudoku se compone de 81 casillas, 9 filas por 9 columnas. A su vez el
tablero se subdivide en 9 subcuadrados de 9 casillas cada uno (3x3) NO SUPERPUESTOS
(un numero en una posición NO puede pertenecer a dos subcuadros).
!2. Se debe cumplimentar todas las casillas con un número comprendido entre el 1 y el
9.
!3. No puede repetirse ninguna cifra en la misma fila, ni en la misma columna ni en el
mismo subcuadrado.
IMPLICIT NONE
INTEGER :: sudoku(9,9)
INTEGER:: f,c,kf,kc
LOGICAL ::incorrecto
LOGICAL, EXTERNAL:: FCorrectoFila, FCorrectoColumna,FCorrectoSubcuadrado
!-----suponemos el sudoku precargado en memoria, aquí se genera aleatoriamente
Do f=1,9
Do c=1,9
sudoku(f,c)=f
End Do
End Do
!-----comprobamos que en todas las casillas hay un numero entre el 1 y el 9
incorrecto=.false.
f=1
c=1
Do while ((f<=9) .and. (incorrecto==.false.))
Do while ((c<=9) .and. (incorrecto==.false.))
select case (sudoku(f,c))
case (1,2,3,4,5,6,7,8,9)
incorrecto=.false.
case default
incorrecto=.true.
end select
c=c+1
End Do
f=f+1
End Do
f=1
Do while ((incorrecto==.false.) .and. (f<=9))
incorrecto=.not. (FCorrectoFila(f,sudoku))
f=f+1
End do
c=1
Do while ((incorrecto==.false.) .and. (c<=9))
incorrecto=.not. (FCorrectoColumna(c,sudoku))
c=c+1
End do
kf=1
kc=1
Do while ((incorrecto==.false.) .and. (kf<=7))
Do while ((incorrecto==.false.) .and. (kc<=7))
incorrecto=.not. (FCorrectoSubcuadrado(kf,kc,sudoku))
!Cada subcuadrado se identifica por los indices de su esquina
! superior izda kf,kc
kf=kf+3
End do
kc=kc+3
End Do
If (incorrecto) then
Print *, 'el sudoku no es correcto'
Else
Print *, 'el sudoku SI es correcto'
End IF
END PROGRAM ComprobarSudoku
!Funciones y subrutinas
LOGICAL FUNCTION FCorrectoFila(fila,s)
Integer::s(9,9),esta(9)
Integer::fila,i
Logical:: hay_un_cero
esta=(/0,0,0,0,0,0,0,0,0/)
!uso el vector está, para comprobar si un determinado digito está en la fila
!cuando encuentro un digito pongo esa posicion del vector a 1
Do i=1,9
esta(s(fila,i))=1
End do
!reviso el vector esta para ver si es todo unos
hay_un_cero = .false.
i=1
Do while ((hay_un_cero==.false.) .and. (i<=9))
If (esta(i)==0) then
hay_un_cero = .true.
End if
i=i+1
End Do
FCorrectoFila=.not. (hay_un_cero)
END FUNCTION FCorrectoFila
LOGICAL FUNCTION FCorrectoColumna(col,s)
Integer::s(9,9),esta(9)
Integer::col,i
Logical:: hay_un_cero
esta=(/0,0,0,0,0,0,0,0,0/)
!uso el vector esta, para comprobar si un determinado digito está en la fila
!cuando encuentro un digito pongo esa posicion del vector a 1
Do i=1,9
esta(s(i,col))=1
End do
!reviso el vector esta para ver si es todo unos
hay_un_cero = .false.
i=1
Do while ((hay_un_cero==.false.) .and. (i<=9))
If (esta(i)==0) then
hay_un_cero = .true.
End if
i=i+1
End Do
FCorrectoColumna=.not.(hay_un_cero)
END FUNCTION FCorrectoColumna
LOGICAL FUNCTION FCorrectoSubcuadrado(f_sub,c_sub,s)
Integer::s(9,9),esta(9)
Integer::f_sub,c_sub,i,j
Logical:: hay_un_cero
esta=(/0,0,0,0,0,0,0,0,0/)
!uso el vector esta, para comprobar si un determinado digito está en el
subcuadrado
!cuando encuentro un digito pongo esa posicion del vector a 1
Do i=0,T_SUB-1
Do j=0,T_SUB-1
!cada subcuadrado se identifica por los indices de su esquina
¡superior izquerda f_sub. c_sub
esta(s(f_sub+i,c_sub+j))=1
End Do
End do
!reviso el vector esta para ver si es todo unos
hay_un_cero = .false.
i=1
Do while ((hay_un_cero==.false.) .and. (i<=9))
If (esta(i)==0) then
hay_un_cero = .true.
End if
i=i+1
End Do
FCorrectoSubcuadrado=.not.(hay_un_cero)
END FUNCTION FCorrectoSubcuadrado

Anónimo dijo...

Tú no eres ingeniero, tú eres tonto.