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!