Word search puzzles contain hidden words. We investigate a computer program written in the C# language that can solve this kind of puzzle, such as those given to children to keep them busy. In these word search puzzles, English words are hidden in any direction inside a grid of letters.
This C# algorithm article demonstrates a way to search for words in a block of letters.
Input puzzle cat dog ead Words found in this puzzle cat found [top] cod found [diagonal right] dog found [middle] toe found [diagonal left] god found [middle backwards] doc found [diagonal left backwards]
To start, this is the complete implementation of a program that solves these puzzles. It uses several dictionary collections and populates one with data from a text file containing a list of English words. An array is built from the input string, and then each square is searched in every direction using the word dictionary as a guide.
Word search program [C#]
using System;
using System.Collections.Generic;
using System.IO;
enum WordType : byte
{
FullWord,
PartialWord,
FullWordAndPartialWord
}
class Program
{
static Dictionary<string, WordType> _words = new Dictionary<string, WordType>(400000, StringComparer.Ordinal);
static Dictionary<string, bool> _found = new Dictionary<string, bool>(StringComparer.Ordinal);
const int _minLength = 3; // Minimum length of matching words.
const string _pattern = @"cat
dog
ead";
static void Main()
{
// Read in dictionary.
using (StreamReader reader = new StreamReader("enable1.txt"))
{
while (true)
{
string line = reader.ReadLine();
if (line == null)
{
break;
}
if (line.Length >= _minLength)
{
for (int i = 1; i <= line.Length; i++)
{
string substring = line.Substring(0, i);
WordType value;
if (_words.TryGetValue(substring, out value))
{
// If this is a full word.
if (i == line.Length)
{
// If only partial word is stored.
if (value == WordType.PartialWord)
{
// Upgrade type.
_words[substring] = WordType.FullWordAndPartialWord;
}
}
else
{
// If not a full word and only partial word is stored.
if (value == WordType.FullWord)
{
_words[substring] = WordType.FullWordAndPartialWord;
}
}
}
else
{
// If this is a full word.
if (i == line.Length)
{
_words.Add(substring, WordType.FullWord);
}
else
{
_words.Add(substring, WordType.PartialWord);
}
}
}
}
}
}
Console.WriteLine("[Read completed]");
Console.ReadLine();
// Write pattern.
Console.WriteLine(_pattern);
Console.WriteLine();
// Split on newlines.
string[] lines = _pattern.Split(new char[] { '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries);
// Put into 2D array.
int height = lines.Length;
int width = lines[0].Length;
char[,] array = new char[height, width];
for (int i = 0; i < width; i++)
{
for (int a = 0; a < height; a++)
{
array[a, i] = lines[a][i];
}
}
// Start at each square in the 2D array.
for (int i = 0; i < width; i++)
{
for (int a = 0; a < height; a++)
{
// Search all directions.
for (int d = 0; d < 8; d++)
{
SearchAt(array, i, a, width, height, "", d);
}
}
}
Console.WriteLine("[Search completed]");
Console.ReadLine();
}
static void SearchAt(char[,] array,
int i,
int a,
int width,
int height,
string build,
int direction)
{
// Don't go past around array bounds.
if (i >= width ||
i < 0 ||
a >= height ||
a < 0)
{
return;
}
// Get letter.
char letter = array[a, i];
// Append.
string pass = build + letter;
// See if full word.
WordType value;
if (_words.TryGetValue(pass, out value))
{
// Handle all full words.
if (value == WordType.FullWord ||
value == WordType.FullWordAndPartialWord)
{
// Don't display same word twice.
if (!_found.ContainsKey(pass))
{
Console.WriteLine("{0} found", pass);
_found.Add(pass, true);
}
}
// Handle all partial words.
if (value == WordType.PartialWord ||
value == WordType.FullWordAndPartialWord)
{
// Continue in one direction only.
switch (direction)
{
case 0:
SearchAt(array, i + 1, a, width, height, pass, direction);
break;
case 1:
SearchAt(array, i, a + 1, width, height, pass, direction);
break;
case 2:
SearchAt(array, i + 1, a + 1, width, height, pass, direction);
break;
case 3:
SearchAt(array, i - 1, a, width, height, pass, direction);
break;
case 4:
SearchAt(array, i, a - 1, width, height, pass, direction);
break;
case 5:
SearchAt(array, i - 1, a - 1, width, height, pass, direction);
break;
case 6:
SearchAt(array, i - 1, a + 1, width, height, pass, direction);
break;
case 7:
SearchAt(array, i + 1, a - 1, width, height, pass, direction);
break;
}
}
}
}
}
Output
[Read completed]
cat
dog
ead
cat found
cod found
dog found
toe found
god found
doc found
[Search completed]
How is the words Dictionary used? The words Dictionary is built up from the list of words on the disk. Each substring is taken from the word from the first character to further characters. So the word "man" has the "m", "ma", and "man" encoded into the dictionary. As the dictionary is built, the FullWord, PartialWord, and FullWordAndPartialWord enums are managed.
How does the search start? The search starts by looping over each element in the two-dimensional array of letters we built. Then, the eight directions that each word can continue in are further scanned. The SearchAt method is where a search at a square on the grid continues.
How does SearchAt work? The SearchAt method is recursive, which means it calls itself. It first detects invalid coordinates and returns early in this case. It takes the specified letter and builds up a new string with that letter at the end. If that string is found in the Dictionary, we use additional logic to determine how to proceed.
Full words. In SearchAt, then, we check the built-up string to see if it is a full word. If it is, we display it unless we have already found it. No recursion is necessary on full words.
Partial words. For partial words in SearchAt, we determine which direction we are searching in. The directions are restricted because we don't want twisted words to count. The direction integer is translated here into a coordinate shift on the grid, and then SearchAt is recursively called to continue searching.
More details. The program uses a lot of knowledge from other articles on Dot Net Perls. See the articles on StringComparer.Ordinal, the Dictionary type, StreamReader, enums, TryGetValue, Split, WriteLine, ReadLine, 2D arrays, recursion, and the switch statement.
Dictionary StringComparer Tip Dictionary Examples Using StreamReader Enum Examples TryGetValue Method Split String Examples Console.WriteLine Console.ReadLine Tips 2D Array Examples Recursion Example Switch StatementText file. It is important you download the enable1.txt file for use in this program. The enable1.txt file is available from the obsolete dotnetperls-controls project where it has been downloaded 156,000 times. It is 1.8 megabytes.
enable1.txtIn this example, we enable multidirectional searching: as words are searched for in a puzzle, we can change direction to get each letter. With the complete code here, we explore a recursive searching algorithm guided by a hashtable.
Input puzzle abc def ghi Words found in the puzzle abed found [top left] defi found [middle] bead found [top left] bade found [top left] badge found [left] hied found [bottom] head found [bottom]
This program was adapted from the previous word search algorithm developed for this site. There are some significant changes: the input puzzle is read in from the console each time; a two-dimensional array indicating which squares have been used is employed; and the search recursion is not restricted to any direction.
Program that implements multidirectional word search [C#]
using System;
using System.Collections.Generic;
using System.IO;
enum WordType : byte
{
FullWord,
PartialWord,
FullWordAndPartialWord
}
class Program
{
static Dictionary<string, WordType> _words = new Dictionary<string, WordType>(400000);
static Dictionary<string, bool> _found = new Dictionary<string, bool>();
const int _minLength = 4; // Minimum length of matching words.
static string Input()
{
Console.WriteLine("Input lines of text and then a blank line.");
string total = "";
while (true)
{
// Get line.
string line = Console.ReadLine();
if (string.IsNullOrWhiteSpace(line))
{
return total.Trim();
}
total += line.Trim();
total += "\r\n";
}
}
static void Main()
{
// Read in dictionary.
using (StreamReader reader = new StreamReader("enable1.txt"))
{
while (true)
{
string line = reader.ReadLine();
if (line == null)
{
break;
}
if (line.Length >= _minLength)
{
for (int i = 1; i <= line.Length; i++)
{
string substring = line.Substring(0, i);
WordType value;
if (_words.TryGetValue(substring, out value))
{
// If this is a full word.
if (i == line.Length)
{
// If only partial word is stored.
if (value == WordType.PartialWord)
{
// Upgrade type.
_words[substring] = WordType.FullWordAndPartialWord;
}
}
else
{
// If not a full word and only partial word is stored.
if (value == WordType.FullWord)
{
_words[substring] = WordType.FullWordAndPartialWord;
}
}
}
else
{
// If this is a full word.
if (i == line.Length)
{
_words.Add(substring, WordType.FullWord);
}
else
{
_words.Add(substring, WordType.PartialWord);
}
}
}
}
}
}
// Get pattern.
string pattern = Input();
// Write pattern.
Console.WriteLine(pattern);
Console.WriteLine();
// Split on newlines.
string[] lines = pattern.Split(new char[] { '\r', '\n' },
StringSplitOptions.RemoveEmptyEntries);
// Put into 2D array.
int height = lines.Length;
int width = lines[0].Length;
char[,] array = new char[height, width];
for (int i = 0; i < width; i++)
{
for (int a = 0; a < height; a++)
{
array[a, i] = lines[a][i];
}
}
// Create empty covered array.
bool[,] covered = new bool[height, width];
// Start at each square in the 2D array.
for (int i = 0; i < width; i++)
{
for (int a = 0; a < height; a++)
{
Search(array, i, a, width, height, "", covered);
}
}
}
static void Search(char[,] array,
int i,
int a,
int width,
int height,
string build,
bool[,] covered)
{
// Don't go past around array bounds.
if (i >= width ||
i < 0 ||
a >= height ||
a < 0)
{
return;
}
// Don't deal with already covered squares.
if (covered[a, i])
{
return;
}
// Get letter.
char letter = array[a, i];
// Append.
string pass = build + letter;
// See if full word.
WordType value;
if (_words.TryGetValue(pass, out value))
{
// Handle all full words.
if (value == WordType.FullWord ||
value == WordType.FullWordAndPartialWord)
{
// Don't display same word twice.
if (!_found.ContainsKey(pass))
{
Console.WriteLine("{0} found", pass);
_found.Add(pass, true);
}
}
// Handle all partial words.
if (value == WordType.PartialWord ||
value == WordType.FullWordAndPartialWord)
{
// Copy covered array.
bool[,] cov = new bool[height, width];
for (int i2 = 0; i2 < width; i2++)
{
for (int a2 = 0; a2 < height; a2++)
{
cov[a2, i2] = covered[a2, i2];
}
}
// Set this current square as covered.
cov[a, i] = true;
// Continue in all directions. [8]
Search(array, i + 1, a, width, height, pass, cov);
Search(array, i, a + 1, width, height, pass, cov);
Search(array, i + 1, a + 1, width, height, pass, cov);
Search(array, i - 1, a, width, height, pass, cov);
Search(array, i, a - 1, width, height, pass, cov);
Search(array, i - 1, a - 1, width, height, pass, cov);
Search(array, i - 1, a + 1, width, height, pass, cov);
Search(array, i + 1, a - 1, width, height, pass, cov);
}
}
}
}
Output
Input lines of text and then a blank line.
abc
def
ghi
abc
def
ghi
abed found
defi found
bead found
bade found
badge found
hied found
head found
Description of Search. The Search method is a recursive method: it calls itself. It can call itself eight times on each call; this is to go in every possible direction from a single square. At the start of Search, we have some bounds checking logic. Then, we check the covered array to make sure a letter has not already been used.
Covered array. The algorithm uses an array of booleans; this indicates what squares have been used already in the search path. The array must be copied each time it is changed. At the start of Search, we see if the current square is already covered. If we did not copy the covered array, the algorithm would fail because previous search paths would have covered squares.
Tip: We looked at program that recursively searches for known patterns in a multidirectional array. Mainly used as a programming exercise, it draws upon some important concepts, including recursion and constraining the search path.
Unless you are making some sort of game, what use is this sort of exercise? As a programmer, you do not get to write recursive search algorithms very often. Recursion is one of the most fascinating topics in computer science. It can be used to solve problems of staggering complexity.
This algorithm is recursive and would continue infinitely except it is constrained by the data in the Dictionary. In other words, it only continues so long as it is finding correct prefixes to words. This is an example of how searching algorithms can be guided by a separate data structure.
With this program, you can search for and list all the words embedded in word search puzzles. The hard part is inputting the text file into the program. Further changes to this program could make the pattern of letters read in from a text file. The implementation here is also wildly inefficient; the most efficient representation of the word dictionary would be a DAWG structure. Finally, programming game algorithms is one of the best ways to learn complex programming techniques.
Directed Acyclic Word Graph Algorithms