Inteligencia Artificial del Juego SUDOKU SAMURAI

LP1 - UC 1

Sudoku2TXT Pro R©Colman, Alberto Denis Ramırez, Pedro Daniel

Resumen—Implementacion en lenguaje C de un algoritmo debusqueda de solucion del juego de estrategia Sudoku Samurai.

I. INTRODUCCION

Es un pasatiempo japones que aparecio a mediados de losanos 80 en los diarios nipones y que en el ano 2005 hastaesta epoca ha arrasado en los del resto del mundo. El jugadortiene una matriz de nueve filas por nueve columnas de lascuales algunas celdas tienen numeros y el resto huecos. Setienen que rellenar los huecos de manera que en cada fila ycolumna aparezcan los numeros de uno al nueve sin repetirse.Ası de simple y ası de complicado. Nosotros vamos a ver, ya implementar, un algoritmo bastante famoso: el Backtrackingo Vuelta Atras(haremos uso del nombre en ingles por ser elde mas uso) para solucionar Sudokus.

De alguna forma el Sudoku se basa en la busqueda de lacombinacion numerica perfecta. Hay diferentes niveles de difi-cultad y la resolucion del problema requiere paciencia y ciertasdotes logicas. Profesores de todo el mundo lo recomiendancomo metodo para desarrollar el razonamiento logico.

II. ANALISIS DEL PROBLEMA

Observe la Figura I de la tabla de 3∗3 mostrado, imagıneseque se dispone de 9 numeros(valores validos en el juego) yque solo uno puede estar en cada uno de la casilla, por lotanto en el primer tanteo todos los numeros son validos en laprimera casilla es decir n = 9, la segunda vez solo son ocholas posibles posiciones como tambien de numeros por lo tanton = 8.

Cuadro IBLOQUE DE UN SUDOKU

Matematicamente esto se conoce como que la sucesion seda en forma de factorial y como se buscan todas las posibil-idades considerando el orden es una permutacion, en sıntesistodas las posibilidades de “llenar” las casillas de todas lasmaneras es nPn = n!, que para el caso es 9! = 362800, queindican todas las soluciones posibles; para que este analisis?,como importa el orden al buscar el llenado del sudoku quedaclaro es que se necesitan muchos procesos para encontrar unasolucion valida si el metodo de enfrentar es el de prueba yerror, ademas es un concepto que nos servira mas adelante.

Colman, Alberto estudiante del Departmento de Electronica e Informatica,Universidad Catolica “Nuestra Senora de la Asuncion”, Asuncion, Paraguay,e-mail: [email protected].

Ramırez, Pedro estudiante del Departmento de Electronica e Informatica,Universidad Catolica “Nuestra Senora de la Asuncion”, Asuncion, Paraguay,e-mail: [email protected].

III. SOLUCION PROPUESTA, BACKTRACKING IMPLICARECURSIVIDAD

Se trata de un algoritmo de busqueda en el cual se exploraun arbol de soluciones en anchura o profundidad. Dicho deesta manera queda muy tecnico ası que mejor vemos devuelta un mini− sudoku. Digamos que tenemos el siguienteproblema: se nos presenta un cuadro como el de la FiguraII , tres filas por tres columnas, donde algunas de ellas estanocupadas pero otras no.

12

3

Cuadro IIBLOQUE DE UN SUDOKU SEMI COMPLETO

En cada hueco solo podemos poner un numero comprendidoentre el 1 y el 9 de tal manera que en cada fila y en cadacolumna solo aparezca cada uno de estos numeros una vez. Portanto es imposible encontrar una fila que muestre un (1,3,3)o un (2,1,1). A Donde esta el juego? en hallar los numerosque hay que poner en cada hueco de forma consecutiva detal manera que se verifique que cada numero es unico en sufila y su columna. Como podrıamos elaborar un programa queresuelva este puzzle?

Existen varias opciones, pero nos centraremos en la quequeremos ver. Comenzaremos centrandonos en los huecos, portanto debemos ignorar las celdas que estan ocupadas. Para cadahueco tenemos que elegir un numero que no se encuentre nien su fila ni en su columna. Vamos a necesitar, por tanto, unafuncion que escanee ambas en busca de numeros no usados.

