Programación de Computadores, Proyecto de Autoestudio “Sudoku Java”

Programación de Computadores, Proyecto de Autoestudio “Sudoku Java” Luna Mendoza Jaime Alberto Facultad de Ingeniería, Programa de Ingeniería Industrial, Politécnico Grancolombiano Bogotá DC, Colombia [email protected]

Abstract The purpose of this self-study project was the study and analysis of the mathematical, logical and computational methods for the design and implementation of a unique algorithm for solving any Sudoku puzzle type, in they general representation of one 9x9 matrix. This was done based on the study concerning Sudoku puzzles, its resolution techniques, bibliographic references as well as the literature on the Java programming and concepts abstracted from the classroom.

Resumen El objeto del presente proyecto de autoestudio fue el estudio y análisis de los métodos matemáticos, lógicos y computacionales para el diseño e implementación de un único algoritmo para la resolución de cualquier rompecabezas del tipo Sudoku, en su representación general de matriz 9x9. Esto se realizo partiendo de las referencias bibliográficas concernientes al estudio de los rompecabezas del tipo sudoku, sus técnicas de resolución, así como la bibliografía referente a la programación en java y conceptos abstraídos del aula de clase.

I. INTRODUCCIÓN Se sabe bien que la solución del juego sudoku se divide en varias estrategias, como vamos a ver a través sobre el lenguaje Java y su relevancia como lenguaje estándar en la actualidad; además se define en que consiste el Sudoku, para de esta forma establecer la relación ge se puede generar entre el uso de algoritmos para la resolución de problemas y tener un programa de forma versátil la solución a cualquier sudoku establecido dentro de los parámetros de cada persona. Continuando con lo establecido anteriormente el presente proyecto de aula se enfoco en el diseño, desarrollo e implementación de un código que permita determinar la solución para cualquier rompecabezas del tipo Sudoku estándar (del tipo matriz 9x9) si este es valido, o en caso contrario determinar si el sudoku es invalido y en otros casos

correspondientes determine si tiene infinitas soluciones o ninguna. Para lograr la implementación del ya mencionado algoritmo para la resolución del rompecabezas de tipo Sudoku se considero la aplicación de técnicas aplicadas en la resolución de este tipo de rompecabezas empleadas cotidianamente como es el caso del Retroceso o Backtracking, así como de técnicas de programación como lo es la programación por ciclos y la programación por recursividad o recursión. Para abordar el proceso diseño, desarrollo e implementación del algoritmo para la resolución de Sudoku, el presente documento hace énfasis en definir brevemente que es un lenguaje de programación y específicamente que es el lenguaje de programación Java. Definiendo a su vez en que consiste un rompecabezas del tipo Sudoku, las técnicas empleadas comúnmente para su resolución, así como análogamente las técnicas de nivel computacional con las que se puede dar solución a un rompecabezas de este tipo, para de este modo llegar al método empleado para la generación del algoritmo del cual es objeto el presente proyecto de aula.

II. MARCO TEÓRICO Lenguaje de Programación Para iniciar el abordaje del presente proyecto de auto estudio se hace necesario iniciar por definir qué es un lenguaje de programación y en consecuencia que es Java. Un lenguaje de programación se define como la notación constituida por símbolos y reglas que permiten escribir programas. Donde todo programa esta compuesto por su propia sintaxis y semántica. Por ende se establece que “A través de los lenguajes de programación es posible establecer una comunicación sistematizada y precisa con una computadora.” (Velarde de Barraza, 2006).

Lenguaje Java Ya habiendo definido a groso modo lo que en si significa un lenguaje de programación y para que se emplea, se puede definir Java como un lenguaje de programación, pero que no

