An initial specific processor for Sudoku solving

In this article, we present a design of a Sudoku solver submitted to the FPT Design Competition. Using only the on-chip resources of a XC2VP30 Virtex-II Pro FPGA we have designed a specific processor that can solve Sudokus from order 3 to 11. This processor applies a Branch&Bound approach to explore the solution space. However, this solution space is too big, and frequently the time needed to solve the Sudokus is excessive. To attempt to improve the design we have implemented an equivalent software version, and add several heuristics that reduce the solution space to it. The results have shown that these heuristics can drastically speedup the search. Hence we have included a few of them in the processor: Singles, Hidden Singles, Hidden Pairs, Hidden Triplets and Hidden Quartets that are well-known in the Sudokus literature. This design can still be improved by including other heuristics like Locked Candidates or Naked Candidates. Moreover, it is possible to extend the design for larger Sudokus since all the modules are customizable, but since the on-chip memory resources are very limited, it would be needed to use an external DDR RAM memory.