An Introduction

Designing an algorithm to solve word search puzzles is not exactly a difficult task. As any good programmer knows, however, an easy or simple solution isn’t always a good one. After all, the easy solution could be wasting valuable CPU cycles. Luckily for a word search, the only guaranteed place cycles can be wasted – in any given algorithm – is in comparing words against strings too small to contain the word.

Simple problems make prime candidates for learning advanced techniques.

Description

This project was given as a college assignment in Data Structures. The only requirement was to create a program that could solve any word search puzzle, and not suck at it. With that being said, I thought an algorithm dealing with string comparisons was the perfect opportunity to learn about parallel algorithms.

My algorithm loads a file containing a puzzle and its specifications. The file is formatted xypuzzle{word1,word2,wordN}, x and y are both 8-bit binary values. The puzzle section is laid out row1row2rowN with no delimiter, and not spacing. Which makes the X and Y values very important to reading the file. After the file gets loaded, the puzzle is broken up into strings; that is the puzzle gets scanned horizontally, vertically, and diagonally. There are two pairs of scans, each pair has two directions which are perpendicular to one another. I didn’t need to scan 8 directions because I could make the backward scanning part of the comparisons; I mean, since it was a data structures class after all why not have less data. After all the strings (ie. the search areas) were constructed the algorithm began comparing search words against search areas.

Search areas were pooled together according to their lengths, so any search area 15 characters long would be pooled with all the others 15 characters long. It was also necessary to save the starting coordinates of each search area with the corresponding string. Threads were spawned to compare every search word against every pool of search areas of equal or greater length. I wasn’t focused greatly on efficiency, so I couldn’t tell you if my methodology for spawning threads was the best. What I can say, is that most threads ended immediately after beginning.

Objectives

• Load a Word Search Puzzle File
• Solve the Word Search Puzzle
• Learn to create a Parallel Algorithm

Highlights

Successes

• Creating a generic Scan method. This is notable, because in order to perform any complete puzzle scans for any given direction there are a handful of things needed. The scan function needs to know what edge coordinates to start and end on. It needs to increment the string starting coordinates correctly (ie. around the edge of the puzzle), which is a non-trivial task for diagonal scans. Lastly, the scanner needs to know if a string is finished (ie. whether it made it to the opposite size of the puzzle). All the scans used the same IO, so I felt it was a good idea to parameterize the logic used to scan. This was a big help when I was debugging the logic for the diagonal scans.
• Displaying the search results. I learned how to extract information from a threaded function using futures and promises. That data expressed the coordinates of lower-bound letter in the search word according to its location in the search area. Calculating this required pairing the search area string with the coordinates where it began, before passing it along to a thread; this ended up becoming a new data structure.

Challenges

• Divining a way to show the location of words. Initially I got the algorithm up and running with only string comparisons, I consciously avoided thinking about how I would determine word locations in the puzzle. After I knew the algorithm could find words, I went back and refactored a number of things so that the algorithm could return coordinates.
• Understanding futures and promises was the biggest challenge I faced; I simply couldn’t get it right. I could get the syntaxes ‘correct’ or enough to compile, but no matter what I did I was unable to retrieve the results from my threads. I figured out, eventually, all I needed to do was use std::move on the promise.

Results

While I am still not sure if my algorithm is in its most efficient form, I do know that it works. More than working, it works well and doesn’t waste CPU cycles. In conclusion the project was a success because I accomplished all of my objectives.