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