Seleccionaremos uno de los posibles numeros y avanzare-mos hacia la derecha rellenando los huecos hasta llegar alultimo. De entre los metodos de resolucion algorıtmica deproblemas el metodo de vuelta atras o de backtrackingse caracteriza por plantear el mismo problema pero con lamuestra de menor tamano, por lo tanto, en forma recursiva.Muchos problemas de juegos de tablero se resuelven mediantebacktracking como en este caso.

IV. CONSIDERACIONES INICIALES

Usaremos un tablero de 21 ∗ 21 e ignoraremos mediantecondicionales las celdas que no intervienen en el tablero delsudoku, ademas observando la Figura 1 se nota que el tablerode 9 ∗ 9 central comparte cada uno de sus bloques de aristascon los cuatro sudokus restantes, por lo tanto es el que tienemayor peso en la busqueda de la solucion.

Es decir, para minimizar el tiempo de busqueda primerobuscaremos la solucion del tablero central, una vez encontrado,

LP1 - UC 2

Extreme Sudoku by Sudoku2pdf Pro

Sudoku #1

1

7

5 2 3

7

7

4

8

2 5

6

4

9 1

1 9

2

5

9

3

2

8 8

5

6

3

2

7 9 5

3

1

8

3

4 7

4

8

1 8

3

9 5

6

7

5 2

8

1

3 9

8

9 9

3

5

2

2

7 4 3

8

7

6

7

7

3 2

2

8

4

9 1 4

5

9 3 2 3

2

6

1

8 4

9 7

1

9

7 3

3

8 5

1

8

5 3

8

9

2

2

5

6

6

6

4

9 1 8 3 1

6 8 9

4 8

6

2

4 9 www.sudoku9981.com

Figura 1. Planteamiento de un sudoku samurai

se verificara si cada uno de los tableros de 9∗9 de los extremostiene solucion, en caso de ser ası esto serıa la solucion alsudoku, no es tan facil como suena, pues de acuerdo a lacomplejidad del sudoku planteado, habra casos donde hay queagotar todas las soluciones posibles del sub-tablero central,que implica? mayor tiempo de ejecucion, mayor consumode recursos y considerando que la pila stack de recursividadpodrıa desbordarse por sobrecarga(overhead).

Esta consideracion la hicimos para dividir el “trabajo”,una funcion se dedica exclusivamente a encontrar soluciondel sub-tablero central con las condiciones que implica alpertenecer tambien a las demas en sus vertices, una vezencontrado una de las tantas soluciones que seguro tendra, sepasa la matriz modificada a la misma funcion1 que vera si loscuatro restantes sub-tableros de los extremos tienen solucion(almismo tiempo), para cada sub-tablero central encontrado, deser ası es una solucion2, en caso de no ser, regresa a lafuncion (backtracking) y vuelve a buscar otra solucion deltablero central para el mismo proceso hasta agotarlo, si estoocurriese el sudoku no tiene solucion, quiza la tenga, soloque el algoritmo no es lo bastante potente para encontrarlo,pues existen algoritmos especıficos para cada complejidad desudoku, la nuestra es la mas general a nuestro criterio.

V. DESCRIPCION DEL ALGORITMO

Como se dijo, utilizamos una matriz de 21∗21, se definieroncuatro zonas distintas dentro del tablero que comparten simili-tudes que nos ayudaran a simplificar la solucion del problema,luego se considero la simetrıa que existe entre las filas y lascolumnas, lo cual ayudo mas a la simplicidad, bueno vayamospor pasos, primero, observe la Figura , en el estan definidoslas cuatro zonas, y se hacen distinciones a cinco tableros desudokus simples, con las letras A,B,C,D,E.

Las zonas definidas son:

1Se tienen en cuenta condiciones distintas para los extremos2Un sudoku bien planteado deberıa tener una sola solucion, nuestro

algoritmo busca todas las soluciones posibles.

