Sudoku Solution with Backtracking Algorithm
Sudoku has a logic-based, N-row and N-column size, and the 1-N numbers are table-locating pseudo-words in the same row, same column and sub-square. Sudoku is a puzzle that opens minds of our day and is among the mind sports with the help of brainstorming. Sudoku is a kind of puzzle that has always attracted the attention of people, as it increases the curves of the brain, gives those different points of view, gives them problem solving ability and develops individuals on alternative solutions. It is the smallest Sudoku 4x4 dimension, just like Sudoku has thousands of derivations. At the same time, the Federation of World Intellect Games has decided to make the world Sudoku championship apart from the World Intellect Games Championship, which it has organized since 1992, together with 2006, and every year since then, a championship has been organized like this worldwide. Sudoku puzzle is an interesting puzzle for people as much as it found itself in the field of computer science as a study field. The aim of this work is to design a new algorithm for the Sudoku puzzle and to compare the performance of the designed algorithm with the recursive backtrack algorithm. In this study, a Sudoku puzzle with numbers from 1-9 with a 9-row and 9-column size was used. In the sequential solution algorithm developed for the Sudoku puzzle, the whole line, the column and the sub frame are traversed and one of the digits 1-9 is checked to see if the line, column and sub frame completes to the same 45, assigned. After the first control is made in this designed algorithm, as a second step, the probabilities of which digits may come to that square for each of the 81 squares are deduced. Among these possibilities, it is checked whether any number is used once in the row, column and sub frame, and if it is used once, it is assigned as the value belonging to that frame. If Sudoku has a single solution, then that solution is found. If more than one solution exists, the algorithm continues until one of the solutions is found. In this study, sequential solution algorithm developed for Sudoku puzzler was compared with recursive return algorithm and performance analysis was performed. The sequential solution algorithm is compared with the recursive backtrack algorithm in performance and a much faster solution is obtained. With this solution, sequential solution algorithms seem to be more efficient for Sudoku puzzler.
Keywords - Sudoku, Algorithm, Backtrack Algorithm, Recursion.