How to determine if optimal word galaxy has a reasonable algorithm
First, determine whether optimal word galaxy is in NP. Ie, given a word galaxy, can you determine if it is optimal in polynomial time? If your answer is "no" then you're dead. About the only way you can find the optimal word galaxy is to list out all possible combinations.
Only if you can find an algorithm that can verify the solution in polynomial time should you even try to proceed to find a polynomial time algorithm to solve the problem. Or prove that the problem is np-complete.
Some intuition tells me, though, that the problem is not in NP. I leave it to those smarter than me to prove (or disprove) my claim.