Repositorio Institucional de Documentos

Proyecto de fin de carrera Diseño e implementación de un procesador específico para la resolución de Sudokus Director: Javier Resano Codirector: Carlos González Autor: Javier Olivito del Ser Ingeniería Informática Abril 2010 Departamento de informática e ingeniería de sistemas Centro Politécnico Superior Grupo de Arquitectura de Computadores 2 ….…………………………………………………………………………. …………………………………………………………………….. ………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. ………………………………………… ………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………… ……………………….. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. ……………………………………………………………………… Índice Resumen 1. Introducción 1.1. Qué es un Sudoku 1.2. Qué es una FPGA 1.3. Especificaciones del FPT ’09 2. Versión inicial: Procesador basado en la técnica de ramificación y poda 2.1.Motivación 2.2.Diseño del procesador 2.3.Detalles de implementación 2.3.1. Requisitos de memoria 2.3.2. Implementación de la memoria 2.3.3. Implementación del evaluador de la función de poda 2.4.Depuración 2.4.1. Resultados de la fase de depuración 2.5.Resultados 3. Versión final: Procesador basado en la técnica de ramificación y poda con funciones heurísticas para acotar el espacio de búsqueda 3.1.Motivación 3.2.Descripción de las heurísticas 3.3.Elección del conjunto de heurísticas a implementar 3.4.Diseño del procesador 3.4.1. Estrategia global 3.5.Detalles de implementación 3.5.1. Requisitos de memoria 3.5.2. Implementación de la memoria 3.5.3. Implementación de las heurísticas seleccionadas 3.6.Resultados 4. Conclusiones 5. Planificación Anexo I: Artículo publicado en las actas del FTP '09 Anexo II: Poster presentado en el congreso del FTP '09 5 6 6 7 7 8 8 9 10 10 10 12 13 13 15 17 17 17 19 20 21 22 22 23 24 27 29 32 3 9 10 11 12 13 14 17 17 18 18 18 19 22 24 25 26 32 32 ….…………………………………………………………………………. ……………………………………………………. ……………………………………. …………………………. …………………………………………………………………………. …………………………………………………………………………. ……………………………………………… …………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………….……………………………………… ……………………… …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………… ………………………………………………………………. Índice de figuras Figura 1: Memoria capaz de suministrar una columna y una caja en un solo ciclo de reloj, y una fila, columna y caja en dos ciclos de reloj Figura 2: Módulo 8-comparador Figura 3: Ruta de datos simplificada del algoritmo de ramificación y poda Figura 4: Diagrama de flujo de las operaciones de memoria necesarias en la ejecución del algoritmo de backtracking sobre el Sudoku Figura 5: Evaluador de 8 candidatos en paralelo Figura 6: Comparativa de la dificultad entre Sudokus de tipo A y B en función del número de casillas libres y candidatos promedio iniciales Figura 7: Candidato único Figura 8: Candidato único oculto Figura 9: Pares escondidos Figura 10: Pares pelados Figura 11: Líneas de candidatos Figura 12: Líneas dobles Figura 13: Algoritmo de resolución mediante heurísticas y backtracking utilizado en la versión HW Figura 14: Esquema hardware del evaluador que implementa la heurística “candidatos únicos” Figura 15: Esquema de la implementación hardware de la heurística “candidato único oculto” Figura 16: Esquema de la implementación hardware de la heurística “Pares escondidos” Figura 17: Diagrama de Gantt de la planificación inicial del proyecto Figura 18: Diagrama de Gantt del desarrollo real del proyecto 4 15 16 20 23 27 28 ….. ….…………………………………………………………………………. ………………………………………………………….. ………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………… ………………………………………………………….. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………….……………………………………… ……………………… …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………………. …………………………………………………………………… …………………………………………………………………………… Índice de tablas Tabla 1: Tiempos de resolución de los distintos benchmarks en la versión inicial Tabla 2: Recursos de la FPGA utilizados según el número de candidatos evaluados por ciclo de reloj Tabla 3: Enumeración de las heurísticas implementadas en las versiones SW y HW finales Tabla 4: Requisitos de memoria para la implementación de heurísticas de eliminación de candidatos Tabla 6: Recursos de la FPGA utilizados en función de las heurísticas implementadas Tabla 7: Tiempos de resolución de los distintos benchmarks en la versión final 5 Diseño e implementación de un procesador específico para la resolución de Sudokus 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. 6 1. Introducción El proyecto surgió como propuesta de participación en el FPT 2009 Design Competition (en adelante, concurso), concurso internacional de diseño hardware. El objetivo del proyecto consistía en el diseño e implementación de un procesador específico para la resolución de Sudokus. Además, la realización del proyecto conlleva varios objetivos: - Aprender diseño hardware avanzado - Familiarización con un entorno de descripción hardware (Xilinx ISE) y el lenguaje de descripción hardware VHDL - Comparación de soluciones Hardware / Software para un problema dado El contenido de esta memoria sigue un orden cronológico del desarrollo del proyecto. La sección 2 describe el desarrollo de la primera versión del diseño, basada en la técnica de ramificación y poda, así como los resultados que motivaron el desarrollo de una segunda versión. La sección 3 describe dicha segunda versión, la cual añade un conjunto de heurísticas que acotan en espacio de búsqueda. La sección 4 consta de las conclusiones, tanto a nivel personal como aquellas extraídas del desarrollo del proyecto y de sus resultados. La sección 5 muestra la planificación inicial de las tareas del proyecto y las tareas y sus distribuciones temporales finales. El anexo I contiene el artículo que se publicó en el concurso, describiendo el trabajo presentado. El anexo II contiene el poster que se presentó en el concurso, describiendo más someramente el trabajo. 1.1 ¿Qué es un Sudoku? Sudoku es un juego de lógica de origen japonés que consiste, en su versión estándar, en rellenar una caja de 9x9 casillas divida en nueve cajas de 3x3 casillas con los números del 1 al 9 cumpliendo las siguientes restricciones: - En cada fila aparece cada número una vez - En cada columna cada número aparece una vez - En cada caja cada número aparece una vez El problema del Sudoku es generalizable a orden N, resultando un Sudoku de N2 x N2 casillas dividido en N2 cajas de tamaño NxN, que deben ser rellenadas con los 7 números del 1 al N2 siguiendo las mismas restricciones que las anteriormente mencionadas para el tamaño estándar. Un sudoku correctamente planteado posee solución única. 1.2 ¿Qué es una FPGA? Una FPGA (Field Programmable Gate Array) es un circuito integrado que contiene bloques de lógica, elementos de memoria e interconexiones, todos ellos programables. La configuración de la FPGA mediante la interconexión de los bloques lógicos y la funcionalidad de los mismos, permite generar el sistema lógico deseado. La descripción del sistema lógico que se desea diseñar se suele realizar mediante el uso de un lenguaje de descripción de hardware, siendo los más usados VHDL (acrónimo de VHSIC HDL, Very High Speed Integrated Circuit Hardware Description Language) y Verilog. 1.3 Especificaciones del concurso El concurso está centrado en la computación de propósito general en FPGAs. Más específicamente, se propone diseñar un procesador que resuelva Sudokus de distintos tamaños. Las especificaciones detalladas más relevantes son:  Se pretende resolver Sudokus desde orden 3 hasta orden 15  La puntuación final será calculada mediante la siguiente expresión: Siendo tN el tiempo medio en resolver un Sudoku de orden N. El tiempo máximo permitido para resolver un Sudoku de orden N está definido por: tmax = 3 * 10-4N6 segundos. Todo Sudoku no resuelto en tiempo igual o menor al definido por la anterior función tendrá puntuación cero.  Además del Sudoku resuelto, se debe calcular y enviar el checksum del Sudoku resuelto según la siguiente expresión: 8 Siendo d[r,c] el valor de la casilla situada en la fila r y la columna c.  La entrada y salida se realizará mediante RS-232 ajustándose a el siguiente formato: Entrada de datos a la FPGA 0xA5 0x3C 0x5A 0xC3 N*N d[0,0] d[0,1] … d[N*N,N*N] checksum Salida de datos desde la FPGA 0xA5 0x3C 0x5A 0xC3 checksum N*N d[0,0] d[0,1] … d[N*N,N*N]  La FPGA sobre la que se implementará el diseño debe ser una de las siguientes: - DE2 Development and Education Board - XUP Virtex-II Pro Development System - Xtreme DSP Starter Platform – Spartan-3A DSP 1800A Edition - DE2-70 Development and Education Board - Altium NanoBoard 3000 Nuestro diseño ha sido implementado sobre la XUP Virtex-II Pro Development System (en adelante, FPGA). 2. Versión inicial: Procesador basado en la técnica de ramificación y poda 2.1 Motivación Como primera aproximación para la resolución de un Sudoku mediante un procesador dedicado, planteamos un algoritmo de ramificación y poda (en adelante, backtracking) cuya función de poda sea la eliminación como candidato para una casilla de todo número que esté en la fila, columna o caja correspondientes a dicha casilla. La implementación hardware de este algoritmo llevada a cabo permite explotar el paralelismo que posee la función de poda, puesto que las comparaciones que precisa (comparar un posible candidato con los números fijados de su correspondiente fila, columna y caja) se pueden realizar en paralelo, permitiendo acelerar la búsqueda del siguiente candidato válido para cada casilla. 9 2.2 Diseño del procesador El diseño del procesador se debe ajustar tanto a las especificaciones del concurso, como a las limitaciones que presenta la FPGA. Son destacables dos decisiones de diseño: a) Diseño de la memoria: Decidimos almacenar en memoria el Sudoku de tres formas distintas. Esto triplica el espacio necesario en memoria con respecto a almacenarlo de un único modo, pero simplifica enormemente el acceso a la información necesaria en cada instante. Además diseñamos una memoria capaz de proporcionar tanto una fila, como una columna y una caja en único ciclo de reloj (ver figura 1). b) Diseño del evaluador de la función de poda: Para explotar el paralelismo existente en la función de poda de esta versión, debemos proveer a la arquitectura de capacidad de comparación para evaluar la validez de más de un candidato simultáneamente. En nuestro diseño hemos conseguido evaluar 8 candidatos en paralelo (ver figura 2). Fig. 1. Memoria capaz de suministrar una columna y una caja en un solo ciclo de reloj, y una fila, columna y caja en dos ciclos de reloj. 16 Versión BRAMs Slices Evaluación 1 candidato/ciclo 107 (78%) 9.471 (69%) Evaluación 2 candidatos/ciclo 107 (78%) 9.716 (70%) Evaluación 4 candidatos/ciclo 107 (78%) 10.699 (78%) Evaluación 8 candidatos/ciclo 107 (78%) 12.227 (89%) Tabla 2. Recursos de la FPGA utilizados en función del número de candidatos evaluados por ciclo 17 3. Versión final: Procesador basado en la técnica de ramificación y poda con funciones heurísticas para acotar el espacio de búsqueda 3.1 Motivación Anteriormente hemos probado que nos enfrentamos a un problema de búsqueda de solución en un espacio de búsqueda extremadamente amplio. La literatura sobre Sudokus ofrece una colección de técnicas de eliminación de candidatos que permiten reducir el espacio de búsqueda. Es nuestro objetivo pues conocer dichas técnicas y decidir qué conjunto de ellas implementar y cómo hacerlo para poder tratar con Sudokus no abordables hasta el momento. 3.2 Descripción de las heurísticas Candidato único: Si existe una casilla con un solo candidato, podemos fijar dicho candidato como número de dicha casilla. Candidato único oculto: Dada una fila, columna o caja (en adelante, región), si un candidato dado aparece en una única casilla, podemos fijar dicho candidato como número de dicha casilla. Pares escondidos: Dada una región, si existe una dupla de candidatos que solo pueden ir en dos casillas de dicha región, y dichas casillas son las mismas para ambos candidatos, podemos asegurar que esas dos casillas estarán ocupadas por la dupla de candidatos en cuestión, y por lo tanto eliminar el resto de candidatos de ambas casillas. Fig. 7. Candidato único. El 9 es candidato único de la casilla 4. Podemos fijarlo y eliminar el 9 como candidato del resto de casillas. Fig. 8. Candidato único oculto. El 6 es candidato único oculto de la casilla 6. Podemos fijarlo. 18 Tríos, cuartetos y quintetos escondidos: Extensión de la técnica “Pares escondidos” a tres casillas y tres candidatos, cuatro casillas y cuatro candidatos, y cinco casillas y cinco candidatos respectivamente. Pares pelados: Si existen dos casillas en una región ambas con solo dos candidatos, y dichos candidatos son los mismos en las dos casillas, podemos eliminar ambos candidatos del resto de casillas de la región. Tríos, cuartetos y quintetos pelados: Extensión de la técnica “Pares pelados” a tres casillas y tres candidatos, cuatro casillas y cuatro candidatos, y cinco casillas y cinco candidatos respectivamente. Líneas de candidatos: Si existe una caja en la cual algún candidato aparece únicamente en una sola fila/columna de dicha caja, podemos eliminar dicho candidato del resto de casillas de la fila/columna fuera de la caja. Fig. 9. Pares escondidos. El 1 y el 9 forman un par escondido en las casillas 4 y 7. Podemos eliminar el resto de candidatos de dichas casillas. Fig. 10. Pares pelados. El 6 y el 8 forman un par pelado en las casillas 4 y 7. Podemos eliminar el 6 y el 8 como candidatos del resto de casillas. Fig. 11. Líneas de candidatos. El 4 aparece como candidato únicamente en la fila central para la caja de la izquierda. Podemos eliminar el 4 como candidato en las casillas 4 y 7 de la fila central. 19 Líneas dobles: Dadas dos cajas ubicadas en la misma “línea de cajas”, si existe algún candidato que solo puede ubicarse en dos filas/columnas en ambas cajas, y dichas filas/columnas son las mismas para las dos cajas, entonces podemos eliminar dicho candidato del resto de casillas de tales filas/columnas. Líneas triples: Extensión de la técnica “Líneas dobles” a tres cajas y tres filas/columnas. Casillas forzadas: Elegimos aquellas casillas con dos candidatos posibles. Inicialmente, asumimos que el número definitivo de dicha casilla es uno de los dos candidatos, y en función de ello, aplicamos el resto de técnicas al Sudoku resultante de aplicar dicha hipótesis, almacenando qué números se fijan y qué candidatos se eliminan como consecuencia de la asunción que hemos realizado. A continuación repetimos el proceso eligiendo esta vez como número definitivo de la casilla el otro candidato. Finalmente, comparamos los números fijados y los candidatos eliminados en cada asunción: aquellos números fijados que coincidan en ambas asunciones pueden ser fijados de manera segura en la solución del Sudoku, y aquellos candidatos eliminados que coincidan en ambas asunciones pueden ser eliminados de manera segura en el proceso de resolución del Sudoku. Esta técnica es extensible a casillas con más de 2 candidatos siguiendo los mismos razonamientos. 3.3 Elección del conjunto de heurísticas a implementar Las limitaciones de la FPGA, tanto en lógica programable como en memoria, no permiten implementar todas las heurísticas descritas. Determinamos que la mejor manera de seleccionar el conjunto de heurísticas que serían finalmente implementadas en la versión HW, era implementar todas ellas Fig. 12. Líneas dobles. En las cajas central y derecha el 2 aparece como candidato únicamente en las filas superior e inferior. Podemos eliminar el 2 como candidato en la casilla 1 de la fila superior y las casillas 1 y 2 de la fila inferior. 20 en la versión SW y determinar experimentalmente qué heurísticas consiguen mejores resultados sobre los Sudokus de los benchmarks y precisan de recursos, tanto a nivel de lógica como de memoria necesarias, que no excedan los disponibles en la FPGA. La evaluación de las heurísticas sobre la versión SW reveló la extrema eficacia de las heurísticas "Candidatos únicos" y "Candidatos únicos ocultos". Además, estas heurísticas destacan por ser las que poseen una complejidad computacional más baja y por tener un coste de implementación bajo. Todo esto motivó su implementación en la versión HW. La siguiente heurística elegida, siguiendo los mismos criterios, fue "Pares escondidos". Finalmente añadimos "Tríos escondidos" y "Cuartetos escondidos" por sus buenos resultados en Sudokus de gran tamaño y alta dificultad y, fundamentalmente, debido a que reutilizan hardware de la implementación de "Pares escondidos", siendo así su coste de implementación menor que otras heurísticas de similar eficacia. Heurísticas en la versión HW Heurísticas en la versión SW Candidatos únicos Candidatos únicos ocultos Pares escondidos Tríos escondidos Cuartetos escondidos Candidatos únicos Candidatos únicos ocultos Pares escondidos Tríos escondidos Cuartetos escondidos Quintetos escondidos Pares pelados Tríos pelados Cuartetos pelados Quintetos pelados Líneas de candidatos Líneas dobles Líneas triples Casillas forzadas (para casillas con 2 y 3 candidatos) 3.4 Diseño del procesador El objetivo de las heurísticas es reducir el espacio de búsqueda hasta dejarlo asequible para ser resuelto mediante backtracking, o bien resolver el Sudoku mediante las mismas exclusivamente. Tabla 3. Enumeración de las heurísticas implementadas en las versiones SW y HW finales 21 3.4.1 Estrategia global El conjunto de heurísticas seleccionadas no garantiza la resolución de cualquier Sudoku. Necesitamos pues una estrategia híbrida consistente en la aplicación iterativa del conjunto de heurísticas hasta que no consigan reducir el espacio de búsqueda y posteriormente, si es necesario, aplicar backtracking sobre el Sudoku resultante de la aplicación de las heurísticas. El algoritmo propuesto en la figura 13 garantiza encontrar solución a cualquier Sudoku(2), pero no garantiza hacerlo en un tiempo igual o menor que el máximo indicado en las especificaciones del concurso. Este algoritmo aplica secuencialmente las heurísticas implementadas, ordenándolas según su coste computacional. En caso de éxito en la aplicación de una heurística, se vuelve a la heurística más simple que proceda(3). De este modo se aplican las heurísticas más complejas solo cuando las de menor complejidad dejan de conseguir resultados por sí mismas. Finalmente, en caso de que la heurísticas más compleja implementada no consiga resultados se procede a la búsqueda de la solución en el espacio de búsqueda resultante mediante backtracking. (2) El Sudoku propuesto debe ser correcto (3) Para las técnicas N-escondidos se vuelve a "Candidato único oculto" ya que la aplicación de N- escondidos nunca tendrá como resultado inmediato nuevos candidatos únicos 22 3.5 Detalles de implementación 3.5.1 Requisitos de memoria Todas las heurísticas se basan en la eliminación de candidatos, por lo tanto precisan conocer los candidatos de cada casilla. Almacenar los candidatos de una casilla requiere N2 bits, siendo N el orden del Sudoku. El coste de almacenamiento de los candidatos de cada casilla para un Sudoku será: N2 (filas) * N2 (columnas) * N2 (tamaño vector candidatos casilla) Esto representa una limitación a la hora de implementarlas, ya que, como se puede observar en la tabla 3, imposibilita alcanzar orden 12 y superiores. 1. Aplicar Candidato único Si se ha fijado algún número entonces Ir a 1; Si no Ir a 2; 2. Aplicar Candidato único oculto Si se ha fijado algún número entonces Ir a 1; Si no Ir a 3; 3. Aplicar Pares escondidos Si se ha eliminado algún candidato entonces Ir a 2; Si no Ir a 4; 4. Aplicar Tríos escondidos Si se ha eliminado algún candidato entonces Ir a 2; Si no Ir a 5; 5. Aplicar Cuartetos escondidos Si se ha eliminado algún candidato entonces Ir a 2; Si no Ir a 6; 6. Aplicar backtracking Fig. 13. Algoritmo de resolución mediante heurísticas y backtracking utilizado en la versión HW 23 3.5.2 Implementación de la memoria La implementación de las heurísticas requiere añadir una nueva memoria para almacenar los candidatos de cada casilla. Por cuestiones de eficiencia (obtener los candidatos de cada casilla en un ciclo de reloj, independientemente de la heurística en ejecución), añadimos una tercera memoria que almacena los números que faltan en cada fila, columna y caja. Así pues, tenemos tres memorias en esta versión: 1) Memoria para el Sudoku 2) Memoria para los candidatos de cada casilla 3) Memoria para los candidatos de cada fila, columna y caja La memoria 2 almacena la información resultante de la aplicación de las heurísticas N-escondidos . La memoria 3 almacena los candidatos de cada fila, columna y caja en función de los números fijados, y permite obtener los candidatos para cada casilla según este criterio. Orden Sudoku Coste almacenamiento candidatos Coste almacenamiento Sudoku Coste almacenamiento total 15 11.390.625 455.625 11.846.250 14 7.529.536 345.744 7.875.280 13 4.826.809 266.904 5.093.713 12 2.985.984 186.624 3.172.608 11 1.771.561 117.128 1.888.689 Tabla 4. Requisitos de memoria (en bits) para la implementación de heurísticas de eliminación de candidatos. La FPGA dispone de 2448 Kb de memoria, por lo que el diseño final queda limitado a orden 11. 24 3.5.3 Implementación de las heurísticas seleccionadas Candidato único: Para cada casilla, el evaluador examina su lista de candidatos en busca de casillas con un solo candidato. El evaluador determina que existe solo un candidato en caso de que el primer y el último candidato para la casilla coincidan. Candidato único oculto Para cada región del Sudoku, se examina el número de ocurrencias de cada candidato en busca de aquellos cuyo número de ocurrencias sea igual a uno. Se tiene un contador de apariciones para cada candidato y tres registros para cada candidato que almacenan fila columna y caja respectivamente. Aquellos contadores que tras examinar las listas de candidatos de cada casilla de una región contengan un uno indicaran que el candidato que corresponde a dicho contador se puede fijar en la casilla almacenada en los registros de posición correspondientes a dicho candidato. Fig. 14. Esquema hardware del evaluador que implementa la heurística “candidatos únicos”. 25 Par escondido: Para cada región del Sudoku, se examina el número de ocurrencias de cada candidato almacenándolas en contadores dispuestos para cada candidato. Se almacenan también las dos últimas posiciones en las cuales aparece cada candidato en los registros de posición. Posteriormente se comparan todas las duplas de candidatos en busca de aquellas cuyo número de apariciones para los dos candidatos sea dos y las posiciones de los dos candidatos sean las mismas. Aquellas casillas que cumplan estas condiciones contienen un par escondido. Fig. 15. Esquema de la implementación hardware de la heurística “candidato único oculto”. 32 5. Planificación En un principio tan solo planteamos llevar a cabo la implementación del diseño hardware, como se aprecia en la figura 15. El desarrollo final del proyecto incluyó el desarrollo en paralelo de una versión software y una fase de depuración del diseño hardware más prolongada de lo esperado (figura 16). Figura 17. Diagrama de Gantt de la planificación inicial del proyecto. Figura 18. Diagrama de Gantt del desarrollo real del proyecto 33 La dedicación en este periodo fue prácticamente completa con un total de 760 horas dedicadas al desarrollo de este proyecto. Como se puede ver en las figuras 17 y 18, pudimos cumplir el plazo final marcado en la planificación, el cual era imprescindible para participar en el concurso. También se puede observar como una de las tareas que inicialmente debería durar 2 semanas, acabó durando 10, debido a los problemas que encontramos durante la etapa de diseño, que eran imprevisibles a la hora de planificar.