EVALUASI ALGORITMA RUNUT BALIK DAN SIMULATED ANNEALING PADA PERMAINAN SUDOKU

Abstrak

Sudoku is one of the popular puzzle games in many countries. How to solve this game is being the Non Polynomial Completeness problem. Because of that, a lot of research has been done to find the most effective algorithm completing Sudoku. This study presents the evaluation of algorithm in completing the Sudoku 2 x 2 and 3 x 3. The most common algorithm is brute force and backtracking. There is also simulated annealing algorithm. The evaluation is done by comparing the step of each algorithm to solve the Sudoku and also their running time. The result of this evaluation shows the differences of each algorithm characteristic in solving this Sudoku problem. By comparing the result of this study, the most effective algorithm can be chosen. Based on the test, concluded that the backtracking algorithm is more effective than the simulated annealing algorithm which the value reach 50%.