se limita a una arquitectura única sino que esta dotado de una portabilidad que permite ejecutarse independiente de la plataforma, tanto de hardware como de software. Java nace de esta misma necesidad de portabilidad como paso subsecuente en la evolución tecnológica se consideraba en los años 90 la implementación de inteligencia en los electrodomésticos (Dean, 2009), de ahí la necesidad del desarrolló de un lenguaje portable e independiente del hardware donde se ejecutaría. Adicional a esto Java es un lenguaje orientado a objetos, donde el enfoque es el objeto en si mismo, brindando herramientas al programador representar el objeto en el espacio del problema, de forma tan general que evita limitarse a un problema en especifico y que las soluciones empleadas sean adaptables a diferentes entornos únicamente con la adición de nuevos objetos (Eckel, 2002).

1

Figura 1

Sudoku, el Rompecabezas matemático El sudoku es un juego que se presenta a forma de problema, dicho problema esta representado en un tablero de R x C casillas, donde R es el numero de filas y C el numero de Columnas. Dicho tablero se divide en un numero k de bloques de un tamaño r x c c (con r = √𝑅 y c = √C ) en los que se colocaran r x c elementos (Sudoku, 2013) donde a cada conjunto r x c se le denomina bloque. En la Figura 1. se observa la distribución estándar de un tablero de Sudoku. El objetivo del Sudoku es poder poder rellenar los espacios vacíos con números de un digito del 1 al 9, sin repetir numero alguno en la misma fila, Columba o bloque. Algunos de los espacios ya cuentan con números a modo de pista. De alguna forma el Sudoku se basa en la búsqueda de la combinación numérica perfecta. Por ello existen denominadas reglas para solucionarlo:

II. ESTRATEGIAS PROPUESTAS Para la resolución del rompecabezas de tipo Sudoku existen diferentes técnicas y/o estrategias que difieren según la complejidad del tablero. Estas técnicas se encuentran clasificadas por orden de dificultad en el rango de Fácil, Medio y Avanzado según sea el caso (Limited, 2014). Para el presente proyecto de aula nos limitaremos a las técnicas de nivel Fácil y su contraparte a nivel de programación.

Estrategias de Nivel Fácil Las técnicas en este nivel son recomendables para la resolución de la mayoría de Sudokus como los incluidos en los periódicos y revistas. •

Regla 1: Se debe completar las casillas vacías con un solo número del 1 al 9. Regla 2: En la misma fila no puede tener números repetidos. Regla 3: En la misma columna no puede tener números repetidos. Regla 4: En una misma región no pueden existir números repetidos. Regla 5: la solución de un sudoku es única y dependiendo de las pistas establecidas de su creador.

Posición Individual

Esta técnica consiste en elegir una fila o Columna o bloque y luego ir a través de cada uno de los números que no hayan sido colocados anteriormente. Puesto que ya se han colocado otros números previamente se limitaran las posiciones donde pueden ir ubicados otros números. Si se ha reducido con éxito se podrán completar los espacios vacíos en línea recta, como se muestra en la Figura 2. Es por ello que los individuos pueden lograr llenar con esta estrategia tomar por renglones números y comenzar a descifrar cuales serán el resto de números restantes dentro de cada zona que aún no completa los renglones más llenos.

1

Imagen recuperada de http://www.infosudoku.com/reglas.php

Estrategias de solución computacional Para la resolución de un rompecabezas Sudoku de forma computacional mediante el empleo de Algoritmos, hay que partir del hecho de que el rompecabezas es una representación de una matriz numérica 9x9 la cual a su vez de encuentra dividida en pequeñas matrices de 3x3 que corresponden a los bloques. Adicional a ello hay que tener en cuenta que cada fila y columna corresponden a permutaciones de los elementos dentro del tablero. Dentro de los métodos de resolución de sudoku por medio de algoritmos se encuentra el método de Programación Lineal (Linear Programming).

2

Figura 2

•



•

Candidato Individual

Esta técnica surge de haber realizado el descarte de un numero de todas las demás casillas alrededor, por lo que en consecuencia solo habrá un único número a la izquierda que podrá corresponder a la casilla en cuestión, tal y como se muestra en la Figura 3. Cuando el individuo toma decisiones de comenzar a establecer números supuestos alrededor tiene la ventaja de ir desechando números de otros lugares y llegar a una velocidad más rápida a la solución del sudoku. Pero para que la estrategia sea eficaz el jugador debe ser lo suficientemente capaz para crear relaciones entre los números que escoge para cada casilla ya que se llegase a equivocarse en un número, al final su sudoku quedara mal y deberá comenzar desde el principio.

