badaman escribió:Sería muy interesante si, en unas líneas generales, expusieras el funcionamiento de la rutina para la resolución de sudokus que creaste para el juego OSUSQ.
El procedimiento de resolución del sudoku en el juego usa la recursividad para su resolución y concretamente un algoritmo clásico llamado backtracking, que es básicamente un algoritmo recursivo pero con vuelta atrás para retomar otro "camino" diferente en caso de no encontrar una solución. Es un algoritmo de "fuerza bruta", es decir explora "a lo bestia" todas las posibilidades. No es un algoritmo muy óptimo pero funciona. (El que se implementa aquí creo que se podría optimizar intentando evitar comprobaciones innecesarias, aunque no sé si el coste final sería menor).
Por simplicidad he extraído el siguiente código del juego que genera la solución empleando dicho algoritmo recursivo. En este caso es el la FuNction Generar().
Esta función emplea tres parámetros, el primero es un array de 9x9 de enteros que contiene el planteamiento del sudoku a resolver (el valor 0 en una posición es un hueco vacío), valores <> 0 indican números del planteamiento del problema. Los dos parámetros siguientes son fila, columna donde empezará la búsqueda (1,1 en la primera llamada).
Lo que hace la función básicamente es empezar a rastrear la matriz y buscar un hueco (donde haya un valor 0). Luego intentar buscar en ese hueco el primer valor válido (de 1 a 9 cumpliendo las relgas del sudoku, esto es, que el valor no se repita en la fila, columna o sección). Aquí usa una rutina de apoyo que no está en este trozo de código por simplicidad, dicha función es obvia (ver código del juego para detalle de esas rutinas, ValidaNumero()).
A partir de este punto la función llega la sección crítica, si encuentra un valor válido avanza llamándose a si misma pero con la búsqueda de un nuevo hueco. Si no encuentra un valor válido en este punto (fila, columna) debe retroceder a la llamada anterior para intentarlo con el siguiente valor (de la llamada anterior), es decir "otro camino".
La condición de parada es que se llegue a la última posición del array (posición 9,9) y que en dicha posición se encuentre un valor válido. Entonces el sudoku tendrá solución, si no es así entonces NO habrá solución. Podría pasara también que el programa agotara todas las valores en todas las retroceda sin encontrar solución.
Bueno .... no sé si me he enrollado mucho, el extracto de código es el siguiente y como dice badaman es un buen ejemplo de la potencia de la recursividad:
Código: Seleccionar todo
3540 REMark ...
3610 :
3620 solucion% = Generar (sk%, 1, 1)
3630 :
3650 IF solucion% <> 0 THEN
3660 Mensaje "³³ EL SUDOKU TIENE SOLUCI–N !!", 1
3670 ELSE
3680 Mensaje "³³ JOOOPP EL SUDOKU NO TIENE SOLUCI–N !!", 1
3690 END IF
3700 :
3710 :
3740 REMark --- Funci–n recursiva (tipo backtracking) para solucionar el sudoku
3750 DEFine FuNction Generar(sk%, fil, col)
3760 LOCal num%: LOCal res%
3770 LOCal f, c
3780 LOCal sol%
3790 :
3800 REMark Avanzar hasta encontrar una posici–n libre
3810 REPeat BuscaHueco
3820 IF fil > 9 OR col> 9 THEN sol%=1: RETurn sol%
3830 IF sk%(fil,col) = 0 THEN
3840 EXIT BuscaHueco
3850 END IF
3860 col = col + 1
3870 IF col > 9 THEN
3880 col = 1
3890 fil = fil + 1
3900 END IF
3910 END REPeat BuscaHueco
3920 :
3930 sol% = 0
3940 num% = 0
3950 REMark Rastrear todos los n™meros del sudoku del 1 al 9
3960 REPeat BuscaNumero
3970 num% = num% + 1
3980 res% = ValidaNumero(sk%, num%, fil, col)
3990 REMark PRINT#0, num%;res%: INPUT#0, "> ";b$
4000 IF res% <> 0 THEN
4010 sk%(fil,col) = num%
4020 PintaCasilla num%, fil, col, 0
4030 f = fil
4040 c = col + 1
4050 IF c > 9 THEN
4060 f = f + 1
4070 c = 1
4080 END IF
4090 REMark Llamada recursiva si llega al final
4100 REMark estamos en la condici–n de parada
4110 IF f < 10 THEN
4120 sol% = Generar (sk%, f, c)
4130 ELSE
4140 sol% = 1
4150 END IF
4160 END IF
4170 IF sol% = 1 OR num% = 9 THEN
4180 EXIT BuscaNumero
4190 END IF
4200 END REPeat BuscaNumero
4210 :
4220 IF sol% = 0 THEN
4230 sk%(fil,col) = 0
4240 PintaCasilla 0, fil, col, 0
4250 END IF
4260 RETurn sol%
4270 END DEFine
4280 :
4290 :