Hi there.
I'm trying to make a word puzzle game, and for that i'm using a recursive method to find all possible words in the given letters.
The letters is in a 4x4
board.
Like this:
ABCD
EFGH
HIJK
LMNO
The recursive method is called inside this loop:
for (int y = 0; y < width; y++)
{
for (int x = 0; x < height; x++)
{
myScabble.Search(letters, y, x, width, height, "", covered, t);
}
}
letters is a 2D array
of chars.
y & x is ints that shows where in the
board
width & height is also int, that tells the dimensions
of the
board
"" is the string we are trying to make (the word)
covered is an array
of bools, to check if we allready used that square.
t is a List (wich contains all the words to check against).
The recursive method that need optimizing:
public void Search(char[,] letters, int y, int x, int width, int height, string build, bool[,] covered, List<aWord> tt)
{
// Dont get outside the bounds
if (y >= width || y < 0 || x >= height || x < 0)
{
return;
}
// Dont deal with allrady covered squares
if (covered[x, y])
{
return;
}
// Get Letter
char letter = letters[x, y];
// Append
string
pass = build + letter;
// check if its a possibel word
//List<aWord> t = myWords.aWord.Where(w => w.word.StartsWith(pass)).ToList();
List<aWord> t = tt.Where(w => w.word.StartsWith(pass)).ToList();
// check if the list is emphty
if (t.Count < 10 && t.Count != 0)
{
//stop point
}
if (t.Count == 0)
{
return;
}
// Check if its a complete word.
if (t[0].word == pass)
{
//check if its allrdy present in the _found dictinary
if (!_found.ContainsKey(pass))
{
//if not add the word to the dictionary
_found.Add(pass, true);
}
}
// Check to see if there is more than 1 more that matches string
pass
// ie. are there more words to find.
if (t.Count > 1)
{
// make a copy
of the covered array
bool[,] cov = new bool[height, width];
for (int i = 0; i < width; i++)
{
for (int a = 0; a < height; a++)
{
cov[a, i] = covered[a, i];
}
}
// Set the current square as covered.
cov[x, y] = true;
// Continue in all 8 directions.
Search(letters, y + 1, x, width, height,
pass, cov, t);
Search(letters, y, x + 1, width, height,
pass, cov, t);
Search(letters, y + 1, x + 1, width, height,
pass, cov, t);
Search(letters, y - 1, x, width, height,
pass, cov, t);
Search(letters, y, x - 1, width, height,
pass, cov, t);
Search(letters, y - 1, x - 1, width, height,
pass, cov, t);
Search(letters, y - 1, x + 1, width, height,
pass, cov, t);
Search(letters, y + 1, x - 1, width, height,
pass, cov, t);
}
}
The code works as i expected it to do, however it is very slow.. it takes about 2 mins to find the words.
EDIT: i clarified that the letters
array is 2D
