Wordseach Solver (& Generator)

(Version 3)

What is This?

It a simple program to solve wordsearch puzzles. Given a word grid and a list of target words to look to for, it will find any of those words that are in the grid and list were they are (this can be considered cheating :-) ). It will also separately list all the strings that are in grid whether or not they are in the target list.

It can also find words that the puzzle creator did not intend to hide in the puzzle by feeding it a dictionary as the list of target words. It was for this purpose that I originally wrote the program.

To use it to generate (rather pathetic) wordsearch puzzles, feed it a grid of random letters and a dictionary. It will report all the words from the dictionary that happen, by chance, to be in the grid. You can pretend that you spent ages creating that particular grid to hide those particular words in (this can also be considered cheating :-) ).

System Requirements

A Perl interpreter.

How to Use It

To Search for words in a Wordsearch Puzzle

Input:

Put the wordsearch grid in a plain text file called Wordsearch.txt. No spaces between letters in a row. Rows separated by linebreaks. No blank lines between rows.
Put the list of words to find in a file called Dictionary.txt separated by linebreaks.

Run the program WordsearchSolver.pl with the current working directory being the one containing Wordsearch.txt & Dictionary.txt.

Output:

All found strings in the grid will be put in a file called Strings.txt.
All found words (i.e. strings that were in the dictionary) in the grid that were in the dictionary will also be put in a file called Words.txt.

Warning: it overwrites the files Strings.txt & Words.txt in the current working directory.

To Generate a Random Letter Grid

Run the trivial RandomLetterSquareGenerator.pl program with one parameter, the width of the grid. Note that it uses English letter frequencies so you may want to change those in the source code before running if your target language is not English.

Where to Get Word Lists from

The ENABLE (definitive) & YAWL (even longer) word lists for the game Scrabble are convenient. For more colloquial words I used some of the Elite Sys word lists (which were made for dictionary attacks on common passwords but also have benign uses such as dictionary attacks on wordsearch puzzles).

Remember when downloading plain text files to check they have the line break format suited to your computer (currently carriage-return + line-feed for Microsoft but just line-feed for Linux, Apple, Android & iOS) and convert if necessary.

It will slightly save time for multiple runs of the program if the word list is sorted alphabetically so that the program does not need to sort it each time. Similarly it saves time if the list does not include duplicates. To combine & sort lists in GNU/Linux/Unix/Bash simply use cat <names-of-lists> | sort | uniq > <name-of-combined-list>.

Example Puzzle Search

The puzzle I originally wrote this for was a 14 x 14 grid with a target word list (which were answers to questions rather than a customary plain text word list) of 40 words.

The program found 7216 unique strings. When these were checked for English words with various word lists it found:

Word List	Words Found
The intended 40 target words	40
ENABLE (173528 words)	268
YAWL (264061 words)	326
YAWL + 35856 words from Elite Sys	421
YAWL + 35856 words from Elite Sys + 14640 UK place names	434

The search took just 2.5 s (AS Perl 5.6.1, Microsoft Windows 2000, 512 MB memory, 1.3 GHz Athalon CPU). If the dictionary needed sorting (I simply reversed it for this test), this was still only increased to 3 s.

Example Puzzle Generation

Averages over 6 random grids of 14 x 14 letters and searching for English words therein found 201±19 words per grid.

Making the letter frequencies match those of typical English text improved it dramatically to 337±23 words.

However this is still only three quarters of the number found in the human generated grid (this is because the human created grid had 40 words purposefully included and those in turn included substrings that were more likely to be valid words than random letters are). More seriously deficient compared to a more intelligently constructed grid was the type of words. Most of the words found were very short with very few of five letters or more. (And the disproportionate number of four-letter words in English that are rude means that one needs to vet the word list before publishing :-) .)

Increasing the random grids to 40 x 40 letters increased the number of words found but not in proportion to the number of letters (only to 1383±60) & the domination of short words showed up even worse.

Known Deficiencies

It stores everything in memory whilst working which is very memory-inefficient (fortunately PC memories are now so large that this should not be a problem for reasonable size grids).
The method of generating wordsearch puzzles produces pretty pathetic puzzles (but then it was not the original intention of the program, just an almost free additional use).