I really like this idea. The only problem was that over the course of 5 runs, 80% of my letters were vowels. I think this should be developed further it has a lot of potential.
And if you'd like to hear my naive approach on how to prevent unsolvable battles: implement something like a sudoku board generator and solver. Create a 2d matrix of words that can be interlinked and then use that as a bucket of letters to draw from and give the player a randomize button, which will reset the matrix and redraw new letters from that bucket.