Solving Sudokus through an incidence matrix on an FPGA

This paper presents an implementation to solve Exact Cover Problems on FPGAs intending to speed up their computation. The Exact Cover Problem and the basic solving technique using an incidence matrix are introduced. The paper shows an approch on how to modify the data structure and the solving algorithm to allow a memory-efficient implementation on FPGA-devices. The architecture was implemented to solve Sudoku puzzles of an order between 3 and 15. The computation times of design are compared to several other hardware solvers and to state-of-the-art SAT solvers in software. A design, adapted to the rules of the FPT'09 design competition, solves the benchmark puzzles faster than the participating teams but still performs poorly in comparison with the software results. Thus, the paper also takes a critical look on opportunities to speed up Exact Cover Solving by using hardware implementations in general.