Diseño e implementación de un procesador específico para la resolución de Sudokus

Olivito del Ser, Javier
Resano Ezcaray, Jesús Javier (dir.) ; González Calvo, Carlos (dir.)

Universidad de Zaragoza, CPS, 2010
Departamento de Informática e Ingeniería de Sistemas, Área de Arquitectura y Tecnología de Computadores

Ingeniero en Informática

Resumen: Este proyecto surge como propuesta de participación en el Field-Programmable Technology ’09 Design Competition, concurso de diseño hardware que propuso el desarrollo de un procesador específico para resolver Sudokus de diferentes tamaños sobre una FPGA. Nuestro primer diseño consistió en la implementación de un algoritmo de ramificación y poda, utilizando como función de poda la eliminación de candidatos mediante las reglas del Sudoku. El diseño de la memoria y de la ruta de datos estuvo encaminado a explotar el paralelismo que presenta dicha función de poda. Los resultados de esta primera versión evidenciaron una necesidad de mejora, puesto que nuestro diseño era ineficiente en la resolución de Sudokus de gran tamaño o de alta complejidad. La versión final de nuestro procesador mejora estos resultados incorporando una etapa de preprocesamiento que aplicaba un conjunto de heurísticas capaces de acotar el espacio de búsqueda. Paralelamente, se desarrolló una versión software equivalente que se utilizó para depurar el diseño hardware y para evaluar la eficacia de las heurísticas existentes antes de implementarlas en el procesador hardware. Las mejoras de esta versión permiten una resolución eficiente de Sudokus de baja-media complejidad y gran tamaño (hasta orden 11: 121x121 casillas), si bien aun se muestra ineficiente en la resolución de los Sudokus de alta complejidad. Los resultados obtenidos con este diseño nos permitieron lograr el primer premio del FPT '09 Design Competition. Además el diseño fue elegido para su presentación en el congreso y una descripción del mismo fue publicada en sus actas, siendo accesible a toda la comunidad científica a través del IEEE Xplorer.

Palabra(s) clave (del autor): Procesador ; Sudoku ; Diseño hardware ; Arquitectura de computadores ; FPT

Tipo de Trabajo Académico: Proyecto Fin de Carrera