+ + + + + + * * * x x x * * * + + + + + ++ + + + + + * * * x x x * * * + + + + + ++ + + + + + * * * x x x * * * + + + + + ++ TABLERO A * x x x * TABLERO C ++ + + + + + * * * x x x * * * + + + + + ++ + + + + + * * * x x x * * * + + + + + ++ + + + + + * * * o o o * * * + + + + + ++ + + + + + * * * o o o * * * + + + + + ++ + + + + + * * * o o o * * * + + + + + +x x x x x x * * * o o o * * * x x x x x xx x x x x x * TABLERO B * x x x x x xx x x x x x * * * o o o * * * x x x x x x+ + + + + + * * * o o o * * * + + + + + ++ + + + + + * * * o o o * * * + + + + + ++ + + + + + * * * o o o * * * + + + + + ++ + + + + + * * * x x x * * * + + + + + ++ + + + + + * * * x x x * * * + + + + + ++ TABLERO D * x x x * TABLERO E ++ + + + + + * * * x x x * * * + + + + + ++ + + + + + * * * x x x * * * + + + + + ++ + + + + + * * * x x x * * * + + + + + +

Cuadro IIIMATRIZ DE 21 ∗ 21 UTILIZADA

+ Al cual le llamamos zona 1* Al cual le llamamos zona 2o Al cual le llamamos zona 3x Al cual le llamamos zona 4

V-A. Recorrido de filas y columnas

Como se puede ver en la zona 1, se recorren todas las filasi, la descripcion en C de tal region queda en funcion de lascolumnas j de la siguiente manera:

if((j >= 0&&j <= 5)||(j >= 15&&j <= 20))

Para que definimos esta y las demas zonas?. . .Supongase que se quiere insertar un numero en la celda

(i = 3, j = 2), esta cae en la zona 1, para “mirar” la columnanecesitamos saber desde y hasta donde debemos recorrer lamatriz de 21 ∗ 21 para insertar tal numero y la jugada seavalida de acuerdo a las reglas del juego, por lo tanto si caeaquı, preguntaremos:

Es la fila i <= 8

Si esto ocurre debemos escanear en la columna j = 2 y lasfilas i = 0 a i = 8; en caso contrario preguntaremos:

Es la fila i >= 12

En este caso escanearemos en la columna j = 2 y las filasi = 12 a i = 20.

Para la zona 2, tenemos la siguiente condicion:

if((j >= 6&&j <= 8)||(j >= 12&&j <= 14))

Esta zona es muy importante, pues aquı es donde lossudokus simples comparten cada vertice con los demas, por lotanto al querer insertar un valor en esta zona y especıficamenteen uno de estos cuatro bloques, los recorridos deben abarcarambos tableros implicados, es decir el tablero del centro conuno de los demas de los extremos.

Primero analizaremos el desde, es decir desde donde sedebe empezar a escanear la columna si se quisiese insertaruna valor en esta zona. Por lo tanto una vez que estemos enesta zona nos preguntaremos:

Es i <= 8. Si ocurriese esto el desde es la fila i = 0Es i >= 12. Si ocurriese esto el desde es la fila i = 12Por utlimo, si no cumple ambos el desde es la fila i = 6.

LP1 - UC 3

Luego el hasta, aquı hay que poner mayor atencion, y ungrado de concentracion, para mayor comprension compareselas condiciones con la Tabla III, Por lo tanto una vez queestemos en esta zona nos preguntaremos:

Es i <= 5. Si ocurriese esto el hasta es la fila i = 8Es i >= 12. Si ocurriese esto el hasta es la fila i = 20Por utlimo, si no cumple ambos el hasta es la fila i = 14.

Para la zona 4, son las zonas no permitidas o ignoradas dela matriz, la condicion es:

if((i >= 9&&i <= 11)&&((j >= 0&&j <= 5)||(j >= 15&&j <= 20)))

Para las horizontales.

if((j >= 9&&j <= 11)&&((i >= 0&&i <= 5)||(i >= 15&&i <= 20)))

Para las verticales.Por ultimo la zona 3, que es el complemento de todas

las anteriores, es decir todas las celdas de la matriz queno cumplen con ninguna de las condiciones de las zonasanteriores.

Ahora vamos a algo concreto, una vez definidos las zonas,los lımites de recorrido(fila, columna), se tiene que para cadacelda (i=fila,j=columna), se define dos funciones:

retorna desde(int i, int j), que no hay casi nada queexplicar que es lo que hace, retorna la cota superior desdedonde se tiene que empezar a “mirar”.retorna hasta(int i, int j), retorna la cota inferior,hasta donde se tiene que “mirar”.

