How can i optimize this recursive method
- by Tirdyr
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
