A further enhancement of backtracking algorithm to be used in Sudoku Solver

ABSTRACT: Sudoku is a popular and logic game composed of digits from 1 to 9. The modern Sudoku puzzle was designed by a 74-year old retired Architect from Indiana, named Howard Garns around 1979. The typical Sudoku board has a 9 rows by 9 columns, building 81 cells with 3 sub boxes. The game level varies on the puzzle’s difficulty. The greater the number of clues or the recognized digits, the easier it for the user to solve. The researchers study one of the algorithms used in Sudoku Solver which is the Backtracking Algorithm. It is the algorithm that is used in Sudoku Solver which is the Backtracking Algorithm. It is the algorithms used in most of the Sudoku solver. While studying the said algorithm, researchers found some weak points that needs to be enhanced. The researchers improved the Backtracking algorithm to be used in a Sudoku Solver. The study added some enhancements in address to the three major drawbacks of the existing algorithm. The first problem that the researchers found is that there is unnecessary process under the checking part before filling the number in the cell. Second, the researchers noticed that the existing algorithm can only provide one solution. And lastly, the existing algorithm cannot determine the number of possible solutions that a given puzzle can have. The objectives of this study is to remove the unnecessary process under the checking part so that there will be lesser number of loops and faster solving time. The second is to show more than one solution of the puzzle using random selection of unmarked values. And lastly, to determine the number of possible solutions based on the number and location of given hints. The researchers used Descriptive Research Method and Random Sampling Technique that helped them gather essential information about the backtracking algorithm. Through conducting survey and with adequate interpretation of results, the researchers were able to collect data and identify the advantages and disadvantages of the existing algorithm and used it as their basis in defining the statement of the problems and objectives of the study. The researchers now used the enhanced algorithm in the Sudoku solver and they proved that the enhanced algorithm is much better than the existing because the enhanced algorithm can now produce more than one solution for a given puzzle, it can determine the number of possible solution for a given puzzle, it can determine the number of possible solution/s a Sudoku puzzle can have and also the number of loops is now lesser and the solving time is faster compared to the existing algorithm. After studying, researchers recommend to show all of the possible solutions in a given puzzle. Nest is by using random starting cell in filling the number in a specific cell. And lastly to make a mobile application of a Sudoku Solver having multiple solutions per puzzle. These recommendations are offered for future research in the filed of Sudoku Solving.

Filipiniana