Sudoku es un juego de l贸gica en el que se debe rellenar una cuadr铆cula de 9x9 celdas dividida en subcuadr铆culas de 3x3 celdas con n煤meros del 1 al 9. La cuadr铆cula inicialmente contiene algunos n煤meros. El objetivo es rellenar las celdas vac铆as con n煤meros que no se repitan en ninguna fila, columna o subcuadr铆cula de 3x3 celdas. En este problema, se le proporciona una cuadr铆cula parcialmente rellenada y se le pide que la complete.
Se plantea inicialmente la resoluci贸n del problema de una manera visual implementando una interfaz gr谩fica PyGame, para luego implementar un algoritmo de resoluci贸n de Sudoku, para los cuales se busca realizar un benchmark entre diferentes maneras de resolver el tablero de Sudoku, como lo son:
- Backtracking con y sin heuristica
- Red neuronal convolucional (CNN)
- Algoritmos gen茅ticos
El ambiente del Sudoku es discreto, est谩tico y determinista. Es discreto porque el juego se desarrolla en un conjunto finito de posibles estados (cada configuraci贸n del tablero). Es est谩tico porque el ambiente no cambia mientras se resuelve el Sudoku, es decir, no hay elementos que se muevan o evolucionen con el tiempo. Es determinista porque las acciones tomadas por el agente tienen un resultado predecible y 煤nico
Las acciones son discretas y el dominio de cada acci贸n es un n煤mero del 1 al 9, representando el n煤mero que se quiere colocar en la celda, estas pueden ser representada por una tupla que contiene las coordenadas de la celda en la que se desea colocar el n煤mero, junto con el n煤mero mismo. Por ejemplo, para colocar un 2 en la celda (0, 2), la acci贸n puede ser representada como (0, 2, 2).
La entrada consiste en una sentencia de 81 caracteres que representan una cuadr铆cula de Sudoku parcialmente rellenada. Los d铆gitos del 1 al 9 representan los n煤meros en la cuadr铆cula y el n煤mero cero representa las celdas vacia. Para luego convertir a un numpy array de 9x9, utilizando la funci贸n reshape de numpy.
Se considera este tipo de entrada para el problema, ya que es la forma m谩s com煤n de representar un Sudoku. Adem谩s de incorporar facilmente dataset de millones de juegos, con su respectiva soluci贸n, para afrontar de mejor manera el problema.
Se requiere una instalaci贸n correcta de TensorFlow, para m谩s informaci贸n del proceso de instalaci贸n se puede consultar la documentaci贸n oficial.
- Clonar el repositorio
git clone https://github.com/fcocea/SudokIA
- Creaci贸n de entorno virtual (Opcional)
python -m venv .venv
source .venv/bin/activate
- Instalar las dependencias
pip install -r requirements.txt
- Ejecutar el script
python main.py --help
Se tiene el m贸delo ya entrenado con el algoritmo de resoluci贸n de Sudoku, para ejecutarlo se debe correr el siguiente comando:
python main.py --solve --method cnn --model cnn/Model9x64x5-11.keras
- Building a Deep Learning Model to Solve Sudoku: A Case Study with CNNs
- Sudoku Solver - @felipecacique
- Solving Sudoku with Neural Networks
Proyecto realizado por:
- Oscar Castillo
- Francisco Cea
- Matias Gayoso