Hmm, your description sounds remarkably identical to the game "Boggle".
So you want to write AI for boggle huh?
Boggle also has a 'Qu' on one side of one of the dice. Does your game also allow for that?
Anyway, down to algorithms and data structures. My preference for the word list would be a multi-way trie. Probably a 26-way trie to be more specific. Should make for very fast word validity checking.
Once you've got that down, you need something that Gives you all combinations of letters that agree with the rules for connecting letters etc.
For that, I'd recommend a recursive function, and perhaps a list as one of the parameters. That list would contain the positions used so far, so as to not use them twice.
You would call it 25 times, once for each possible starting position, passing a list containing only that position.
The recusrive function would look like this in pseudocode:
There, all solved. You just have to write:
currentSpot = usedPositionsList.front()
for i = -1 to 1
for j = -1 to 1
newSpot = (currentSpot.x+i, currentSpot.y+j)
if newSpot == currentSpot
if not spotIsValid(newSpot)
if spotAlreadyInList(usedPositionsList, newSpot)
checkForRealWord, which looks up the word in the multi-way trie,
spotIsValid, which simply tells you if the coordinates are in the range 0..4,
spotAlreadyInList, which checks that the spot is not in the list already.
Oh and of course, translate pseudocode to C++.