Implementation of a Sudoku puzzle solver on a FPGA

Abstract

Sudoku is often considered as a casual puzzle game, which is played as a pastime. From a scientific perspective, the Sudoku puzzle features certain characteristics that entail finding a non-trivial solution, while giving the opportunity to explore and investigate several possibilities for solver implementations. Althoughatfacevalue, solving Sudoku puzzles seems to beaself-contained problem, in reality it encompasses a lot of properties which are useful to many other domains. In this work, the design, implementation and evaluation of a hybrid Sudoku puzzle solver on a Field-Programmable Gate Array(FPGA) is presented. The proposed Sudoku puzzle solver follows the specifications of the competition of the 2009 International Conference on Field-Programmable Technology (FPT). The solver initially makes use of simple pen-and-paper solving techniques to reduce the number of possible values and prune the overall search space. Once this is complete, the solver then utilises the brute-force search algorithm (also known as depth-first search algorithm) to systematically guess and back track through the puzzle, until a solution is reached. The implementation and testing of the Sudoku puzzle solver were carried out on a Xilinx Spartan-6XC6SLX45FPGA.