3

Figura 3 .

https://www.sudokuoftheday.com/techniques/single-position/ 3

Este método de solución computacional modela el sudoku como un problema matemático partiendo de la premisa de que cada sudoku corresponde a una matriz n*n. (Barlett & Langville, 2008). En la programación lineal da respuesta a situaciones en las que se necesita maximizar o minimizar funciones que se muestran sujetas a determinadas limitaciones, que llamaremos restricciones. Para lograr resolver los problemas mediante la programación se debe hacer una identificación de los elementos básicos del modelo matemático: o

Función objetivo: Se tiene una estrecha relación con la pregunta general en la cual se desea responder. Sí en un modelo resultara distintas preguntas, la función objetivo se relaciona con la pregunta del nivel superior. Así por ejemplo, si en una situación se desean minimizar los costos, es muy probable que la pregunta de mayor nivel sea la que se relacione con aumentar la utilidad en lugar de un interrogante que busque hallar la manera de disminuir los costos.

o

Variables: Similar a la relación que existe entre objetivos específicos y objetivo general que comportan las variables de decisión respecto a la función objetivo, por ello estas se identifican partiendo de una serie de preguntas derivadas de la pregunta fundamental. Las variables de decisión son aquellas que en teoría son factores controlables del sistema que se está modelando, de ahí que, estas pueden tomar diversos valores posibles, de los cuales se precisa conocer su valor óptimo, que contribuya con la consecución del objetivo de la función general del problema.

o

Restricciones: Para hablar de las restricciones en un problema de programación lineal, tomamos como importancia a todo aquello que limita la libertad de los valores que pueden tomar las variables de decisión. La mejor manera de hallarlas consiste en



2 Imagen recuperada de

Imagen recuperada de https://www.sudokuoftheday.com/techniques/single-candidate/

Programación Lineal

pensar en un caso hipotético en el que decidimos darle un valor infinito a nuestras variables de decisión •

Retroceso (Backtracking)

Esta técnica consiste en el desarrollo por prueba y error donde en cada paso el algoritmo toma y verifica una posible solución, de ser correcta prosigue, en caso contrario devuelve el sudoku a su estado previo. (Fundaciòn Wikiedia Inc., 2015). Además, se refiere como técnica general de resolución de problemas, aplicable tanto a problemas de optimización, juegos y otros tipos. La solución de un problema de back tracking se puede expresar como (x1, x2,..., xn), satisfaciendo unas restricciones P(x1, x2,..., xn) y tal vez optimizando una cierta función objetivo. El resultado es equivalente a hacer un recorrido en profundidad en el árbol de soluciones. Sin embargo, este árbol es implícito, no se almacena en ningún lugar. Existen tres tipos de problemas a resolver utilizando la técnica de Back tracking: o

Búsqueda de una solución

o

Búsqueda de todas las soluciones

o

Búsqueda de la solución óptima

recursividad ya que lo que se requiere es hacer un llamado por cada posición donde se pueda realizar operación y en caso contrario volver a el anterior y realizar un llamado de la función por si mismo. El método propuesto consiste en realizar una comprobación en los índices i, j de la matriz están vacíos es decir equivalentes a 0 y en caso de cumplirse se procede a probar con las combinaciones posibles de enteros faltantes, tanto la en fila como en la columna a la que pertenece la casilla en cuestión, para posteriormente realizar un llamado recursivo de igual forma en la casilla subsiguiente y el método se finaliza en el momento q se ha ubicado un valor valido en la casilla en cuestión. Se parte desde la posición [0][0] para localizar la primera posición libre, como se muestra en la Figura 4.

