Implementasi Algoritma Best First Search Untuk Melakukan Penyelesaian Game Sudoku

Abstract

The problem in this research is that the Sudoku puzzle game is difficult to solve because it is included in the NP-complete problem, so it cannot be solved at the same time. Until now, many programmers are looking for the right algorithm to solve this puzzle. One way to solve this game is to use the best first search algorithm. This algorithm is an improvement of the Brute Force algorithm, where solutions can be found with fewer searches and can find solutions to problems more efficiently because there is no need to check all possible solutions. Only searches that lead to solutions need to be considered. The results of this study are the application of the best first search method in the sudoku game and determine the performance of the best first search method in the sudoku game. This research was built using Unity 3D software with the C# programming language and then using the unified modeling language as the flow of the diagram in the Sudoku game.

Keywords: Sudoku, algorithm, BFS