How can I find the valid words in a grid of characters?

Question

I am creating a game similar to Tetris, with two main differences: the screen already begins filled with tiles (like in Puzzle Quest for Nintendo DS and PC) and each individual tile has a letter in it. The player's objective is to eliminate tiles by forming valid words with them. Words are formed by placing letters next to each other, in any direction, except diagonally.

The player can move an entire row of tiles to the left or to the right or an entire column of tiles up or down, for as many spaces as he desires (if the movement of a row/column surpasses the limits of the board, the letter that crosses the limit will "cycle", appearing at the other end of the row/column). After the player's action, the game should check the entire board to look for valid words and remove the letters that form those words from the board. The letters above those that were removed will fall down in the place of those letters that were removed and new letters will drop from the top of the screen until the board is filled up again.

I have already written a linear algorithm that, given a sequence of characters, determines if it is a valid english word. The problem I am having is: how can I check for valid words on the board? Is brute force the only way? Testing all possible combinations from the board to see if they are valid is very slow, even for a small (5x5) board. Any help will be very appreciated, thanks!

Answer 1

Brute force is not the only way.

Solving your game board is similar to solving a Boggle board, except simpler. You want to check every tile in the board, looking to see if there are any words that can be made along the appropriate directions.

You'd still like to refine your search space further so you don't bother searching along a direction if you know you can't make a word. For example, if you find two qs in a row, you should abort. To that end, you'll want some kind of data structure that allows you to tell if a given set of characters is a prefix of a valid word. For this, you can use a trie, or prefix tree; a useful data structure when solving problems like this.

A prefix tree is a hierarchical node-based structure, where every node represents some prefix of its children, and the leaf nodes (generally) represent the final values. For example, if your dictionary of valid words contains "cat," "car," and "cell," a trie might look like:

    0        The root of the trie is the empty string here, although you 
    |        can implement the structure differently if you want.
    c
   / \ 
  a   e
 / \   \
t  r    l
         \
          l

Thus, begin by filling a prefix tree with every valid word in your game.

The actual process of finding valid words on the board at any given time will involve starting a recursive search from each tile on the board. Because each search through the board space starting at some given tile is independent, these can be parallelized if needed. As you search, you "follow" the prefix tree based on the value of the letter in the direction you are searching.

You will eventually reach a point where none of the surrounding letters are children of your current prefix tree node. When you reach that point, if it is also true that the current node is a leaf, you have found a valid word. Otherwise, you have not found a valid word and you may abort the search.

Example code and a discussion of this technique (and others, such as a dynamic programming solution that can be even faster by "inverting" the search space after a fashion) can be found on this fellow's blog here; he discusses solving Boggle, but adapting the solutions to your game is more or less a matter of changing which directions you allow searching to occur in.

Answer 2

You might have tried this, already implemented this, maybe better accompanied by another answer, etc. But I didn't see them mentioned (yet), so here it is:

You can discard a lot of the checks by keeping track of what changed and what didn't. For example:

On a 5x5 field, A vertical word is found on base of the third column,
All the rows change. However, the first, second, fourth, and fifth,
columns do not change, so you dont need to worry about them (the third did change.)

On a 5x5 field, A 3 letter word is found horizontally on row 2, column 3, to column 5.
So you need to check row 1 and 2 (row 1 because the words on that one
fell down and where replaced), as-well as columns 3, 4, and 5.

or, in psudo code

// update the board

// and check
if (vertical_word)
{
    check(updated_column)

    for (i in range 0 to updated_row_base)
        check(i)
}
else // horizontal word
{
    for (i in range 0 to updated_row)
        check(i)

    for (i in range 0 to updated_column_start)
        check(i)

    for (i in range updated_column_end+1 to final_column)
        check(i)
}

And the trivial questions:

Do you have the compilers speed optimizations set? (if your using one)

Can your word searching algorithm be optimized at all? In any way?

Answer 3

Remember that every character is a value. So use that to your advantage. There are some hash functions that could be computed quickly when iterating on substrings. For instance, lets say we give every letter a 5 bit code (just do c - 'a' + 1 in C):

space = 00000;
a = 00001;
c = 00011;
e = 00101;
t = 01100;

Than you could quickly run over all substrings of a certain size:

a b [c a t] e t h e = 00011 00001 01100;
//Now we just remove the 5 msb and shfit the rest 5 bits left and add the new character.
a b  c [a t e] t h e = (([c a t] & 0xffff) << 5) | e; // == a t e

We can check substrings up to 12 letters this way on most common architectures today.

If a hash code exists in your dictionary you can pull the word from there quickly cause hash codes like this are unique. When you reach the max of 12 letters, you may wish to add another data structures for words starting with those 12 letters. If you find a word that starts with a specific 12 letters than simply create a list or another tiny hash table for the suffixes of each word that starts with that prefix.

Storing a dictionary of all existing word codes should not take more than a few megabytes of memory.

Answer 4

Are you limited only to the classical Tetris shapes when forming words, or will any formation do? Can words bend indefinitely or only once? Can a word be as long as it wants? This get's quite complex if you can do as many bends as you like, effectively making the longest possible words 25 characters long. I would assume you have a list of accepted words. On that assumption I suggest you try something like this:

At the start of the game:
  Iterate tiles:
    Use tile as starting letter
      Store previous tile
      Check the four adjacent tiles
      If a tile can continue a word started by the previous tile, carry on
      Store the next tile
      Move check to next tile

This will create a map on each tile with information how this tile is connected to words around it in the grid. When a column or row is moved check all tiles that has been, or is adjacent to the movement and recalculate the information. When you find a word, and no more tiles can be added to that word; remove it. I'm not sure if this will be faster, it really boils down to how many words are half created. The benefit to this is that the user is most likely trying to create a word from a half complete word on the board. By keeping all these words stored, it is easy to check if a word has been completed.