III. ESTRATEGIA EMPLEADA Para la resolución del Sudoku propuesto en el presente proyecto de aula se decidió emplear un método por recursión, dada ya que para hallar la solución computacionalmente es necesario el probar todos los movimientos posibles, y la programación por recursión nos permite hacerlo partiendo desde un caso base. •

Recursión.

Recursión es cuando un método se llama a si mismo (Dean, 2009). Mediante este método lo que se busca es encontrar la solución mas sencilla de forma progresiva para solucionar el problema al cual se denomina caso base. El caso base es la condición que esta asociada con la versión mas simple del problema (Dean, 2009). Luego se aplican los casos recursivos, que pueden ser tantos como se necesiten, estos casos recursivos son sub métodos que contienen una o varias llamadas al método con uno o mas valores que lo invocan de forma progresiva hasta satisfacer la solución correcta. Como se definió en el numeral II, en el apartado de técnicas de solución, existe una técnica llamada Retroceso o Backtracking (por su nombre en inglés) es análoga al método de programación por recursión, dado que siempre se recurre a hacer un llamado de prueba y error hasta que se satisfaga la respuesta retornando en caso negativo el sudoku sin modificación, en contraste se emplea esta técnica mediante

4

Figura 4



Remplazar el valor de 0 por el de 1 y si la entrada no está duplicada, por recursión se vuelve al inicio para ubicar la siguiente casilla vacía y probar el siguiente numero. En caso que no haya mas números por probar y no hay solución, salir del método indicando que no se ha encatrado solución, en caso contrario se denotara que la solución ha sido encontrada, y el sudoku a sido exitoso. En caso del numero estar repetido se vuelve al método y se prueba con el numero siguiente. En la Figura 5. Se ilustra el método recursivo para completar cada casilla.

4 Imagen recuperada de http://www.migapro.com/sudoku-solverrecursive-method/

También se concluyó que todo problema que pueda ser modelado o expresado de forma matemática puede ser expresado y solucionado computacionalmente, comprobando lo visto en el aula. Finalmente se pudo demostrar que no es necesario crear un algoritmo para cada problema en especifico, sino que mediante el modelado de un algoritmo general se puede hacer solución a diferentes problemas en este caso diferente rompecabezas de sudoku sin tener que hacer una programación especifica para cada caso.

REFERENCIAS

5

Figura 5

Para que este método fuera eficaz, se opto por sub dividir la matriz del Sudoku en pequeñas sub matrices de 3x3 como indica la Figura 6.

• • • •

•

•

•

6

Figura 6



IV. CONCLUSIONES Mediante la realización del presente proyecto de aula, se ha concluido que no existe un único método o forma de realizar un algoritmo o programa para la resolución de un mismo problema, y cada solución difiere del método propuesto para la solución mas que de el problema en si para llegar a la respuesta esperada.

5 Imagen recuperada de http://www.migapro.com/sudoku-solverrecursive-method/ 6 Imagen recuperada de http://www.migapro.com/sudoku-solverrecursive-method/

Velarde de Barraza, O. (2006). Introducción a la programación orientada a objetos. México: Pearson. Eckel, B. (2002). Piensa en Java. Madrid: Pearson. Dean, J. S. (2009). Introducción a la programación con JAVA. México D.F.: McGraw-Hill. Sudoku. (2013). Universidad Carlos III de Madrid Departamento de Ingeniería Telemática. Recuperado el 2015, de Universidad Carlos III de Madrid: http://www.it.uc3m.es/jvillena/irc/practicas/1213/01mem.pdf Limited, A. (2014). Sudoku Techniques. Recuperado el 17 de Agosto de 2015, de Sudoku of the Day: https://www.sudokuoftheday.com/techniques/ Barlett, A., & Langville, A. (14 de Enero de 2008). An Integer Programming Model for the Sudoku Problem. Journal of Online Mathematics and its Applications . Fundación Wikiedia Inc. (15 de Julio de 2015). Sudoku backtracking. Recuperado el 2 de Septiembre de 2015, de Wikipedia: https://es.wikipedia.org/wiki/Sudoku_backtracking