Implementation of a sudoku puzzle solver on a FPGA

Abstract

In this paper, the design, implementation and evaluation of a hybrid Sudoku puzzle solver on a Field-Programmable Gate Array (FPGA) is presented. The solver initially makes use of pen-and-paper solving techniques to reduce the number of possible values and prune the overall search space. Once this process is complete, the solver then utilizes a depth-first search algorithm to systematically guess and backtrack through the puzzle, until a solution is reached. This work strived to implement a solver with minimal area utilization while maintaining simplicity and still achieving adequate performance. The implementation and the testing of the Sudoku puzzle solver were carried out on a Xilinx Spartan-6 XC6SLX45 FPGA.