Application of Backtracking Algorithm with Recursive Method in Word Search Game

Abstract

The word search game is a puzzle game for finding words in the matrix, the words can be arranged horizontally, vertically or diagonally, the solving process in this word search game must find all the hidden words. Recursive backtracking algorithm can solve the game more effectively and efficiently because the problem-solving strategy only focuses on the solution. The methods used for data collection are library studies to collect relevant related information, word search game analysis that explains the rules and possible paths, and recursive backtracking algorithm that describes the steps and general scheme of the algorithm. This study explains the solution steps of applying the recursive backtracking algorithm, by referring to previous studies that used the iterative version of the backtracking algorithm and comparing these studies. The recursive and iterative versions of the backtracking algorithm have differences in code writing and memory allocation, as well as different execution time speeds depending on the complexity of the word being searched and the size of the matrix in the word search game