Every possible combination/best combination
I am given a 5x5 matrix of characters, each character having a certain value. I need to find the best (highest sum of the values of the included characters) 3 words that can be made. Any number of letters is fine, so long as it is a word. I have a word list (will probably be read from a file into memory as a hash table) to check to see if the series of characters (string) is a word, so checking to see if a string is valid is not a problem. The hard part is that you can start at any place in the matrix, but you can only move to adjacent (or diagonal) cells. For instance, if the matrix was
you could use "MNOTS" but you could not use "GSEJ." I know those aren't really words, but you understand what I mean I hope. Also, once you use a letter, it is removed, and you cannot use that letter any more. That spot in the matrix is left blank (so each adjacent/diagonal matrix now has one less option for the next letter). Note that a character can occur in the matrix multiple times (in different cells), but only the one that is used is removed from the matrix. All of this (except the loading of the word list) needs to happen in about 15 seconds on a standard PC.
A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y
I have thought about implementing the matrix as a graph (adjacency matrix) and check the links to see which are the possible next letters. This would make it easy to remove a letter from the matrix after it has already been used, and to keep up with which letters can be used next. I thought about making another data structure that will hold all the possible combinations of letters which are in the word list (without removing anything from the matrix), then sorting it (or using an AVL tree and traversing from high to low values) based on the values of the words and finding which 3 were the best that were compatible (did not use the same cell).
My problem is how to get all the possible combinations of characters, especially in a reasonable amount of time. Since any number of characters can be used in a possible combination, that will have to be taken into consideration as well. Once I get the valid combinations, what would be the best way to go about determining the 3 best compatible ones?
If anybody can think of any other way to do this, please let me know. This all seems very time consuming, and I'm not sure that it would work in the short period of time it has to work in (only a few seconds). I am new to graphs, hashes, and trees, so this probably isn't the best way to go about this. But that's why I'm asking.