AUTOMATIC WORD SEARCH PUZZLE SOLVER

Nikita Gautam
2017
BSc.CSIT
Semester 7
Downloads 8

Automatic Word Search Puzzle solver is an automated system for solving word search problems using Linear Search, Binary Search and Tries Algorithm. In order to generate solution of the provided puzzle image processing techniques namely, grayscale conversion, thresholding, dilation and contour detection were used to horizontally and vertically segment the puzzle image into equivalent individual character images. The segmented characters were then fed into the trained neural network. Neural network training was conducted using 26416 image data for 26 different alphabet letters (A-Z). Finally, the recognized data was modeled into an equivalent puzzle matrix form. Separation of train and test dataset into ratio of 8000:26416 was carried out for neural network training and testing, where the final accuracy obtained was 87.7625 % (solely for neural network only). Similarly, for generating solution by searching dictionary words, dictionary data was collected in a text file along with its description. This data was preprocessed and the final output was a word list of 36739 words. Number of possible word combinations for equivalent puzzle matrix in horizontal, vertical and diagonal direction was calculated. 10360 total calculated word combination for 15*15 letter matrix puzzle was obtained. This combination was tested with the collected dictionary data using linear search, binary search and tries algorithm. After evaluation of three algorithms for puzzle solution generation the time complexity for puzzle (15*15 letter grid puzzle) in ascending order were obtained as; tries, binary and linear. Hence, tries implementation was found more efficient in terms of time complexity for generating puzzle solution.

Automatic Word Search Puzzle Solver
Image Processing
Neural Network
Binary Search
Linear Search
Tries
Puzzle Matrix

Similar Projects