Identification of numbers and positions using MATLAB to solve Sudoku on FPGA

In this paper, we propose the digital detection and decryption of a sudoku puzzle using vision based techniques and subsequent solving of the puzzle in FPGA using brute force. The system can recognize any sudoku puzzle captured from a digital camera and after employing appropriate pre-processing algorithms which include adaptive thresholding, Hough Transform and geometric transformation, the digits are recognized using Optical Character Recognition (OCR), and based on their pixel locations in the image, they are stored in corresponding locations in the 9×9 matrix which is then further consigned to the FPGA for solution generation. Subsequently, the FPGA uses the 9×9 matrix to construct bitmaps for every row, column and block which are stored in the memory. The algorithm employed to solve the sudoku puzzle uses a brute force method, which fills the empty cells in a row wise manner and backtracks if a cell is encountered to which a digit cannot be assigned. The system was tested for various kinds of Sudoku puzzles, and proved to be capable in handling problems arising from non-uniform illumination, background noise and translation and was able to work at the maximum frequency of 353.61 MHz, while consuming 314 slices, 396 LUTs and 0.253 W in power.