Solving sudoku puzzle with parallel depth-first-search method based on the list of queues data structure

The sudoku puzzle, an NP-Complete game, is a puzzle that is highly popular around the world. The intensity of the interest in the sudoku has resulted in the first championship being held in 2006. Sudokus can be in different levels of difficulty depending on the number of sequences and the number of digits used. Sudoku puzzles at easy levels can be solved with a classic paper-pencil. On the other hand, trial-and-error methods have been developed for puzzles in different levels of difficulty. The aim of this study was to solve sudoku puzzles by using the parallel depth-first-search method based on the list of queues data structure. Different numbers of threads and parameters were tested in parallelling process. Optimal thread and parameters were examined. The parallel depth-first-search method based on the list of queues data structure was compared with the traditional depth-first-search search algorithm. Two sudoku puzzles were used in each of two different levels of difficulty in the study. Each sudoku puzzle was solved ten times and analyses were performed by taking the averages of solution. As a result of the experiments, the parallel depth-first-search method based on the list of queues data structure was found to solve sudokus faster than the traditional depth-first-search algorithm with a certain number of threads and parameters.