Sudoku is often considered 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 individuals the opportunity to explore and investigate several possibilities for solver implementations. Although at face value, solving Sudoku puzzles seems to be a self-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 backtrack through the puzzle, until a solution is reached.
The proposed architecture, which is shown in Figure 1, was coded in VHDL and synthesized using Xilinx ISE 14.7. The implementation was done on an Atlys development board from Digilent, containing a Xilinx XC6SLX45 FPGA. To test the solver, unsolved puzzles of varying difficulties were sent to the device via the RS-232 protocol, from a MATLAB user interface (refer to Figure 2). Upon solving the puzzle, the device can be prompted to send the solution and the timing result back to the computer, where they are displayed on the interface.
From the twenty-three puzzles that were tested, it was noticed that the solver performed very well for easy and medium puzzles. However, due to the nature of the searching algorithm, it took a significantly longer time to finish hard and ‘extreme’ puzzles, with some even becoming intractable. Comparing it to existing implementations [1]-[5], when the same puzzles were used, the solver performed better for the easy benchmark by an average of 8.5ms, and worse for the harder benchmark by an average of 12.3ms. Overall, the results were rather satisfactory since some improvements were made with respect to the solutions reported in literature, while still keeping a relatively simple solver.
References
[1] K. van Der Bok, M. Taouil, P. Afratis and I. Sourdis, “The TU Delft Sudoku Solver on FPGA,” International Conference on Field- Programmable Technology (FPT) 2009, pp. 526-529, 2009.
[2] P. Malakonakis, M. Smerdis, E. Sotiriades and A. Dollas, “An FPGA-Based Sudoku Solver based on Simulated Annealing Methods,” International Conference on Field-Programmable Technology (FPT) 2009, pp. 522-525, 2009.
[3] C. Gonzalez, J. Olivito and J. Resano, “An Initial Specific Processor for Sudoku Solving,” International Conference on Field- Programmable Technology (FPT) 2009, pp. 530-533, 2009.
[4] M. Dittrich, T. B. Preusser and R. G. Spallek, “Solving Sudokus through an Incidence Matrix on an FPGA,” International Conference on Field-Programmable Technology (FPT) 2010, pp. 465-469, 2010. [5] I. Skliarova, T. Vallejo and V. Sklyarov, “Solving Sudoku in Reconfigurable Hardware,” 8th International Conference on Computing and Networking Technology (INC, ICCIS and ICMIC) 2012, pp. 10-15, 2012.
Student: Keith George Ciantar
Supervisor: Dr Inġ. Owen Casha
Course: B.Sc. (Hons.) Computer Engineering