Por lo tanto aquı se explica la simetrıa, si quisieramossaber el recorrido en columna, llamamos a la funcion dela siguiente manera:

desde = retorna desde(i, j);

Cota superior(primera posicion, fila de la matriz a recorrer)

hasta = retorna hasta(i, j);

Cota inferior(ultima posicion, fila de la matriz a recorrer)Para el recorrido en fila, es lo mismo, solo que se inter-

cambian los parametros de fila por columna y viceversa, esdecir:

desde = retorna desde(j, i);

Cota izquierda(primera posicion, columna de la matriz arecorrer)

hasta = retorna hasta(j, i);

Cota derecha(ultima posicion, columna de la matriz a recorrer)

V-B. Recorrido del bloque

Es muy sencillo, suponiendo un bloque de 3 ∗ 3 como laTabla I, dentro de una matriz de 21∗21, por lo tanto podemosdebemos ver a cada bloque como un multiplo entero de 3,es decir para cada par (i, j), se puede saber a cual de losbloques pertenece dentro de la matriz, nuestra referencia esla parte superior izquierda, a partir del cual se desplaza doslugares para la derecha y dos lugares para bajo como en laTabla IV

Cuadro IVBLOQUE DE UN SUDOKU, REFERENCIA CELDA NEGRA

Es decir, para cada par (i, j), que se encuentre en cualquierparte de la matriz de 21 ∗ 21, se puede hallar el (i′, j′)(celdanegra) al cual pertenece (i, j), de la siguiente manera:

y = (i/3) ∗ 3;

Para la fila, y ademas

x = (j/3) ∗ 3;

Para la columna, con una notacion de par ordenado (x, y)para mayor entendimiento de la referencia, es importanteresaltar que tanto i como j se declaran con un tipo de datoint, lo cual da sentido al dividir y multiplicar por 3 lo cualparecerıa algo tonto, pero lo que hace es toma la parte enterade () y lo multiplica por 3 y eso es asignado a las variables.

VI. DESCRIPCION DE LA FUNCION PRINCIPAL

VI-A. Funcion Solucionador

Esta funcion es el cerebro, utiliza recursividad, bactrackingcon un esquema para todas las soluciones; como dijimosconceptualmente dividimos la matriz de 21 ∗ 21 en cincotableros de sudokus simples; el del centro llamado como B enla Tabla III es la primordial a nuestro criterio, lo que hacemoses agotamos todas las soluciones posibles de tal sub-tablero, ypara cada solucion verificamos si los tableros A,C,D,E tienensolucion, si esto ocurre se ha encontrado una solucion, paraque tal funcion pueda “distinguir” entre cada sub-tablero, leetiquetamos un numero, tal que:

Tablero A = 1; sector(i = 0, j = 0) a (i = 8, j = 8)Tablero B = 0; sector(i = 6, j = 6) a (i = 14, j = 14)Tablero C = 2; sector(i = 0, j = 12) a (i = 8, j = 20)Tablero D = 3; sector(i = 12, j = 0) a (i = 20, j = 8)Tablero E = 4; sector(i = 12, j = 12) a (i = 20, j =20)

En todo el codigo se han declarado nueve funciones, sibien este es un documento de apoyo para entender la logicaseguida y la solucion propuesta ya ha cumplido con lo suyo,por lo tanto las demas se describen dentro del codigo mismo loque realizan y como funcionan, algunas son: lectura de datos,escritura de solucion, impresion e interfaz para consola, entreotras.Ultima revision 25 de abril de 2011.

REFERENCIAS

http://www.publispain.com/sudoku/que es sudoku.html

http://www.publispain.com/sudoku/que_es_sudoku.html

This is the first line in the header Page: 1 of 9New3 * Print Date: 26/04/2011. Time: 0:05:02

#include <stdio.h>#include <stdlib.h>#include <ctype.h>#include <string.h>#define DIMENSION 21/* definimos la variable de tipo booleano */typedef int boolean;#define FALSE 0#define TRUE 1//***************************PROTOTIPO DE FUNCIONES********************************boolean Solucionador( int tablerote[ ][ DIMENSION ], int selector);int Verificador_Insertar( int tablerote[ ][ DIMENSION ], int i, int j, int valor);int retorna_desde(int i, int j);int retorna_hasta(int i, int j);void carga_tablerote(int tablero_X[][DIMENSION], int contenedor[]);void lectura_datos(int contenedor[]);void escritura_datos(int tablerote[][DIMENSION]);void parametros_recorrido(int vector[], int selector);//*********************************************************************************

