Sudoku em FPGA

Abstract

Este trabalho, desenvolvido no âmbito dos sistemas reconfiguráveis, tem como objetivo a implementação de um solucionador de puzzles Sudoku, quer em software quer em hardware, tentando minimizar o seu tempo de solução. Deste modo, foram desenvolvidos três solucionadores: Simples, apenas capaz de resolver puzzles simples, Tentativa e Erro, que implementa um algoritmo de Breadth-First Search para solucionar puzzles mais complexos, e, por fim, o solucionador Tentativa e Erro com capacidade para processamento paralelo, também este capaz de solucionar puzzles mais complexos. Todos estes solucionadores foram implementados e testados numa FPGA da família Spartan-3E da Xilinx, usando, para isso, uma placa de prototipagem da Digilent. Os resultados obtidos foram comparados entre as várias implementações abordadas, assim como com outros solucionadores existentes.

This work, developed in the context of reconfigurable systems, has as an objective the implementation of a Sudoku solver, both in software and hardware, and attempting to minimize its solution time. Thus, three solvers were developed: Simple, only able to solve simple puzzles, Trial and Error, which implements a Breadth-First Search algorithm, being able to solve more complex puzzles, and, finally, the Trial and Error solver with the possibility of parallel processing, being also able to solve complex puzzles. All these solvers were implemented and tested on an FPGA of Xilinx Spartan- -3E family, using for this purpose a prototyping board from Digilent. The results were compared between the various implementations, as well as with other state-of-the-art solvers.