Solving Computationally Intensive Problems in Reconfigurable Hardware: A Case Study
In this paper, the authors explore the effectiveness of solution of computationally intensive problems in FPGA (Field-Programmable Gate Array) on an example of Sudoku game. Three different Sudoku solvers have been implemented and tested on a low-cost FPGA of Xilinx Spartan-3E family. The first solver is only able to deal with simple puzzles with reasoning, i.e. without search. The second solver applies breadth-first search algorithm and therefore has virtually no limitation on the type of puzzles which are solvable. They prove that despite the serial nature of implemented backtracking search algorithms, parallelism can be used efficiently.