//Ver Sudoku2TXT Pro.pdf adjunto para una mejor comprensión del códigoint main(){ int contenedor[373]; int tablerote[21][21]; lectura_datos(contenedor); carga_tablerote(tablerote, contenedor); Solucionador(tablerote,0);//se le pasa el valor "0" que indica el tablero B del centro return 0;}//Ver Sudoku2TXT Pro.pdf adjunto para una mejor comprensión del código

/*+++++++++++++++++++++++++++++++CEREBRO DEL ALGORITMO+++++++++++++++++++++++++++++++++++*//* la función solucionador es el "cerebro" de todo el algoritmo, aquí se utilizan técnicasde programación como recursividad y el famoso bactracking o vuelta atrás, básicamente lamatriz de 21*21 está dividida en 5 tableros individuales o sudokus simples, cada vez quese quiera insertar una valor de prueba se verifica si se puede hacer(Verificador_insertar)

Printed by Code Visual to Flowchart 1/9


mientras se pueda se avanza, si se llegase a un punto dónde ya no se puede avanzar y todavíano está resuelto se retrocede y se prueba de otra forma(backtracking).Vale pa pena mencionar que "selector" es quien dice de qué tablero estamos "hablando", sies cero(0), es el del medio, en el cual las condiciones son diferentes por compartir susvértices con los demás tableros.Lo que se hace es, se agotan todas las soluciones posibles que pueda tener el tablerocentral pues por cada solución que tenga ésta podría o no tener las cuatro restantes almismo tiempo; la condicion es if(decision && k == 9 && selector == 0).En pocas palabras, por cada solución que tenga el tablero del centro(selector == 0) se "ve"si las demás tienen solución, si esto ocurre el sudoku samurai tiene solución, es por elloque se busquen todas las soluciones del tablero central que de acuero a nuestras pruebas llegaa valores mayores a las milésimas de acuerdo a la complejidad del sudoku samurai*/

