TheDeveloperBlog.com
C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML
C# Word Search Algorithm
This C# algorithm article demonstrates a way to search for words in a block of letters.Word search puzzles contain hidden words.
We investigate a computer program that solves this kind of puzzle, such as those given to children to keep them busy.
English words are hidden in any direction inside a grid 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]
Example. 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.
And: 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.
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]
Description. 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 substrings "m", "ma", and man encoded into the dictionary.
And: As the dictionary is built, the FullWord, PartialWord, and FullWordAndPartialWord enums are managed.
The search starts by looping over each element in the 2D array of letters we built. Then, the eight directions that each word can continue in are further scanned. SearchAt is where a search at a square on the grid continues.
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.
And: 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.
For partial words in SearchAt, we determine the search direction. The directions are restricted. The direction int is translated into a coordinate shift on the grid. Then SearchAt is recursively called to continue searching.
Note: The program uses a lot of knowledge from other articles on Dot Net Perls. Please see the relevant articles.
Dictionary StringComparerStreamReaderEnumTryGetValueSplitConsole.WriteLineConsole.ReadLine2D ArraySwitch
Text file. It is important you download the enable1.txt file for use in this program. This text file is available from the obsolete TheDeveloperBlog-controls project where it has been downloaded 156,000 times. It is 1.8 megabytes.
Multidirectional. In 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 2 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]
There are some significant changes in this program. The input puzzle is read in from the console each time. It uses a 2D array indicating which squares have been used. And the search is not restricted to any direction.
C# program that implements multidirectional word search
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
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.
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.
Info: If we did not copy the covered array, the algorithm would fail because previous search paths would have covered squares.
Summary. With this program, we 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.
Caution: The implementation here is 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.