title: Finding the longest word given a trie dictionary and letters
body: <p>For a word-building game I'm working on, I have a trie that stores every possible word from a dictionary. That's about 179,000 at the moment.</p>
  
  <p>The way the game works, there's a 5x5 (or possibly larger in the future, depending on how efficient the solution to this question turns out to be) grid of letters. The player and the PC take turns making words from those letters, getting points based on the letters and length of the words (the letter valuations are similar to Scrabble, but that's not important). Whenever a player makes a word, those letters are removed from the board, and this continues until no words can be made, at which point the grid is reset (and the winner of the round gets a bonus).</p>
  
  <p>The question is this: given a 5x5 grid of letters and that dictionary trie, how can I efficiently determine either the longest word that can be made or a list of all possible words? Note that the letters don't need to be touching each other to be used; any of the grid's letters are fine.</p>
  
  <p>The only way I can think is to essentially do a BFS on the trie, pruning it when the next letter isn't in the grid, but that doesn't seem very efficient to me as it'd have to be tried for each letter in the grid. Is there a better way to do this?</p>