boolean Solucionador( int tablero_X[ ][ DIMENSION ], int selector){ int i, j, k, decision; int vector[4]; /* inicio de filas vector[0] fin de filas vector[1] inicio de columnas vector[2] fin de columnas vector[3] */ parametros_recorrido(vector, selector); for(i = vector[0]; i <= vector[1]; i++){ for(j = vector[2]; j <= vector[3]; j++){

if(tablero_X[ i ][ j ] != 0)//para los números que ya estaban o los que se han continue; //cargado buscando una solución hasta el momento

for(k = 1; k <= 9; k++){//prueba con cada valor posible(backtraking) if(Verificador_Insertar( tablero_X, i, j, k )){//verifica fila,columna y bloque tablero_X[ i ][ j ] = k;//Prueba con un valor y avanza en forma recursiva decision = Solucionador(tablero_X, selector);//recibe un TRUE o FALSE if(decision && k == 9 && selector == 0)//para el tablero central y "k==9" return TRUE; // es para agotar posibilidades else if(decision && selector != 0)//para los demás tableros de los extremos return TRUE; tablero_X[ i ][ j ] = 0;//valor no acertado vuelve a cero y prueba de nuevo



} } return FALSE;//Si ya no se ha podido avanzar, se vuelve atras con "decision" } } //si se ha encontrado una solución del tablero central, se "ve" si las demás tienen solución if(selector == 0 && (Solucionador(tablero_X, 1)) && (Solucionador(tablero_X, 2)) && (Solucionador(tablero_X, 3)) && (Solucionador(tablero_X, 4)) ) escritura_datos(tablero_X);//ha encontrado la solución return TRUE;}/*++++++++++++++++Verifica FILA, COLUMNA, BLOQUE+++++++++++++++++++++++++++++++++++++++++++*//*para cada (i,j), devuelve un TRUE o FALSE, para verificar si se puede insertar en tal posicionel valor "k"*/

int Verificador_Insertar( int tablero_X[ ][ DIMENSION ], int i, int j, int valor){ int a, b, x, y;//Mira columna a = retorna_desde(i,j);//cota superior (i,j) b = retorna_hasta(i,j);//cota inferior (i,j) for( a; a <= b; a++) { if(a != i && tablero_X[ a ][ j ] == valor) { return FALSE; } }//Mira fila a = retorna_desde(j,i);//cota izquierda (j,i) -- utiliza la simetría del sudoku,"simplificar" b = retorna_hasta(j,i);//cota derecha (j,i) -- menor uso de variables y misma funciónfor(a; a <= b; a++) { if(a != j && tablero_X[ i ][ a ] == valor) { return FALSE; } } //Mira cuadrado



y = ( i / 3 ) * 3;x = ( j / 3 ) * 3;for(a = 0; a < 3; a++) { for(b = 0; b < 3; b++) { if(a != i && b != j && tablero_X[ y + a ][ x + b ] == valor) { return FALSE; } } }return TRUE;}/*+++++++++++++++FUNCIÓN QUE RETORNA EL LÍMITE SUPERIOR A RECORRER+++++++++++++++++++++++++++++++++*//*retorna_desde y retorna_hasta fueron creadas para simplificar, utilizar simetríay que el código sea más compacto y fácil de depurar, lo que realiza retorna_desdees dado una coordenada (i,j), devuelve desde qué "fila" se debe empezar arecorrer y retorna_hasta devuelve hasta donde se debe recorrer la "fila", esto espara mirar la columna en cuestión("j").Para mirar la fila en cuestion("i") es lo mismo, cambiando (j,i) y todo lo explicado por "columna"aquí es donde se aplica la simetría.En la matriz de 21*21 se han definido tres zonas en las cuales las condiciones son las mismaspara cada par ordenado(i,j), y una cuarta que son las ignoradas o que no son parte del sudokupara mejor entendimiento ver sudoku2TXT Pro.pdf adjunto*/int retorna_desde(int i, int j){ if( (j >= 0 && j <= 5) || (j >=15 && j <= 20) )//primera zona { if(i <= 8) return 0; else return 12; } else if( (j >= 6 && j <= 8) || (j >= 12 && j <= 14) )//segunda zona { if(i <= 8) return 0; else if(i >= 15)



return 12; else return 6; } else //tercera zona return 6;}/*+++++++++++++++++++++FUNCIÓN QUE RETORNA EL LÍMITE INFERIOR A RECORRER++++++++++++++++++++++++++*/int retorna_hasta(int i, int j){ if( (j >=0 && j <= 5) || (j >= 15 && j <= 20) )//primera zona { if(i <= 8) return 8; else return 20; } else if( (j >= 6 && j <= 8) || (j >= 12 && j <= 14) )//segunda zona { if(i <= 5) return 8; else if(i >= 12) return 20; else return 14; } else//tercera zona return 14;}/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

/*++++++++++++++++++++++++++++++++++ Carga matriz de 21*21+++++++++++++++++++++++++++++++++++++*//*recibe el vector donde se cargaron los datos del txt, y traspasa los valores a la matrizde 21*21 que se utilizará para representar el sudoku samurai*/void carga_tablerote(int tablero_X[][DIMENSION], int contenedor[]){ int i, j, k=0; for(i = 0; i < DIMENSION; i++){ for(j = 0; j < DIMENSION; j++){ //las celdas que no son parte del sudoku o ignoradas



if((i>=9 && i <=11)&&((j>=0 && j <=5)||(j>=15 && j<=20)) || ((j>=9 && j <=11)&&((i>=0 && i <=5)||(i>=15 && i<=20)))) tablero_X[i][j] = 5;//carga un valor cualquiera else { tablero_X[i][j] = contenedor[k]; k++; } } } }/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

/*+++++++++++++++++++++++++++Carga del txt a un vector+++++++++++++++++++++++++++++++++++++++++++*//*lee los datos del txt en forma lineal, y va cergando en forna secuencial en unvector, que luego se cargará en la matriz de 21*21*/void lectura_datos(int contenedor[]){ int c,z = 0; char direccion[80]; printf("***********************************************************************\n"); printf("\t\t\t UNIVERSIDAD CATOLICA\n"); printf("\t\t\tPROGRAMA Sudoku2TXT Pro\n"); printf("\t\t RAMIREZ, PEDRO\t COLMAN, ALBERTO\n"); printf("***********************************************************************\n\n"); printf("Introduzca nombre del archivo a solucionar; Ejemplo: nombre.txt\n\n"); printf("Sudoku2TXT Pro ->"); gets(direccion); FILE *datos_entrada; datos_entrada = fopen(direccion, "r");//sera de lectura if (datos_entrada == NULL) { printf("El archivo no existe \n"); exit (EXIT_FAILURE); } else { printf("\n\n Espere por favor... En busca de alguna soluciOn... Puede tardar varios minutos... \n\n"); do



{ c = getc(datos_entrada); /* Obtiene un caracter del archivo */ //putchar(c); if(isdigit(c)){//Devuelve un valor verdadero si "c" es un dígito; de lo contrario 0(falso) contenedor[z] = c - 48;//como lee en ascii se le resta los 48 z +=1; } if(c == '-'){//si cumple con esto carga cero a la posicion del vector contenedor[z] = 0;//que significa celda vacía. z +=1; } } while (c != EOF); /* hasta encontrar EOF (el final del archivo)*/ } fclose(datos_entrada); }/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

/*++++++++++++++++++++++++++++++++Carga de la matriz al txt--SALIDA--++++++++++++++++++++++++++++*//*carga de la matiz de 21*21 a un archivo de texto, toda vez que se halla encontradouna solución*/void escritura_datos(int tablero_X[][DIMENSION]){ int i,j; char solucion[80]; printf("\n\t\t¡¡¡Solucion encontrada!!!\n\n"); printf("Introduzca el nombre del archivo resuelto; Ejemplo: nombre.txt\n"); printf("\nSudoku2TXT Pro->"); gets(solucion); FILE *datos_salida; datos_salida = fopen(solucion,"w");//sera de escritura for(i = 0; i < DIMENSION; i++){ for(j = 0; j < DIMENSION; j++){ if( (j % 21 == 0) && i != 0) fprintf(datos_salida,"\n"); //las celdas que no son parte del sudoku o ignoradas if((i>=9 && i <=11)&&((j>=0 && j <=5)||(j>=15 && j<=20)) || ((j>=9 && j <=11)&&((i>=0 && i <=5)||(i>=15 && i<=20)))) fprintf(datos_salida," ");



else fprintf(datos_salida,"%d ", tablero_X[i][j]); } } fprintf(datos_salida, "\n\n\n\n¡¡¡Gracias por utilizar Sudoku2TXT Pro!!!\n"); fprintf(datos_salida, "\n Colmán, Alberto\t59333-II"); fprintf(datos_salida, "\n Ramírez, Pedro\t59320-IE"); fprintf(datos_salida, "\n\n Lenguaje de Programación I"); fprintf(datos_salida, "\n\t UC - 2011"); fclose(datos_salida);

}/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*//*+++++++++++++++++++++++++RETORNA LOS LÍMITES DE CADA SUB-TABLERO+++++++++++++++++++++++++++++++++++++++*//*en la matriz de 21*21 están los 5 tableros "individuales" de sudoku simple, conesta función se retornan en un vector tales sectores, de acuerdo a un valor queselecciona cuál de tales tableros se quiere sus coordenadas que la limitan, éstees el "selector".*/void parametros_recorrido(int vector[], int selector){ if(selector == 0)//B { vector[0] = 6;//inicio de filas vector[0] vector[1] = 14;//fin de filas vector[1] vector[2] = 6;//inicio de columnas vector[2] vector[3] =14;//fin de columnas vector[3] } if(selector == 1)//A { vector[0] = 0; vector[1] = 8; vector[2] = 0; vector[3] =8; } if(selector == 2)//C { vector[0] = 0; vector[1] = 8; vector[2] = 12;



vector[3] =20; } if(selector == 3)//D { vector[0] = 12; vector[1] = 20; vector[2] = 0; vector[3] =8; } if(selector == 4)//E { vector[0] = 12; vector[1] = 20; vector[2] = 12; vector[3] = 20; }}/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/


Engineering

Inteligencia Artificial del Juego SUDOKU SAMURAI